2007 | Diego Calvanese · Giuseppe De Giacomo · Domenico Lembo · Maurizio Lenzerini · Riccardo Rosati
The paper introduces DL-Lite, a family of description logics (DLs) designed to capture basic ontology languages while maintaining low reasoning complexity. Reasoning in DL-Lite includes concept subsumption, knowledge base satisfiability, and answering complex queries over the instance level (ABox). The authors show that for DL-Lite, reasoning tasks are polynomial in the size of the TBox, and query answering is LogSPACE in the size of the ABox, achieving polynomial data complexity for query answering. This is the first result of this kind for DL knowledge bases. DL-Lite allows separation between TBox and ABox reasoning during query evaluation, with TBox reasoning independent of the ABox and ABox access handled by an SQL engine, leveraging database optimization strategies. Extensions to DL-Lite increase query answering complexity to NLOGSPACE, making it infeasible to use relational technology for query processing. Thus, DL-Lite is the maximal DL family supporting efficient query answering over large instance sets. The paper highlights the importance of efficient reasoning algorithms for managing large ontologies, especially in applications like the Semantic Web and data integration, where complex queries and large data sets are common. Traditional DLs often suffer from exponential reasoning complexity, making them unsuitable for large-scale applications. DL-Lite addresses these challenges by providing tractable reasoning and efficient query answering.The paper introduces DL-Lite, a family of description logics (DLs) designed to capture basic ontology languages while maintaining low reasoning complexity. Reasoning in DL-Lite includes concept subsumption, knowledge base satisfiability, and answering complex queries over the instance level (ABox). The authors show that for DL-Lite, reasoning tasks are polynomial in the size of the TBox, and query answering is LogSPACE in the size of the ABox, achieving polynomial data complexity for query answering. This is the first result of this kind for DL knowledge bases. DL-Lite allows separation between TBox and ABox reasoning during query evaluation, with TBox reasoning independent of the ABox and ABox access handled by an SQL engine, leveraging database optimization strategies. Extensions to DL-Lite increase query answering complexity to NLOGSPACE, making it infeasible to use relational technology for query processing. Thus, DL-Lite is the maximal DL family supporting efficient query answering over large instance sets. The paper highlights the importance of efficient reasoning algorithms for managing large ontologies, especially in applications like the Semantic Web and data integration, where complex queries and large data sets are common. Traditional DLs often suffer from exponential reasoning complexity, making them unsuitable for large-scale applications. DL-Lite addresses these challenges by providing tractable reasoning and efficient query answering.