%0 Journal Article %1 keyhere %A Calvanese, Diego %A Giacomo, Giuseppe De %A Lembo, Domenico %A Lenzerini, Maurizio %A Rosati, Riccardo %D 2007 %J Journal of Automated Reasoning %K imported %N 3 %P 385--429 %T Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-LiteFamily %U http://dx.doi.org/10.1007/s10817-007-9078-x %V 39 %X Abstract  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 answeringcomplex queries (in particular, unions of conjunctive queries) over the instance level (ABox) of the DL knowledge base. Weshow that, for the DLs of the DL-Lite family, 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-timedata complexity for query answering over DL knowledge bases. Notably our logics allow for a separation between TBox and ABoxreasoning during query evaluation: the part of the process requiring TBox reasoning is independent of the ABox, and the partof the process requiring access to the ABox can be carried out by an SQL engine, thus taking advantage of the query optimizationstrategies provided by current database management systems. Since even slight extensions to the logics of the DL-Lite family make query answering at least NLogSpace in data complexity, thus ruling out the possibility of using on-the-shelf relational technology for query processing, wecan conclude that the logics of the DL-Lite family are the maximal DLs supporting efficient query answering over large amounts of instances.

@article{keyhere, abstract = {Abstract  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 answeringcomplex queries (in particular, unions of conjunctive queries) over the instance level (ABox) of the DL knowledge base. Weshow that, for the DLs of the DL-Lite family, 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-timedata complexity for query answering over DL knowledge bases. Notably our logics allow for a separation between TBox and ABoxreasoning during query evaluation: the part of the process requiring TBox reasoning is independent of the ABox, and the partof the process requiring access to the ABox can be carried out by an SQL engine, thus taking advantage of the query optimizationstrategies provided by current database management systems. Since even slight extensions to the logics of the DL-Lite family make query answering at least NLogSpace in data complexity, thus ruling out the possibility of using on-the-shelf relational technology for query processing, wecan conclude that the logics of the DL-Lite family are the maximal DLs supporting efficient query answering over large amounts of instances.}, added-at = {2008-11-06T18:35:27.000+0100}, author = {Calvanese, Diego and Giacomo, Giuseppe De and Lembo, Domenico and Lenzerini, Maurizio and Rosati, Riccardo}, biburl = {https://www.bibsonomy.org/bibtex/22eae8c30741753abe6b8063082035d17/joergh}, description = {SpringerLink - Zeitschriftenbeitrag}, interhash = {a1065fd36f8398106b2d46beb663eed4}, intrahash = {2eae8c30741753abe6b8063082035d17}, journal = {Journal of Automated Reasoning}, keywords = {imported}, month = {#oct#}, number = 3, pages = {385--429}, timestamp = {2008-11-06T18:35:27.000+0100}, title = {Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-LiteFamily}, url = {http://dx.doi.org/10.1007/s10817-007-9078-x}, volume = 39, year = 2007 }