2 Search Results for "Simkus, Mantas"

Document
DOI: 10.4230/LIPIcs.ICDT.2018.4
Rewriting Guarded Existential Rules into Small Datalog Programs

Authors: Shqiponja Ahmetaj, Magdalena Ortiz, and Mantas Simkus

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)

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 polynomially-sized (disjunctive) Datalog program 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 differently 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 if the maximal number of variables in the (disjunctive) TGDs is bounded by a constant.
Cite as

Shqiponja Ahmetaj, Magdalena Ortiz, and Mantas Simkus. Rewriting Guarded Existential Rules into Small Datalog Programs. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ahmetaj_et_al:LIPIcs.ICDT.2018.4,
  author =	{Ahmetaj, Shqiponja and Ortiz, Magdalena and Simkus, Mantas},
  title =	{{Rewriting Guarded Existential Rules into Small Datalog Programs}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.4},
  URN =		{urn:nbn:de:0030-drops-85950},
  doi =		{10.4230/LIPIcs.ICDT.2018.4},
  annote =	{Keywords: Existential rules, Expressiveness, Descriptive Complexity, Query Rewriting}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.15
Verification of Evolving Graph-structured Data under Expressive Path Constraints

Authors: Diego Calvanese, Magdalena Ortiz, and Mantas Šimkus

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
Integrity constraints play a central role in databases and, among other applications, are fundamental for preserving data integrity when databases evolve as a result of operations manipulating the data. In this context, an important task is that of static verification, which consists in deciding whether a given set of constraints is preserved after the execution of a given sequence of operations, for every possible database satisfying the initial constraints. In this paper, we consider constraints over graph-structured data formulated in an expressive Description Logic (DL) that allows for regular expressions over binary relations and their inverses, generalizing many of the well-known path constraint languages proposed for semi-structured data in the last two decades. In this setting, we study the problem of static verification, for operations expressed in a simple yet flexible language built from additions and deletions of complex DL expressions. We establish undecidability of the general setting, and identify suitable restricted fragments for which we obtain tight complexity results, building on techniques developed in our previous work for simpler DLs. As a by-product, we obtain new (un)decidability results for the implication problem of path constraints, and improve previous upper bounds on the complexity of the problem.
Cite as

Diego Calvanese, Magdalena Ortiz, and Mantas Šimkus. Verification of Evolving Graph-structured Data under Expressive Path Constraints. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{calvanese_et_al:LIPIcs.ICDT.2016.15,
  author =	{Calvanese, Diego and Ortiz, Magdalena and \v{S}imkus, Mantas},
  title =	{{Verification of Evolving Graph-structured Data under Expressive Path Constraints}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.15},
  URN =		{urn:nbn:de:0030-drops-57843},
  doi =		{10.4230/LIPIcs.ICDT.2016.15},
  annote =	{Keywords: Path constraints, Description Logics, Graph databases, Static verification}
}
  • Refine by Author
  • 2 Ortiz, Magdalena
  • 1 Ahmetaj, Shqiponja
  • 1 Calvanese, Diego
  • 1 Simkus, Mantas
  • 1 Šimkus, Mantas

  • Refine by Classification

  • Refine by Keyword
  • 1 Description Logics
  • 1 Descriptive Complexity
  • 1 Existential rules
  • 1 Expressiveness
  • 1 Graph databases
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact