Tuple-Generating Dependencies Capture Complex Values
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
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.
Details
Original language | English |
---|---|
Title of host publication | Proceedings of the 25th International Conference on Database Theory (ICDT 2022) |
Editors | Dan Olteanu, Nils Vortmeier |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 13:1–13:20 |
Number of pages | 20 |
Volume | 220 |
ISBN (electronic) | 9783959772235 |
ISBN (print) | 9783959772235 |
Publication status | Published - 1 Mar 2022 |
Peer-reviewed | Yes |
Publication series
Series | 25th International Conference on Database Theory (ICDT 2022) ; Vol. 220 |
---|---|
Volume | 220 |
ISSN | 1868-8969 |
External IDs
Scopus | 85127929230 |
---|---|
Mendeley | bea557ec-2cfd-3f71-9988-765af623b813 |
dblp | conf/icdt/0001K22 |
Keywords
ASJC Scopus subject areas
Keywords
- Datalog, complexity, existential rules, terminating standard chase