论文标题
查询与轨道的优先数据优先级不一致：算法，实现和实验
Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments
论文作者
论文摘要
我们研究了对优先级知识基础回答不一致的查询的实用算法，该查询包括逻辑理论，一组事实以及相互矛盾的事实之间的优先关系。我们根据两个最佳维修概念（帕累托和完成）考虑了三种知名语义（AR，IAR和勇敢）。确定这些语义下的查询答案是否在一系列逻辑理论的数据复杂性中（CO）NP完成，并且在没有优先关系的情况下，已经为基于维修的语义设计了基于SAT的过程，或者该关系具有特殊的结构。本文介绍了第一个SAT编码W.R.T.一般优先关系，并提出了几种使用现有和新编码来计算基于（最佳）基于维修的语义的答案的方法，通过利用SAT求解器的不同推理模式。对我们实施的全面实验评估比较了（i）基于不同种类的维修的语义的影响，以及（ii）相同语义的替代程序的相对性能。
We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases, which consist of a logical theory, a set of facts, and a priority relation between conflicting facts. We consider three well-known semantics (AR, IAR and brave) based upon two notions of optimal repairs (Pareto and completion). Deciding whether a query answer holds under these semantics is (co)NP-complete in data complexity for a large class of logical theories, and SAT-based procedures have been devised for repair-based semantics when there is no priority relation, or the relation has a special structure. The present paper introduces the first SAT encodings for Pareto- and completion-optimal repairs w.r.t. general priority relations and proposes several ways of employing existing and new encodings to compute answers under (optimal) repair-based semantics, by exploiting different reasoning modes of SAT solvers. The comprehensive experimental evaluation of our implementation compares both (i) the impact of adopting semantics based on different kinds of repairs, and (ii) the relative performances of alternative procedures for the same semantics.
