Preserving Constraints with the Stable Chase
From International Center for Computational Logic
Preserving Constraints with the Stable Chase
David CarralDavid Carral, Markus KrötzschMarkus Krötzsch, Maximilian MarxMaximilian Marx, Ana OzakiAna Ozaki, Sebastian RudolphSebastian Rudolph
David Carral, Markus Krötzsch, Maximilian Marx, Ana Ozaki, Sebastian Rudolph
Preserving Constraints with the Stable Chase
In Benny Kimelfeld and Yael Amsterdamer, eds., Proceedings of the 21st International Conference on Database Theory (ICDT 2018), volume 98 of Leibniz International Proceedings in Informatics (LIPIcs), 12:1--12:19, March 2018. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Preserving Constraints with the Stable Chase
In Benny Kimelfeld and Yael Amsterdamer, eds., Proceedings of the 21st International Conference on Database Theory (ICDT 2018), volume 98 of Leibniz International Proceedings in Informatics (LIPIcs), 12:1--12:19, March 2018. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
- KurzfassungAbstract
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 some set of dependencies, it is interesting to ask which constraints not contained in such set that are initially satisfied in a given database instance are preserved when computing a chase. Such constraints are an example for the more general class of incidental constraints which when added as new dependencies do not affect the 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 when restricting to classes for which query entailment is decidable. We find that for dependency sets admitting a finite universal model, the core chase can be used to decide incidentality. For the infinite case, we propose the stable chase, which is a generalisation of the core chase, and study its relation to incidental constraints. - Projekt:Project: Cfaed, DIAMOND
- Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems
@inproceedings{CKMOR2018,
author = {David Carral and Markus Kr{\"{o}}tzsch and Maximilian Marx and
Ana Ozaki and Sebastian Rudolph},
title = {Preserving Constraints with the Stable Chase},
editor = {Benny Kimelfeld and Yael Amsterdamer},
booktitle = {Proceedings of the 21st International Conference on Database
Theory (ICDT 2018)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {98},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
year = {2018},
month = {March},
pages = {12:1--12:19},
doi = {10.4230/LIPIcs.ICDT.2018.12}
}