Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family
Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family
复制标题
DOI：
10.1007/s10817-007-9078-x
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
Diego Calvanese;Giuseppe De Giacomo;D. Lembo;M. Lenzerini;R. Rosati
中科院分区：
文献类型：
--
作者：
Diego Calvanese;Giuseppe De Giacomo;D. Lembo;M. Lenzerini;R. Rosati
我们提出了一个新的描述逻辑（dl）家族，称为ddl - lite，专门用于捕获基本本体语言，同时保持较低的推理复杂性。这里的推理不仅意味着计算概念之间的包容和检查整个知识库的可满足性，而且还意味着在DL知识库的实例级（ABox）上回答复杂的查询（特别是连接查询的联合）。我们表明，对于DL- litefamily的DL，通常的DL推理任务是TBox大小的多项式，查询回答是ABox大小的logspace（即数据复杂度）。据我们所知，这是在深度学习知识库上查询回答的多项式时间数据复杂度的第一个结果。值得注意的是，我们的逻辑允许在查询评估期间分离TBox和ABox推理：需要TBox推理的部分过程独立于ABox，而需要访问ABox的部分过程可以由SQL引擎执行，从而利用当前数据库管理系统提供的查询优化策略。由于即使对dl - litefamily的逻辑进行轻微的扩展，也会使查询回答的数据复杂性至少达到NLogSpacein，从而排除了使用现成关系技术进行查询处理的可能性，因此我们可以得出结论，dl - litefamily的逻辑是在大量实例上支持高效查询回答的最大dl。
We propose a new family of description logics (DLs), calledDL-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 theDL-Litefamily, the usual DL reasoning tasks are polynomial in the size of the TBox, and query answering is LogSpacein 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 theDL-Litefamily make query answering at least NLogSpacein data complexity, thus ruling out the possibility of using on-the-shelf relational technology for query processing, we can conclude that the logics of theDL-Litefamily are the maximal DLs supporting efficient query answering over large amounts of instances.