Article

Combining existential rules with the power of CP-theories

Authors:

Tommaso Di Noia,

Thomas Lukasiewicz,

Maria Vanina Martinez,

Gerardo I. Simari,

Oana Tifrea-MarciuskaAuthors Info & Claims

IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence

Pages 2918 - 2925

Published: 25 July 2015 Publication History

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.

References

[1]

M. Bienvenu, J. Lang, and N. Wilson. From preference logics to preference languages, and back. In Proc. of KR, pp. 214-224, 2010.

[2]

S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In Proc. of ICDE, pp. 421-430, 2001.

Digital Library

[3]

F. Boubekeur, M. Boughanem, and L. Tamine-Lechani. Semantic information retrieval based on CP-Nets. In Proc. of FUZZ-IEEE, pp. 1-7, 2007.

[4]

C. Boutilier, R. I. Brafman, H. H. Hoos, and D. Poole. Reasoning with conditional ceteris paribus preference statements. In Proc. of UAI, pp. 71-80, 1999.

Digital Library

[5]

C. Boutilier, R. I. Brafman, C. Domshlak, H. H. Hoos, and D. Poole. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res., 21:135-191, 2004.

[6]

R. I. Brafman, C. Domshlak, and S.E. Shimony. On graphical modeling of preference and importance. J. Artif. Intell. Res., 25(1):389-424, 2006.

Digital Library

[7]

G. Brewka. Preferences, contexts and answer sets. In Proc. of ICLP, p. 22, 2007.

Digital Library

[8]

A. Calì, G. Gottlob, and T. Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem., 14:57-83, 2012.

Digital Library

[9]

A. Calì, G. Gottlob, and A. Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193:87-128, 2012.

Digital Library

[10]

A. Calì, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. J. Artif. Intell. Res., 48:115-174, 2013.

[11]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3):385-429, 2007.

Digital Library

[12]

T. Di Noia, T. Lukasiewicz, and G. I. Simari. Reasoning with semantic-enabled qualitative preferences. In Proc. of SUM, pp. 374-386, 2013.

[13]

R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. Theor. Comput. Sci., 336(1):89-124, 2005.

[14]

J. Goldsmith, J. Lang, M. Truszczynski, and N. Wilson. The computational complexity of dominance and consistency in CP-nets. J. Artif. Intell. Res., 33:403-432, 2008.

Digital Library

[15]

K. Govindarajan, B. Jayaraman, and S. Mantha. Preference logic programming. In Proc. of ICLP, pp. 731-745, 1995.

[16]

D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 2, pp. 67-161. MIT Press, 1990.

Digital Library

[17]

M. Lacroix and P. Lavency. Preferences: Putting more knowledge into queries. In Proc. of VLDB, pp. 1-4, 1987.

Digital Library

[18]

T. Lukasiewicz and J. Schellhase. Variable-strength conditional preferences for ranking objects in ontologies. J. Web Sem., 5(3):180-194, 2007.

Digital Library

[19]

T. Lukasiewicz, M. V. Martinez, and G. I. Simari. Preference-based query answering in Datalog+/- ontologies. In Proc. of IJCAI, pp. 501-518, 2013.

Digital Library

[20]

T. Lukasiewicz, M. V. Martinez, A. Pieris, and G. I. Simari. From classical to consistent query answering under existential rules. In Proc. of AAAI, pp. 1546-1552, 2015.

[21]

D. Mindolin and J. Chomicki. Preference elicitation in prioritized skyline queries. VLDB J., 20(2):157-182, 2011.

Digital Library

[22]

C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[23]

G. R. Santhanam, S. Basu, and V. Honavar. Dominance testing via model checking. In Proc. of AAAI, pp. 357-362, 2010.

[24]

W. Siberski, J. Z. Pan, and U. Thaden. Querying the Semantic Web with preferences. In Proc. of ISWC, pp. 612-624, 2006.

Digital Library

[25]

K. Stefanidis, G. Koutrika, and E. Pitoura. A survey on representation, composition and application of preferences in database systems. ACM Trans. Database Syst., 36, 2011.

Digital Library

[26]

M. Y. Vardi. The complexity of relational query languages (extended abstract). In Proc. of STOC, pp. 137-146, 1982.

Digital Library

[27]

H. Wang, X. Zhou, W. Chen, and P. Ma. Top-k retrieval using conditional preference networks. In Proc. of CIKM, pp. 2075-2079, 2012.

Digital Library

[28]

N. Wilson. Extending CP-nets with stronger conditional preference statements. In Proc. of AAAI, pp. 735-741, 2004.

Digital Library

Cited By

Malizia EAndre EKoenig SDastani MSukthankar G(2018)More Complexity Results about Reasoning over ( m )CP-netsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237930(1540-1548)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237930
Martinez M(2017)Knowledge engineering for intelligent decision supportProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3172029(5131-5135)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3172029
Ceylan ILukasiewicz TPeñaloza RTifrea-Marciuska O(2017)Query answering in ontologies under preference rankingsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171777(943-949)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171777
Show More Cited By

Combining existential rules with the power of CP-theories
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Combining RDF and SPARQL with CP-theories to reason about preferences in a Linked Data setting

Preference representation and reasoning play a central role in supporting users with complex and multi-factorial decision processes. In fact, user tastes can be used to filter information and data in a personalized way, thus maximizing their expected ...
Query patterns for existential rules
RR'12: Proceedings of the 6th international conference on Web Reasoning and Rule Systems

In this paper we study query answering over ontologies expressed in Datalog+/---, i.e., datalog with existential variables in rule heads. Differently from previous proposals, we focus on subclasses of unions of conjunctive queries (UCQs), rather than on ...
Preference-based inconsistency-tolerant query answering under existential rules
Abstract
Ontology-mediated query answering (OMQA) emerged as a paradigm to enhance querying of data sources with an ontology that encodes background knowledge. In applications involving large amounts of data from multiple data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence

July 2015

4429 pages

ISBN:9781577357384

Editors:
Qiang Yang
Hong Kong University of Science and Technology
,
Michael Wooldridge
University of Oxford

Sponsors

The International Joint Conferences on Artificial Intelligence, Inc. (IJCAI)

Publisher

AAAI Press

Publication History

Published: 25 July 2015

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Malizia EAndre EKoenig SDastani MSukthankar G(2018)More Complexity Results about Reasoning over ( m )CP-netsProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237930(1540-1548)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237930
Martinez M(2017)Knowledge engineering for intelligent decision supportProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3172029(5131-5135)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3172029
Ceylan ILukasiewicz TPeñaloza RTifrea-Marciuska O(2017)Query answering in ontologies under preference rankingsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171777(943-949)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171777
Bellini VAnelli VDi Noia TDi Sciascio EHidasi BKaratzoglou ASar-Shalom ODieleman SShapira BTikk D(2017)Auto-Encoding User Ratings via Knowledge Graphs in Recommendation ScenariosProceedings of the 2nd Workshop on Deep Learning for Recommender Systems10.1145/3125486.3125496(60-66)Online publication date: 27-Aug-2017
https://dl.acm.org/doi/10.1145/3125486.3125496
Borgwardt SFazzinga BLukasiewicz TShrivastava ATifrea-Marciuska O(2016)Preferential query answering in the semantic web with possibilistic networksProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060759(994-1000)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060759

View Options

View options

Media

Figures

Other

Tables

View Table of Contents