caa a22 4500 46318288X CHVBK 20180406164844.0 cr unu---uuuuu 170326e20071001xx s 000 0 eng 10.1007/s10817-007-9078-x doi (NATIONALLICENCE)springer-10.1007/s10817-007-9078-x Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family [Elektronische Daten] [Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati] We propose a new family of description logics (DLs), called DL-Lite, specifically tailored to capture basic ontology languages, while keeping low complexity of reasoning. Reasoning here means not only computing subsumption between concepts and checking satisfiability of the whole knowledge base, but also answering complex queries (in particular, unions of conjunctive queries) over the instance level (ABox) of the DL knowledge base. We show that, for the DLs of the DL-Litefamily, the usual DL reasoning tasks are polynomial in the size of the TBox, and query answering is LogSpace in the size of the ABox (i.e., in data complexity). To the best of our knowledge, this is the first result of polynomial-time data complexity for query answering over DL knowledge bases. Notably our logics allow for a separation between TBox and ABox reasoning during query evaluation: the part of the process requiring TBox reasoning is independent of the ABox, and the part of the process requiring access to the ABox can be carried out by an SQL engine, thus taking advantage of the query optimization strategies provided by current database management systems. Since even slight extensions to the logics of the DL-Litefamily make query answering at least NLogSpace in data complexity, thus ruling out the possibility of using on-the-shelf relational technology for query processing, we can conclude that the logics of the DL-Litefamily are the maximal DLs supporting efficient query answering over large amounts of instances. Springer Science+Business Media B.V., 2007 Description logics nationallicence DL-Lite nationallicence Query answering nationallicence Ontology languages nationallicence Calvanese Diego Faculty of Computer Science, Free University of Bozen-Bolzano, Piazza Domenicani 3, 39100, Bolzano, Italy aut De Giacomo Giuseppe Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut Lembo Domenico Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut Lenzerini Maurizio Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut Rosati Riccardo Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut Journal of Automated Reasoning Springer Netherlands 39/3(2007-10-01), 385-429 0168-7433 39:3<385 2007 39 10817 https://doi.org/10.1007/s10817-007-9078-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10817-007-9078-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Calvanese Diego Faculty of Computer Science, Free University of Bozen-Bolzano, Piazza Domenicani 3, 39100, Bolzano, Italy aut NATIONALLICENCE 700 1- De Giacomo Giuseppe Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut NATIONALLICENCE 700 1- Lembo Domenico Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut NATIONALLICENCE 700 1- Lenzerini Maurizio Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut NATIONALLICENCE 700 1- Rosati Riccardo Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Ariosto 25, 00185, Roma, Italy aut NATIONALLICENCE 773 0- Journal of Automated Reasoning Springer Netherlands 39/3(2007-10-01), 385-429 0168-7433 39:3<385 2007 39 10817 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer