Equality Generating Dependencies in Description Logics via Path Agreements | SpringerLink
Skip to main content

Equality Generating Dependencies in Description Logics via Path Agreements

  • Conference paper
  • First Online:
AI 2024: Advances in Artificial Intelligence (AI 2024)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 15443))

Included in the following conference series:

  • 166 Accesses

Abstract

We consider generalizing path functional dependencies (PFDs) in Boolean complete feature logics to path description dependencies (PDDs) that now allow occurrences of inverse features. In particular, allowing such occurrences in component path descriptions of PDDs leads to a circumstance in which different notions of path agreement are now possible. We explore the cases of set intersection, set equality and non-empty set equality, studying in particular the decidability and complexity of entailment under combinations of these notions of path agreement.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8465
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Violating this latter condition leads immediately to undecidability [12].

References

  1. Ackermann, W.: Uber die Erfullbarkeit gewisser Zahlausdrucke. Math. Ann. 100, 638–649 (1928)

    Article  MathSciNet  Google Scholar 

  2. Artale, A., Franconi, E., Peñaloza, R., Sportelli, F.: A decidable very expressive description logic for databases. In: d’Amato, C., et al. (eds.) ISWC 2017. LNCS, vol. 10587, pp. 37–52. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68288-4_3

    Chapter  Google Scholar 

  3. Borgida, A., Franconi, E., Toman, D., Weddell, G.E.: Understanding document data sources using ontologies with referring expressions. In: Aziz, H., Corrêa, D., French, T. (eds.) AI 2022. LNCS, vol. 13728, pp. 367–380. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22695-3_26

    Chapter  Google Scholar 

  4. Fischer, M.J., Ladner, R.E.: Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18(2), 194–211 (1979)

    Article  MathSciNet  Google Scholar 

  5. Franconi, E.: A treatment of plurals and plural quantifications based on a theory of collections. Minds Mach. 3(4), 453–474 (1993)

    Article  Google Scholar 

  6. Fürer, M.: Alternation and the Ackermann case of the decision problem. L’Enseignement Mathematique (1981)

    Google Scholar 

  7. Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)

    Google Scholar 

  8. Ito, M., Weddell, G.: Implication problems for functional constraints on databases supporting complex objects. J. Comput. Syst. Sci. 49(3), 726–768 (1994)

    Article  MathSciNet  Google Scholar 

  9. McIntyre, S., Toman, D., Weddell, G.E.: FunDL - a family of feature-based description logics, with applications in querying structured data sources. In: Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, pp. 404–430 (2019)

    Google Scholar 

  10. Toman, D., Weddell, G.: On attributes, roles, and dependencies in description logics and the Ackermann case of the decision problem. In: Description Logics 2001, vol. 49, pp. 76–85. CEUR-WS (2001)

    Google Scholar 

  11. Toman, D., Weddell, G.E.: On the interaction between inverse features and path-functional dependencies in description logics. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pp. 603–608 (2005)

    Google Scholar 

  12. Toman, D., Weddell, G.E.: On keys and functional dependencies as first-class citizens in description logics. J. Aut. Reasoning 40(2–3), 117–132 (2008)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to David Toman .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Feng, E., Franconi, E., Patel-Schneider, P.F., Toman, D., Weddell, G. (2025). Equality Generating Dependencies in Description Logics via Path Agreements. In: Gong, M., Song, Y., Koh, Y.S., Xiang, W., Wang, D. (eds) AI 2024: Advances in Artificial Intelligence. AI 2024. Lecture Notes in Computer Science(), vol 15443. Springer, Singapore. https://doi.org/10.1007/978-981-96-0351-0_16

Download citation

  • DOI: https://doi.org/10.1007/978-981-96-0351-0_16

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-96-0350-3

  • Online ISBN: 978-981-96-0351-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics