The Impact of Active Domain Predicates on Guarded Existential Rules

• Autorzy: Gottlob G. , Pieris A. , Šimkus M.

Identyfikatory

DOI

10.3233/FI-2018-1660

• Konferencja: Convegno Italiano di Logica Computazionale : CILC 2015 (30th; 01-03.07.2015; University of Genoa, Italy)
• Języki publikacji: EN

Abstrakty

EN

It is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, databases that include designated predicates that hold the active domain, which we call product databases, form a natural notion that deserves our attention. An important issue then is to look at the consequences of product databases for the expressiveness and complexity of central existential rule languages. We focus on guarded-based existential rules, and we investigate the impact of product databases on their expressive power and complexity. We show that the queries expressed via (frontier-)guarded rules gain in expressiveness, and in fact, they have the same expressive power as Datalog. On the other hand, there is no impact on the expressiveness of the queries specified via weakly-(frontier-)guarded rules since they are powerful enough to explicitly compute the predicates needed to access the active domain. We also observe that there is no impact on the complexity of the query languages in question.

Słowa kluczowe

EN

rule-based languages; ontology-mediated queries; conjunctive queries; existential rules; tuple-generating dependencies; guardedness; expressive power; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 159, nr 1/2
• Strony: 123--146
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Gottlob G.

• Department of Computer Science, University of Oxford, Oxford, UK

autor

Pieris A.

• School of Informatics, University of Edinburgh, Edinburgh, UK

autor

Šimkus M.

• Institute of Information Systems, Vienna University of Technology, Vienna, Austria

Bibliografia

• [1] Bienvenu M, ten Cate B, Lutz C, and Wolter F. Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP. ACM Trans. Database Syst., 2014;39(4):33:1-33:44. doi:10.1145/2661643.
• [2] Beeri C, and Vardi MY. The Implication Problem for Data Dependencies. In: ICALP. 1981 pp. 73-85. URL https://doi.org/10.1007/3-540-10843-2_7.
• [3] Calì A, Gottlob G, and Kifer M. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. J. Artif. Intell. Res., 2013;48:115-174. doi:10.1613/jair.3873.
• [4] Baget JF, Leclère M, Mugnier ML, and Salvat E. On rules with existential variables: Walking the decidability line. Artif. Intell., 2011;175(9-10):1620-1654. URL https://doi.org/10.1016/j.artint.2011.03.002.
• [5] Gottlob G, Rudolph S, and Simkus M. Expressiveness of guarded existential rule languages. In: PODS. 2014 pp. 27-38. doi:10.1145/2594538.2594556.
• [6] Arenas M, Gottlob G, and Pieris A. Expressive languages for querying the semantic web. In: PODS. 2014 pp. 14-26. doi:10.1145/2594538.2594555.
• [7] Fagin R, Kolaitis PG, Miller RJ, and Popa L. Data exchange: Semantics and query answering. Theor. Comput. Sci., 2005;336(1):89-124. URL Dataexchange:{S}emanticsandqueryanswering.
• [8] Johnson DS, and Klug AC. Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci., 1984;28(1):167-189. URL https://doi.org/10.1016/0022-0000(84)90081-3.
• [9] Maier D, Mendelzon AO, and Sagiv Y. Testing Implications of Data Dependencies. ACM Trans. Database Syst., 1979;4(4):455-469. doi:10.1145/320107.320115.
• [10] Abiteboul S, Hull R, and Vianu V. Foundations of Databases. Addison-Wesley, 1995. ISBN: 0201537710.
• [11] Andréka H, van Benthem J, and Németi I. Modal Languages and Bounded Fragments of Predicate Logic. J. Philosophical Logic, 1998;27:217-274.
• [12] Grädel E. Decision procedures for guarded logics. In: CADE. 1999. vol. 1632 of LNCS. Springer 1999 pp. 31-51. URL https://doi.org/10.1007/3-540-48660-7_3.
• [13] Bárány V, Benedikt M, and Balder ten Cate. Rewriting Guarded Negation Queries. In: MFCS. 2013. vol. 8087 of LNCS. Springer 2013 pp. 98-110. URL https://doi.org/10.1007/978-3-642-40313-2_11.
• [14] Baget JF, Mugnier ML, Rudolph S, and Thomazo M. Walking the Complexity Lines for Generalized Guarded Existential Rules. In: IJCAI. 2011 pp. 712-717. http://ijcai-11.iiia.csic.es.
• [15] Motik B, Sattler U, and Studer R. Query Answering for OWL-DL with rules. J. Web Sem., 2005;3(1):41-60. URL https://doi.org/10.1016/j.websem.2005.05.001.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).