Abstract
The tastes of a user can be represented in a natural way by using qualitative preferences. In this paper, we explore how ontological knowledge expressed via existential rules can be combined with CP-theories to (i) represent qualitative preferences along with domain knowledge, and (ii) perform preference-based answering of conjunctive queries (CQs). We call these combinations ontological CP-theories (OCP-theories). We define skyline and k-rank answers to CQs based on the user’s preferences encoded in an OCP-theory, and provide an algorithm for computing them. We also provide precise complexity (including data tractability) results for deciding consistency, dominance, and CQ skyline membership for OCP-theories.
Introduction
As the digital landscape evolves toward "Web 3.0," users are increasingly confronted with an "information overload" problem. Standard query answering systems typically return flat lists of results that satisfy hard constraints but fail to account for individual user preferences. While quantitative preference models (assigning numerical scores) exist, they are often difficult for users to specify accurately. Qualitative models, such as CP-nets and CP-theories, offer a more natural approach using pairwise comparisons (e.g., "I prefer WiFi over Cable"). However, these models traditionally operate in isolation, ignoring the rich domain knowledge captured in ontologies.
This paper introduces Ontological CP-theories (OCP-theories), a framework that bridges this gap by integrating existential rules (Datalog+/–) with the qualitative preference modeling of CP-theories. This allows preferences to be both constrained and informed by complex domain rules.
Methodology: OCP-Theories and Ranking
The core of the OCP-theory framework is the integration of Datalog+/– for modeling domain relationships and CP-theories for modeling conditional preferences (e.g., "If I'm in Rome, I prefer a hotel with a pool").
Skyline and k-Rank Answers
To handle query results, the authors define two types of answers:
- Skyline Answers: Results for which no other answer is strictly preferred according to the OCP-theory.
- k-Rank Answers: An iterative ranking method to produce a top-$k$ list, useful when the skyline is too large.
The k-Rank-Prefs Algorithm
The authors propose the k-Rank-Prefs algorithm to compute these ranked answers. This non-deterministic algorithm traverses the preference order induced by the OCP-theory to identify the most preferred outcomes.
Complexity Analysis and Results
A significant portion of the work is dedicated to a rigorous complexity analysis across various fragments of the Datalog+/– family. The integration is designed to preserve tractability where possible.
Key Findings
- Data Complexity: For most common fragments (e.g., L, LF, AF, G, S, F, GF, SF, WS, WA), deciding consistency, dominance, and skyline membership is tractable (in P). This is a crucial result for practical applications involving large databases.
- Combined Complexity: For more expressive fragments, the complexity increases significantly, ranging from PSPACE-complete to 2EXP-complete.
Conclusion
OCP-theories provide a robust formal foundation for preference-aware query answering in knowledge-rich environments. By maintaining data tractability for many ontological fragments, the framework shows promise for scaling to large-scale applications. Future work includes empirical evaluation of the k-Rank-Prefs algorithm, exploring approximation methods for high-complexity fragments, and investigating optimized special-case algorithms.
Summary updated