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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Violating this latter condition leads immediately to undecidability [12].
References
Ackermann, W.: Uber die Erfullbarkeit gewisser Zahlausdrucke. Math. Ann. 100, 638–649 (1928)
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
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
Fischer, M.J., Ladner, R.E.: Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18(2), 194–211 (1979)
Franconi, E.: A treatment of plurals and plural quantifications based on a theory of collections. Minds Mach. 3(4), 453–474 (1993)
Fürer, M.: Alternation and the Ackermann case of the decision problem. L’Enseignement Mathematique (1981)
Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)
Ito, M., Weddell, G.: Implication problems for functional constraints on databases supporting complex objects. J. Comput. Syst. Sci. 49(3), 726–768 (1994)
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)
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)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
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)