Tuple-Generating Dependencies Capture Complex Values

Maximilian MarxMaximilian Marx, Markus KrötzschMarkus Krötzsch

ISBN: 978-3-95977-223-5
ISSN: 1868-8969
Download
Slides
DOI Link

Maximilian Marx, Markus Krötzsch
Tuple-Generating Dependencies Capture Complex Values
In Dan Olteanu, Nils Vortmeier, eds., Proceedings of the 25th International Conference on Database Theory (ICDT 2022), volume 220 of LIPIcs, 13:1--13:20, March 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Details
Bibtex

KurzfassungAbstract
We formalise a variant of Datalog that allows complex values constructed by nesting elements of the input database in sets and tuples. We study its complexity and give a translation into sets of tuple-generating dependencies (TGDs) for which the standard chase terminates on any input database. We identify a fragment for which reasoning is tractable. As membership is undecidable for this fragment, we develop decidable sufficient conditions.
Projekt:Project: CPEC, ScaDS.AI, Cfaed
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{MK2022,
  author    = {Maximilian Marx and Markus Kr{\"{o}}tzsch},
  title     = {Tuple-Generating Dependencies Capture Complex Values},
  editor    = {Dan Olteanu and Nils Vortmeier},
  booktitle = {Proceedings of the 25th International Conference on Database
               Theory (ICDT 2022)},
  series    = {LIPIcs},
  volume    = {220},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2022},
  month     = {March},
  pages     = {13:1--13:20},
  doi       = {10.4230/LIPIcs.ICDT.2022.13}
}