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.
%0 Conference Paper
%1 marx2022tuplegenerating
%A Marx, Maximilian
%A Krötzsch, Markus
%B Proceedings of the 25th International Conference on Database Theory (ICDT 2022)
%D 2022
%E Olteanu, Dan
%E Vortmeier, Nils
%I Schloss Dagstuhl - Leibniz-Zentrum für Informatik
%K topic_graph topic_knowledge xack
%P 13:1–13:20
%R 10.4230/LIPIcs.ICDT.2022.13
%T Tuple-Generating Dependencies Capture Complex Values
%V 220
%X 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.
%@ 9783959772235
@inproceedings{marx2022tuplegenerating,
abstract = {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.},
added-at = {2024-11-28T16:27:18.000+0100},
author = {Marx, Maximilian and Krötzsch, Markus},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2bc948a470df0136c0296f5cf5ac973df/scadsfct},
booktitle = {Proceedings of the 25th International Conference on Database Theory (ICDT 2022)},
day = 1,
doi = {10.4230/LIPIcs.ICDT.2022.13},
editor = {Olteanu, Dan and Vortmeier, Nils},
interhash = {149eb70c90e9d1f5002e4ed8c068e59d},
intrahash = {bc948a470df0136c0296f5cf5ac973df},
isbn = {9783959772235},
keywords = {topic_graph topic_knowledge xack},
language = {English},
month = mar,
note = {Publisher Copyright: {\textcopyright} Maximilian Marx and Markus Kr{\"o}tzsch;},
pages = {13:1–13:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik},
series = {25th International Conference on Database Theory (ICDT 2022) ; Vol. 220},
timestamp = {2025-08-23T23:50:38.000+0200},
title = {Tuple-Generating Dependencies Capture Complex Values},
volume = 220,
year = 2022
}
