Preferential Query Answering over the Semantic Web with Possibilistic Networks

Stefan Borgwardt, Bettina Fazzinga, Thomas Lukasiewicz, Akanksha Shrivastava, Oana Tifrea-MarciuskaIJCAI 2016 · OpenReview

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:

  1. 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.
  2. Possibilistic Networks: A graphical model, analogous to a Bayesian network, that represents conditional preferences using "possibility distributions" instead of probabilities to rank outcomes.
The database schema for a car booking system, representing the ontological knowledge component of an OP-net.

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.

A possibilistic network representing conditional user preferences. The left graph shows how car type (T) influences color preference (C), while the right graph models preferences over offers (F_O) based on color (C_O) and reviews (R_O).

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

Abstract

In this paper, we explore how ontological knowledge expressed via existential rules can be combined with possibilistic networks (i) to represent qualitative preferences along with domain knowledge, and (ii) to realize preference-based answering of conjunctive queries (CQs). We call these combinations ontological possibilistic networks (OP-nets). We define skyline and k-rank answers to CQs under preferences and provide complexity (including data tractability) results for deciding consistency and CQ skyline membership for OP-nets. We show that our formalism has a lower complexity than a similar existing formalism.
BibTeX
@inproceedings{borgwardt2016preferential,
  author = {Stefan Borgwardt and Bettina Fazzinga and Thomas Lukasiewicz and Akanksha Shrivastava and Oana Tifrea-Marciuska},
  title = {{Preferential Query Answering over the Semantic Web with Possibilistic Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=IIdN4EsH8Dzfy},
}
Figure