<div class="csl-bib-body">
<div class="csl-entry">Ahmetaj, S., Ortiz de la Fuente, M. M., & Simkus, M. (2018). Rewriting Guarded Existential Rules into Small Datalog Programs. In B. Kimelfeld & Y. Amsterdamer (Eds.), <i>21st International Conference on Database Theory, {ICDT} 2018</i> (pp. 1–24). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ICDT.2018.4</div>
</div>
-
dc.identifier.isbn
978-3-89318-078-3
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/57581
-
dc.description.abstract
The goal of this paper is to understand the relative expressiveness of the query language in which queries are specified by a set of guarded (disjunctive) tuple-generating dependencies (TGDs) and an output (or `answer´) predicate. Our main result is to show that every such query can be translated into a (disjunctive) Datalog program, which has polynomial size if the maximal number of variables in the (disjunctive) TGDs is bounded by a constant. To overcome the challenge that Datalog has no direct means to express the existential quantification present in TGDs, we define a two-player game that characterizes the satisfaction of the dependencies, and design a Datalog query that can decide the existence of a winning strategy for the game. For guarded disjunctive TGDs, we can obtain Datalog rules with disjunction in the heads. However, the use of disjunction is limited, and the resulting rules fall into a fragment that can be evaluated in deterministic single exponential time. We proceed quite di˙erently for the case when the TGDs are not disjunctive and we show that we can obtain a plain Datalog query. Notably, unlike previous translations for related fragments, our translation requires only polynomial time under the reasonable assumption that the maximal number of variables in the (disjunctive) TGDs is bounded by a constant.
en
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
Query Rewriting
-
dc.subject
Existential rules
-
dc.subject
Expressiveness
-
dc.title
Rewriting Guarded Existential Rules into Small Datalog Programs
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
21st International Conference on Database Theory, {ICDT} 2018
-
dc.relation.isbn
978-3-95977-063-7
-
dc.relation.issn
1868-8969
-
dc.description.startpage
1
-
dc.description.endpage
24
-
dc.type.category
Full-Paper Contribution
-
dc.publisher.place
98
-
tuw.booktitle
21st International Conference on Database Theory, {ICDT} 2018
-
tuw.container.volume
98
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
tuw.relation.publisherplace
Dagstuhl
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publisher.doi
10.4230/LIPIcs.ICDT.2018.4
-
dc.description.numberOfPages
24
-
tuw.event.name
Edbt / Icdt 2018
-
tuw.event.startdate
26-03-2018
-
tuw.event.enddate
29-03-2018
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Wien
-
tuw.event.country
AT
-
tuw.event.presenter
Ahmetaj, Shqiponja
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.facultyfocus
Logic and Computation (LC)
de
wb.facultyfocus
Logic and Computation (LC)
en
wb.facultyfocus.faculty
E180
-
wb.presentation.type
science to science/art to art
-
item.cerifentitytype
Publications
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cf
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cf
-
item.fulltext
no Fulltext
-
item.grantfulltext
none
-
item.openairetype
Konferenzbeitrag
-
item.openairetype
Inproceedings
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence