%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 }