Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice
Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice
复制标题
DOI：
10.1613/jair.3470
复制
发表时间：
2014-01
期刊：
影响因子：
--
通讯作者：
B. C. Grau;B. Motik;G. Stoilos;Ian Horrocks
中科院分区：
文献类型：
--
作者：
B. C. Grau;B. Motik;G. Stoilos;Ian Horrocks
为了实现查询应答的可扩展性，语义 Web 应用程序的开发人员常常被迫使用不完整的 OWL 2 推理器，该推理器无法导出至少一个查询、本体和数据集的所有答案。然而，缺乏完整性保证对于医疗保健和国防等领域的应用程序来说可能是不可接受的，因为缺少答案可能会对应用程序的功能产生不利影响。此外，即使应用程序可以容忍一定程度的不完整性，估计丢失的答案数量和类型通常也是有利的。在本文中，我们提出了一种新颖的基于逻辑的框架，允许人们检查推理器对于给定的查询 Q 和本体 T 是否完整——也就是说，推理器是否保证计算 Q 的所有答案。 T 和任意数据集 A。由于本体和典型查询通常在应用程序设计时固定，因此我们的方法允许应用程序开发人员检查已知不完整的推理器对于与应用程序相关的输入类型实际上是否完整。我们还提出了一种技术，给定查询 Q、本体 T 以及满足某些假设的推理器 R1 和 R2，可用于确定对于每个数据集 A，推理器 R1 是否计算更多 Q 的答案。 T 和 A 比推理器 R2 强。这使得应用程序开发人员可以选择为 Q 和 T 提供最高完整性的推理器，并且与应用程序的可扩展性要求兼容。因此，我们的结果为未来基于本体的信息系统的设计提供了理论和实践基础，该系统最大限度地提高可扩展性，同时最大限度地减少甚至消除查询答案的不完整性。
To achieve scalability of query answering, the developers of Semantic Web applications are often forced to use incomplete OWL 2 reasoners, which fail to derive all answers for at least one query, ontology, and data set. The lack of completeness guarantees, however, may be unacceptable for applications in areas such as health care and defence, where missing answers can adversely affect the application's functionality. Furthermore, even if an application can tolerate some level of incompleteness, it is often advantageous to estimate how many and what kind of answers are being lost. In this paper, we present a novel logic-based framework that allows one to check whether a reasoner is complete for a given query Q and ontology T -- that is, whether the reasoner is guaranteed to compute all answers to Q w.r.t. T and an arbitrary data set A. Since ontologies and typical queries are often fixed at application design time, our approach allows application developers to check whether a reasoner known to be incomplete in general is actually complete for the kinds of input relevant for the application. We also present a technique that, given a query Q, an ontology T, and reasoners R1 and R2 that satisfy certain assumptions, can be used to determine whether, for each data set A, reasoner R1 computes more answers to Q w.r.t. T and A than reasoner R2. This allows application developers to select the reasoner that provides the highest degree of completeness for Q and T that is compatible with the application's scalability requirements. Our results thus provide a theoretical and practical foundation for the design of future ontology-based information systems that maximise scalability while minimising or even eliminating incompleteness of query answers.