2026-07-21T19:26:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8601 2024-03-06T10:42:27Z ddc:004 open_access

Preserving Constraints with the Stable Chase Carral, David Krötzsch, Markus Marx, Maximilian Ozaki, Ana Rudolph, Sebastian Incidental constraints Tuple-generating dependencies Infinite core chase Universal Model BCQ entailment Conjunctive query answering over databases with constraints – also known as (tuple-generating) dependencies – is considered a central database task. To this end, several versions of a construction called chase have been described. Given a set Sigma of dependencies, it is interesting to ask which constraints not contained in Sigma that are initially satisfied in a given database instance are preserved when computing a chase over Sigma. Such constraints are an example for the more general class of incidental constraints, which when added to Sigma as new dependencies do not affect certain answers and might even speed up query answering. After formally introducing incidental constraints, we show that deciding incidentality is undecidable for tuple-generating dependencies, even in cases for which query entailment is decidable. For dependency sets with a finite universal model, the core chase can be used to decide incidentality. For the infinite case, we propose the stable chase, which generalises the core chase, and study its relation to incidental constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Carral and Markus Krötzsch and Maximilian Marx and Ana Ozaki and Sebastian Rudolph 2018 Is Part Of LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2018.12 urn:nbn:de:0030-drops-86015 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode