Preference-based inconsistency-tolerant query answering under existential rules

摘要

Ontology-mediated query answering (OMQA) emerged as a paradigm to enhance querying of data sources with an ontology that encodes background knowledge. In applications involving large amounts of data from multiple data sources, it might well be the case that inconsistency arises, making standard query answering useless, since everything is entailed by an inconsistent knowledge base. Being able to provide meaningful query answers in the presence of inconsistency is thus a critical issue to make OMQA systems successful in practice. The problem of querying inconsistent knowledge has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics of query answering have been proposed, that is, approaches to answer queries in a meaningful way despite the knowledge at hand being inconsistent. Most of the semantics in the literature are based on the notion of repair, that is, a “maximal” consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. Specifically, we introduce preference rules, a declarative formalism which enable users to express (i) preferences over both the database and the knowledge that can be derived from it via an ontology, and (ii) preconditions for preferences to hold. We then define two notions of preferred repairs which take preference rules into account. This naturally leads us to introducing preference-aware counterparts of popular inconsistency-tolerant semantics, where only preferred repairs are considered for query answering. We provide a thorough analysis of the data and combined complexity of different relevant problems for a wide range of existential rule languages.