Skip to main content

Preference−Based Query Answering in Datalog+⁄− Ontologies

Thomas Lukasiewicz‚ Maria Vanina Martinez and Gerardo I. Simari

Abstract

The study of preferences has a long tradition in many disciplines, but it has only relatively recently entered the realm of data management through their application in answering queries to relational databases. The current revolution in data availability through the Web and, perhaps most importantly in the last few years, social media sites and applications, puts ontology languages at the forefront of data and information management technologies. In this paper, we propose the first (to our knowledge) integration of ontology languages with preferences as in relational databases by developing PrefDatalog+⁄−, an extension of the Datalog+⁄− family of languages with preference management formalisms closely related to those previously studied for relational databases. We focus on two kinds of answers to queries that are relevant to this setting, skyline and k-rank (a generalization of top-k queries), and develop algorithms for computing these answers to both DAQs (disjunctions of atomic queries) and CQs (conjunctive queries). We show that DAQ answering in PrefDatalog+⁄− can be done in polynomial time in the data complexity, as in relational databases, as long as query answering can also be done in polynomial time (in the data complexity) in the underlying classical ontology.

Book Title
Proceedings of the 23rd International Joint Conference on Artificial Intelligence‚ IJCAI 2013‚ Beijing‚ China‚ August 3−9‚ 2013
Editor
Francesca Rossi
Pages
1017−1023
Publisher
AAAI Press / International Joint Conferences on Artificial Intelligence
Year
2013