Query Answering in Expressive Variants of DL-Lite

Proc. of the 15th Italian Symp. on Advanced Database Systems (SEBD 2007). 2007.

The use of ontologies in various application domains, such as Data Integration, the Semantic Web, or ontology-based data management, where ontologies provide the access to large amounts of data, is posing challenging requirements w.r.t. the trade-off between the expressive power of a Description Logic and the efficiency of reasoning. The logics of the DL-Lite family were specifically designed to meet such requirements and optimized w.r.t. the data complexity of answering complex types of queries. In this paper we propose DL-Litebool , an extension of DL-Lite with full Booleans and number restrictions, and study the complexity of reasoning in DL-Litebool and its significant sub-logics. We obtain our results, together with useful insights into the properties of the studied logics, by a novel reduction to the one-variable fragment of first-order logic. We study the computational complexity of satisfiability and subsumption, and the data complexity of answering positive existential queries (which extend unions of conjunctive queries). Notably, we extend the LogSpace upper bound for the data complexity of answering unions of conjunctive queries in DL-Lite to positive queries and to the possibility of expressing also number restrictions, hence local functionality.

@inproceedings{SEBD-2007-dllite,
   title = "Query Answering in Expressive Variants of DL-Lite",
   year = "2007",
   author = "Alessandro Artale and Diego Calvanese and Roman Kontchakov
and Michael Zakharyaschev",
   booktitle = "Proc. of the 15th Italian Symp. on Advanced Database Systems
(SEBD 2007)",
   pages = "250--257",
}