Introduction
As the Social Semantic Web evolves, the demand for intelligent search and recommendation systems increases. These systems must navigate a dual landscape: "hard" ontological knowledge—strict rules defining a domain—and "soft" user preferences—subjective, conditional desires. For instance, a user might prefer a new car over an old one, but if forced to choose an old car, they might prioritize specific colors or features.
Existing frameworks like OCP-theories (combining Datalog+/- with CP-nets) offer high expressivity but suffer from extreme computational costs, often reaching PSPACE-complete complexity for basic tasks. This paper introduces Ontological Possibilistic Networks (OP-nets), a novel framework designed to bridge this gap by providing a more efficient way to handle qualitative preferences alongside domain knowledge.
The OP-net Framework
An OP-net integrates two core components:
- Datalog+/- Ontologies: A family of logic languages used to express existential rules. These rules model the domain's structure and ensure that any query result is logically consistent with real-world constraints.
- Possibilistic Networks: A graphical model, analogous to a Bayesian network, that represents conditional preferences using "possibility distributions" instead of probabilities to rank outcomes.
The framework focuses on two types of query results:
- Skyline Answers: Results that are not "dominated" (outranked) by any other possible result according to the user's preferences.
- k-Rank Answers: The top-$k$ results based on a numerical ranking induced by the possibilistic network.
Modeling Preferences and Knowledge
To illustrate the power of OP-nets, the authors use a running example of a car booking system. The domain knowledge is stored in relational tables, while user preferences are mapped through a network that defines how different attributes influence each other.
In this model, the ontology doesn't just coexist with preferences; it constrains them. If a user prefers a combination of features that the ontology deems impossible (e.g., a specific model not present in the database), the OP-net filters these out while maintaining the relative ranking of valid options.
Computational Efficiency
The primary breakthrough of OP-nets lies in their computational tractability. In widely used CP-nets, dominance testing—determining if one result is better than another—is PSPACE-complete. In contrast, dominance testing in possibilistic networks is polynomial. This shift drastically lowers the overall complexity of the system.
By mapping these networks to various fragments of Datalog+/- (such as Linear, Guarded, or Sticky rules), the authors demonstrate that deciding skyline membership typically falls within the $\Delta^P_2$ or $\Delta^P_3$ complexity classes. Furthermore, for several fragments, query answering is data-tractable (polynomial or even in $AC^0$ relative to database size), making it feasible for large-scale web applications.
Conclusion and Future Work
OP-nets provide a significant step forward in preferential query answering by offering a framework that is both expressive and computationally efficient. While the current work is primarily theoretical, it lays the groundwork for practical implementations in the Semantic Web. Future research will focus on empirical evaluations, exploring even more expressive possibilistic logics, and handling non-monotonic reasoning where new information might revise existing preference rankings.
Summary updated