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 6246f32b0b8d44e1aa64cf354ac9cd50
%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_knowledge topic_graph Datalog, FIS_scads chase complexity, existential rules, standard terminating
%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{6246f32b0b8d44e1aa64cf354ac9cd50,
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{\"o}tzsch, Markus},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/29ed128645ac21d5455b70551b54b8f0c/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 = {1de03dba6c72321c0ff5b20922c09a84},
intrahash = {9ed128645ac21d5455b70551b54b8f0c},
isbn = {9783959772235},
keywords = {topic_knowledge topic_graph Datalog, FIS_scads chase complexity, existential rules, standard terminating},
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 = {2024-11-28T17:41:09.000+0100},
title = {Tuple-Generating Dependencies Capture Complex Values},
volume = 220,
year = 2022
}
