TLDR: This research introduces a rule-based framework for specifying preferences over conflicting facts in inconsistent knowledge bases. It addresses the challenge of defining priority relations, which are crucial for selecting optimal data “repairs” and obtaining meaningful query answers. The framework allows users to define flexible preference rules, handles problematic preference cycles through various resolution techniques, and includes a preliminary Answer Set Programming implementation and experimental evaluation.
The digital age has led to an explosion of data, often stored in vast knowledge bases. However, this data isn’t always perfect; it can be inconsistent, meaning it contains contradictory information. Imagine a university database where a person is listed as both an “Associate Professor” and a “Full Professor” simultaneously, or as “Faculty” and “Administrative Staff” – these are conflicts. Getting meaningful answers from such inconsistent data is a significant challenge.
Traditional methods for querying inconsistent knowledge bases often rely on “repairs,” which are maximal consistent subsets of the data. If a database has many inconsistencies, it can have a huge number of possible repairs, making it difficult to decide which information to trust. This is where the concept of “prioritized repairs” comes in, where a priority relation between conflicting facts helps select the most optimal repairs. However, a crucial missing piece has been how to easily define these priority relations. Users can’t realistically manually input a binary preference for every single conflicting fact.
A new research paper, available at this link, introduces a novel rule-based framework to address this very problem. The paper, authored by Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, and Robin Jean, proposes a declarative way to specify and compute a priority relation between conflicting facts. Their approach allows users to define “preference rules” that state when one fact should be preferred over another. These rules can be quite sophisticated, referring to the presence or absence of other facts in the dataset, or even metadata like the date a fact was added or its source’s reliability. For instance, a rule might state that “more recently added facts are preferred,” or “facts from a more trusted source are preferred.”
Also Read:
- A New Approach to Learning Logical Rules with Minimum Message Length
- Bridging the Gap: Validating Data with SHACL and OWL Ontologies
Addressing Preference Cycles
One of the key innovations of this framework is its ability to handle “cycles” in expressed preferences. A cycle occurs when, for example, fact A is preferred over B, B over C, and C over A – creating a circular preference that is inherently problematic. The researchers explore two main ways to tackle this: first, by determining if a set of preference rules will always produce an acyclic (non-circular) relation, and second, by providing pragmatic techniques to extract an acyclic relation even if cycles initially arise. These techniques involve different strategies for resolving conflicts, such as “going up” (prioritizing rules from higher importance levels) or “going down” (removing less important preferences that cause cycles).
The paper also details a preliminary implementation of their framework using Answer Set Programming (ASP), a powerful declarative programming paradigm. This implementation allows them to evaluate the preference rules, apply the chosen cycle resolution techniques to obtain a clear priority relation, and then answer queries based on these prioritized repairs. They conducted experiments to evaluate the runtime and the size of the resulting priority relations, comparing different cycle resolution strategies. While their ASP implementation is a significant step, they also compare it to existing SAT-based implementations for optimal repair-based semantics, noting that their system is the first to handle non-binary conflicts effectively.
This work represents a significant step towards making inconsistency-tolerant query answering more practical and user-friendly. By providing a flexible, rule-based method for defining preferences and robust techniques for resolving preference cycles, the researchers pave the way for more reliable and meaningful insights from large, potentially inconsistent knowledge bases. Future work includes extending the static analysis of preference rules and developing a truly end-to-end system for generating input logic programs from various data formats.
