Containment for Rule-Based Ontology-Mediated Queries

被引：4

作者：

Barcelo, Pablo ^{[1
]}

Berger, Gerald ^{[2
]}

Pieris, Andreas ^{[3
]}

机构：

[1] Univ Chile, MI Fdn Res Data & DCC, Santiago, Chile

[2] TU Wien, Inst Log & Computat, Vienna, Austria

[3] Univ Edinburgh, Sch Informat, Edinburgh, Midlothian, Scotland

来源：

PODS'18: PROCEEDINGS OF THE 37TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS | 2018年

基金：

奥地利科学基金会; 英国工程与自然科学研究理事会;

关键词：

DATALOG; EQUIVALENCE; IMPACT;

D O I：

10.1145/3196959.3196963

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Many efforts have been dedicated to identifying restrictions on ontologies expressed as tuple-generating dependencies (tgds), a.k.a. existential rules, that lead to the decidability of answering ontology-mediated queries (OMQs). This has given rise to three families of formalisms: guarded, non-recursive, and sticky sets of tgds. We study the containment problem for OMQs expressed in such formalisms, which is a key ingredient for solving static analysis tasks associated with them. Our main contribution is the development of specially tailored techniques for OMQ containment under the classes of tgds stated above. This enables us to obtain sharp complexity bounds for the problems at hand.

引用

页码：267 / 279

页数：13

共 35 条

[21]

Eiter T, 2016, FIFTEENTH INTERNATIONAL CONFERENCE ON THE PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING, P359

[22] Data exchange: semantics and query answering [J].