Tuple-Generating Dependencies Capture Complex Values
| Autor: | Marx, Maximilian, Krötzsch, Markus |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Datalog
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Theory of computation → Constraint and logic programming InformationSystems_DATABASEMANAGEMENT Theory of computation → Logic and databases terminating standard chase Theory of computation → Complexity theory and logic existential rules complexity |
| DOI: | 10.4230/lipics.icdt.2022.13 |
| Popis: | 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. LIPIcs, Vol. 220, 25th International Conference on Database Theory (ICDT 2022), pages 13:1-13:20 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|