More Web Proxy on the site http://driver.im/

research-article

Datalog rewritability and data complexity of ALCHOIQ with closed predicates

Authors:

Sanja Lukumbuzya,

Magdalena Ortiz,

Mantas ŠimkusAuthors Info & Claims

Volume 330, Issue C

https://doi.org/10.1016/j.artint.2024.104099

Published: 02 July 2024 Publication History

Abstract

We study the relative expressiveness of ontology-mediated queries (OMQs) formulated in the expressive Description Logic ALCHOIQ extended with closed predicates. In particular, we present a polynomial time translation from OMQs into Datalog with negation under the stable model semantics, the formalism that underlies Answer Set Programming. This is a novel and non-trivial result: the considered OMQs are not only non-monotonic, but also feature a tricky combination of nominals, inverse roles, and counting. We start with atomic queries and then lift our approach to a large class of first-order queries where quantification is “guarded” by closed predicates. Our translation is based on a characterization of the query answering problem via integer programming, and a specially crafted program in Datalog with negation that finds solutions to dynamically generated systems of integer inequalities. As an important by-product of our translation we get that the query answering problem is co-NP-complete in data complexity for the considered class of OMQs. Thus, answering these OMQs in the presence of closed predicates is not harder than answering them in the standard setting. This is not obvious as closed predicates are known to increase data complexity for some existing ontology languages.

References

[1]

F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduction to Description Logic, Cambridge University Press, 2017,.

[2]

I. Horrocks, Ontologies and the semantic web, Commun. ACM 51 (12) (2008) 58–67,. http://doi.acm.org/10.1145/1409360.1409377.

Digital Library

[3]

OWL Working Group, W. (27 October 2009): OWL 2 web ontology language: document overview. W3C Recommendation, available at http://www.w3.org/TR/owl2-overview/.

[4]

A. Poggi, D. Lembo, D. Calvanese, G.D. Giacomo, M. Lenzerini, R. Rosati, Linking data to ontologies, J. Data Semant. 10 (2008) 133–173,.

[5]

A. Borgida, On the relative expressiveness of description logics and predicate logics, Artif. Intell. 82 (1–2) (1996) 353–367.

[6]

F.M. Donini, D. Nardi, R. Rosati, Description logics of minimal knowledge and negation as failure, ACM Trans. Comput. Log. 3 (2) (2002) 177–225,.

Digital Library

[7]

T. Eiter, G. Ianni, T. Lukasiewicz, R. Schindlauer, H. Tompits, Combining answer set programming with description logics for the semantic web, Artif. Intell. 172 (12–13) (2008) 1495,.

Digital Library

[8]

P.A. Bonatti, C. Lutz, F. Wolter, The complexity of circumscription in description logics, J. Artif. Intell. Res. 35 (2009) 717–773.

[9]

K. Sengupta, A.A. Krisnadhi, P. Hitzler, Local closed world semantics: grounded circumscription for OWL, in: Proc. of ISWC 2011, Springer, 2011,.

[10]

E. Franconi, Y.A. Ibáñez-García, I. Seylan, Query answering with dboxes is hard, Electron. Notes Theor. Comput. Sci. 278 (2011) 71–84,.

Digital Library

[11]

C. Lutz, I. Seylan, F. Wolter, Ontology-based data access with closed predicates is inherently intractable (sometimes), in: Proc. of IJCAI 2013, IJCAI/AAAI, 2013, pp. 1024–1030. http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6870.

[12]

C. Lutz, I. Seylan, F. Wolter, The data complexity of ontology-mediated queries with closed predicates, Log. Methods Comput. Sci. 15 (3) (2019),.

Digital Library

[13]

S. Tobies, The complexity of reasoning with cardinality restrictions and nominals in expressive description logics, J. Artif. Intell. Res. 12 (2000) 199–217.

[14]

I. Seylan, E. Franconi, J. de Bruijn, Effective query rewriting with ontologies over dboxes, in: Proc. of IJCAI 2009, 2009, pp. 923–925. http://ijcai.org/papers09/Papers/IJCAI09-157.pdf.

[15]

M. Benedikt, P. Bourhis, B. ten Cate, G. Puppis, Querying visible and invisible information, in: Proc. of LICS 2016, ACM, 2016, pp. 297–306,. http://doi.acm.org/10.1145/2933575.2935306.

Digital Library

[16]

B. Glimm, Y. Kazakov, C. Lutz, Status QIO: an update, in: R. Rosati, S. Rudolph, M. Zakharyaschev (Eds.), Proc. of the 24th International Workshop on Description Logics (DL 2011), in: CEUR Workshop Proceedings, vol. 745, Barcelona, Spain, July 13–16, 2011, CEUR-WS.org, 2011, http://ceur-ws.org/Vol-745/paper_44.pdf.

[17]

S. Rudolph, B. Glimm, Nominals, inverses, counting, and conjunctive queries or: why infinity is your friend!, J. Artif. Intell. Res. 39 (2010) 429–481,.

[18]

T. Gogacz, S. Lukumbuzya, M. Ortiz, M. Simkus, Datalog rewritability and data complexity of ALCHOIF with closed predicates, in: D. Calvanese, E. Erdem, M. Thielscher (Eds.), Proc. of KR 2020, 2020, pp. 434–444,.

[19]

S. Lukumbuzya, M. Simkus, Bounded predicates in description logics with counting, in: Z. Zhou (Ed.), Proc. of IJCAI 2021, ijcai.org, 2021, pp. 1966–1972,.

[20]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Data complexity of query answering in description logics, in: Proc. of KR 2006, AAAI Press, 2006, pp. 260–270. http://www.aaai.org/Library/KR/2006/kr06-028.php.

[21]

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

Digital Library

[22]

D. Calvanese, G.D. Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Data complexity of query answering in description logics, Artif. Intell. 195 (2013) 335–360,.

Digital Library

[23]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodriguez-Muro, R. Rosati, M. Ruzzi, D.F. Savo, The MASTRO system for ontology-based data access, Semant. Web 2 (1) (2011) 43–53,.

[24]

M. Rodriguez-Muro, R. Kontchakov, M. Zakharyaschev, Ontology-based data access: ontop of databases, in: Proc. ISWC 2013, in: LNCS, vol. 8218, Springer, 2013, pp. 558–573,.

Digital Library

[25]

G. Gottlob, T. Schwentick, Rewriting ontological queries into small nonrecursive datalog programs, in: Proc. of KR 2012, AAAI Press, 2012, http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4510.

[26]

G. Gottlob, S. Kikot, R. Kontchakov, V.V. Podolskii, T. Schwentick, M. Zakharyaschev, The price of query rewriting in ontology-based data access, Artif. Intell. 213 (2014) 42–59,.

Digital Library

[27]

C. Lutz, I. Seylan, F. Wolter, Ontology-mediated queries with closed predicates, in: Proc. of IJCAI 2015, AAAI Press, 2015, pp. 3120–3126. http://ijcai.org/papers15/Abstracts/IJCAI15-440.html.

[28]

U. Hustadt, B. Motik, U. Sattler, Reasoning in description logics by a reduction to disjunctive datalog, J. Autom. Reason. 39 (3) (2007) 351–384,.

Digital Library

[29]

T. Eiter, M. Ortiz, M. Šimkus, T. Tran, G. Xiao, Query rewriting for Horn-SHIQ plus rules, in: Proc. of AAAI 2012, AAAI Press, 2012, http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4931.

[30]

M. Kaminski, Y. Nenov, B.C. Grau, Datalog rewritability of disjunctive datalog programs and non-Horn ontologies, Artif. Intell. 236 (2016) 90–118,.

Digital Library

[31]

M. Bienvenu, B. ten Cate, C. Lutz, F. Wolter, Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP, ACM Trans. Database Syst. 39 (4) (2014) 33:1–33:44,. http://doi.acm.org/10.1145/2661643.

Digital Library

[32]

M. Ortiz, S. Rudolph, M. Šimkus, Worst-case optimal reasoning for the Horn-DL fragments of OWL 1 and 2, in: Proc. of KR 2010, AAAI Press, 2010, http://aaai.org/ocs/index.php/KR/KR2010/paper/view/1296.

[33]

S. Ahmetaj, M. Ortiz, M. Simkus, Polynomial rewritings from expressive description logics with closed predicates to variants of datalog, Artif. Intell. 280 (2020),.

Digital Library

[34]

D. Calvanese, M. Lenzerini, D. Nardi, A unified framework for class-based representation formalisms, in: Principles of Knowledge Representation and Reasoning, Elsevier, 1994, pp. 109–120.

[35]

D. Calvanese, Finite model reasoning in description logics, in: L.C. Aiello, J. Doyle, S.C. Shapiro (Eds.), Proc. of KR 1996, Morgan Kaufmann, 1996, pp. 292–303.

[36]

C. Lutz, U. Sattler, L. Tendera, The complexity of finite model reasoning in description logics, Inf. Comput. 199 (1–2) (2005) 132–171,.

[37]

T. Gogacz, V. Gutiérrez-Basulto, Y. Ibáñez-García, F. Murlak, M. Ortiz, M. Simkus, Ontology focusing: knowledge-enriched databases on demand, in: G.D. Giacomo, A. Catalá, B. Dilkina, M. Milano, S. Barro, A. Bugarín, J. Lang (Eds.), Proc. of ECAI 2020, in: Frontiers in Artificial Intelligence and Applications, vol. 325, IOS Press, 2020, pp. 745–752,.

[38]

I. Pratt-Hartmann, Complexity of the two-variable fragment with counting quantifiers, J. Log. Lang. Inf. 14 (3) (2005) 369–395,.

Digital Library

[39]

M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: Proc. of ICLP/SLP 1988, MIT Press, 1988, pp. 1070–1080.

[40]

T. Eiter, G. Gottlob, H. Mannila, Disjunctive datalog, ACM Trans. Database Syst. 22 (3) (1997) 364–418.

[41]

E. Dantsin, T. Eiter, G. Gottlob, A. Voronkov, Complexity and expressive power of logic programming, ACM Comput. Surv. 33 (3) (2001) 374–425.

Digital Library

[42]

C.H. Papadimitriou, On the complexity of integer programming, J. ACM 28 (4) (1981) 765–768.

[43]

B. Motik, U. Sattler, R. Studer, Query answering for OWL-DL with rules, in: S.A. McIlraith, D. Plexousakis, F. van Harmelen (Eds.), The Semantic Web – ISWC 2004, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 549–563.

[44]

M. Krötzsch, F. Maier, A. Krisnadhi, P. Hitzler, A better uncle for OWL: nominal schemas for integrating rules and ontologies, in: S. Srinivasan, K. Ramamritham, A. Kumar, M.P. Ravindra, E. Bertino, R. Kumar (Eds.), Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 - April 1, 2011, ACM, 2011, pp. 645–654,.

Digital Library

[45]

M. Krötzsch, S. Rudolph, Nominal schemas in description logics: complexities clarified, in: C. Baral, G.D. Giacomo, T. Eiter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20–24, 2014, AAAI Press, 2014, http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/8027.

[46]

G. Amendola, N. Leone, M. Manna, P. Veltri, Enhancing existential rules by closed-world variables, in: J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13–19, 2018, Stockholm, Sweden, ijcai.org, 2018, pp. 1676–1682,.

[47]

S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995, http://webdam.inria.fr/Alice/.

Digital Library

[48]

K.R. Apt, H.A. Blair, A. Walker, Chapter 2 - towards a theory of declarative knowledge, in: J. Minker (Ed.), Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, 1988, pp. 89–148,. https://www.sciencedirect.com/science/article/pii/B9780934613408500063.

[49]

A. Schaerf, On the complexity of the instance checking problem in concept languages with existential quantification, J. Intell. Inf. Syst. 2 (3) (1993) 265–278,.

Digital Library

[50]

V. Gutiérrez-Basulto, Y. Ibáñez-García, R. Kontchakov, E.V. Kostylev, Queries with negation and inequalities over lightweight ontologies, J. Web Semant. 35 (2015) 184–202.

Recommendations

Polynomial rewritings from expressive Description Logics with closed predicates to variants of Datalog
Abstract
In many scenarios, complete and incomplete information coexist. For this reason, the knowledge representation and database communities have long shown interest in simultaneously supporting the closed- and the open-world views when ...
Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies

We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i.e., one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be ...
Query containment for data integration systems
Special issue on PODS 2000

The problem of query containment is fundamental to many aspects of database systems, including query optimization, determining independence of queries from updates, and rewriting queries using views. In the data-integration framework, however, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 330, Issue C

May 2024

293 pages

Issue’s Table of Contents

The Authors.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 02 July 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

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

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents