Tuple-Generating Dependencies Capture Complex Values

Maximilian MarxMaximilian Marx, Markus KrötzschMarkus Krötzsch

Download

Maximilian Marx, Markus Krötzsch
Tuple-Generating Dependencies Capture Complex Values
In Dan Olteanu, Nils Vortmeier, eds., Proceedings of the 22nd International Conference on Database Theory (ICDT 2022), volume 220 of LIPIcs, 19:1--19:20, to appear. 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 22nd 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     = {19:1--19:20}
}