1 Search Results for "�imkus, Mantas"


Document
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
  • 1 Calvanese, Diego
  • 1 Ortiz, Magdalena
  • 1 Šimkus, Mantas

  • Refine by Classification

  • Refine by Keyword
  • 1 Description Logics
  • 1 Graph databases
  • 1 Path constraints
  • 1 Static verification

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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