TLDR: This research explores the computational feasibility of Weighted Sums of Minimal Supports (WSMS), a new method for quantifying how much each data fact contributes to a query answer, in the context of Ontology-Mediated Query Answering (OMQA). The paper finds that WSMS computation is efficient for OMQs that can be rewritten into standard database queries (like those using DL-Lite ontologies), but becomes intractable with features like reachability axioms or concept conjunction. It introduces ‘interaction-free’ OMQs as a class where tractability can be maintained for more complex queries, offering a practical path for explaining query answers in knowledge-rich systems.
Understanding why a database query returns a particular answer is crucial, especially in complex systems like those involving ontologies. Traditionally, explanations focused on qualitative aspects, such as identifying the minimal sets of facts that support an answer. However, recent research has shifted towards quantitative approaches, aiming to assign a ‘score’ to each piece of data, reflecting its contribution to a query’s outcome.
One prominent method for this quantitative explanation is based on the ‘Shapley value,’ a concept borrowed from cooperative game theory. It aims to fairly distribute a ‘wealth’ (in this case, the query answer) among ‘players’ (the data facts) based on their individual contributions. While theoretically appealing, computing the traditional Shapley value for query answers has proven to be computationally very challenging, often intractable even for simple queries.
A new family of responsibility measures, called Weighted Sums of Minimal Supports (WSMS), has recently emerged as a more computationally friendly alternative. Instead of focusing on a single ‘wealth’ function, WSMS defines a fact’s score as a weighted sum of the sizes of the minimal sets of facts (minimal supports) that contain it and contribute to the query answer. This approach has shown more favorable computational properties in standard database settings.
This research paper, titled “Tractable Responsibility Measures for Ontology-Mediated Query Answering” by Meghyn Bienvenu, Diego Figueira, and Pierre Lafourcade, delves into the complexity of computing these WSMS scores specifically within the realm of Ontology-Mediated Query Answering (OMQA). OMQA involves using an ontology (a formal representation of knowledge) to enrich and reason over data, making query answering more powerful but also more complex. The study particularly focuses on Description Logic (DL) ontologies, especially the widely adopted DL-Lite family, known for its computational advantages.
The findings reveal several key insights into the tractability (computational feasibility) of WSMS in OMQA. A significant positive result is that WSMS computation is efficient (polynomial time in data complexity) for a broad class of ontology-mediated queries that can be ‘rewritten’ into standard database queries, such as those involving DL-Lite ontologies and conjunctive queries. This means that for these types of queries, existing relational database systems can be leveraged to compute responsibility scores efficiently using simple SQL queries.
However, the paper also identifies scenarios where WSMS computation becomes intractable (computationally very difficult). This includes cases where the ontology language can express ‘reachability queries’ (e.g., axioms that allow inferring connections along a chain of relationships) or when the ontology language supports ‘concept conjunction’ (combining multiple concepts, as seen in DLs like EL and some Horn DL-Lite dialects). Furthermore, even for seemingly simple ‘unions of conjunctive queries,’ intractability can arise, highlighting the subtle complexities involved.
To better understand the boundaries of tractability, the researchers introduce the concept of ‘interaction-free’ OMQs. This class of queries, inspired by ‘self-join free’ queries in databases, ensures that a single data fact isn’t used to satisfy multiple parts of a query in complex, interacting ways. For these ‘interaction-free’ OMQs, particularly those based on DL-Lite ontologies and with certain structural properties, the computation of WSMS becomes tractable. This is achieved by breaking down the problem into computing minimal supports for simpler, atomic queries and then combining these results efficiently.
Also Read:
- Unlocking Logical Formulas: A New Approach to Learning Concepts in Description Logic ALC
- Transparent AI Collaboration: SynLang and the Philosophy of Shared Intelligence
In essence, this research provides a roadmap for understanding when and how quantitative responsibility measures can be efficiently computed in the complex landscape of ontology-mediated query answering. It highlights the potential for practical applications by showing how these measures can be integrated with existing database technologies, while also pinpointing the specific features of ontologies and queries that lead to computational challenges. For more technical details, you can refer to the full research paper: Tractable Responsibility Measures for Ontology-Mediated Query Answering.
