Query and Predicate Emptiness in Description Logics

Franz BaaderFranz Baader, Meghyn BienvenuMeghyn Bienvenu, Carsten LutzCarsten Lutz, Frank WolterFrank Wolter

Download

Franz Baader, Meghyn Bienvenu, Carsten Lutz, Frank Wolter
Query and Predicate Emptiness in Description Logics
In Fangzhen Lin and Ulrike Sattler, eds., Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR2010), 2010. AAAI Press

Details
Bibtex

KurzfassungAbstract
Ontologies can be used to provide an enriched vocabulary for the formulation of queries over instance data. We identify query emptiness and predicate emptiness as two central reasoning services in this context. Query emptiness asks whether a given query has an empty answer over all data sets formulated in a given signature. Predicate emptiness is defined analogously, but quantifies universally over all queries that contain a given predicate. In this paper, we determine the computational complexity of query emptiness and predicate emptiness in the EL, DL-Lite, and ALC-families of description logics, investigate the connection to ontology modules, and perform a practical case study to evaluate the new reasoning services.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaderBLW10,
  author = {Franz {Baader} and Meghyn {Bienvenu} and Carsten {Lutz} and Frank {Wolter}},
  booktitle = {Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning ({KR2010})},
  editor = {Fangzhen {Lin} and Ulrike {Sattler}},
  publisher = {AAAI Press},
  title = {Query and Predicate Emptiness in Description Logics},
  year = {2010},
}