Data Complexity of Query Answering in Expressive Description Logics via Tableaux

Magdalena Ortiz, Diego Calvanese, and Thomas Eiter

J. of Automated Reasoning. 41(1):61--98 2008.

The logical foundations of the standard web ontology languages are provided by expressive Description Logics (DLs), such as SHIQ and SHOIQ . In the Semantic Web and other domains, ontologies are increasingly seen also as a mechanism to access and query data repositories. This novel context poses an original combination of challenges that has not been addressed before: (i) sufficient expressive power of the DL to capture common data modelling constructs; (ii) well established and flexible query mechanisms such as those inspired by database technology; (iii) optimisation of inference techniques with respect to data size, which typically dominates the size of ontologies. This calls for investigating data complexity of query answering in expressive DLs. While the complexity of DLs has been studied extensively, few tight characterisations of data complexity were available, and the problem was still open for most DLs of the SH family and for standard query languages like conjunctive queries and their extensions. We tackle this issue and prove a tight coNP upper bound for positive existential queries without transitive roles in SHOQ , SHIQ , and SHOI . We thus establish that, for a whole range of sublogics of SHOIQ that contain AL , answering such queries has coNP-complete data complexity. We obtain our result by a novel tableaux-based algorithm for checking query entailment, which uses a modified blocking condition in the style of Carin. The algorithm is sound for SHOIQ , and shown to be complete for all considered proper sublogics in the SH family.

   title = "Data Complexity of Query Answering in Expressive Description
Logics via Tableaux",
   year = "2008",
   author = "Magdalena Ortiz and Diego Calvanese and Thomas Eiter",
   journal = "J. of Automated Reasoning",
   pages = "61--98",
   number = "1",
   volume = "41",
   doi = "10.1007/s10817-008-9102-9",