License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICLP.2016.11
URN: urn:nbn:de:0030-drops-67411
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6741/
Go to the corresponding OASIcs Volume Portal

Cruz-Filipe, Luís

Grounded Fixpoints and Active Integrity Constraints

pdf-format:
OASIcs-ICLP-2016-11.pdf (0.4 MB)

Abstract

The formalism of active integrity constraints was introduced as a way to specify particular classes of integrity constraints over relational databases together with preferences on how to repair existing inconsistencies. The rule-based syntax of such integrity constraints also provides algorithms for finding such repairs that achieve the best asymptotic complexity.

However, the different semantics that have been proposed for these integrity constraints all exhibit some counter-intuitive examples. In this work, we look at active integrity constraints using ideas from algebraic fixpoint theory. We show how database repairs can be modeled as fixpoints of particular operators on databases, and study how the notion of grounded fixpoint induces a corresponding notion of grounded database repair that captures several natural intuitions, and in particular avoids the problems of previous alternative semantics.

In order to study grounded repairs in their full generality, we need to generalize the notion of grounded fixpoint to non-deterministic operators. We propose such a definition and illustrate its plausibility in the database context.

BibTeX - Entry

@InProceedings{cruzfilipe:OASIcs:2016:6741,
  author =	{Lu{\'i}s Cruz-Filipe},
  title =	{{Grounded Fixpoints and Active Integrity Constraints}},
  booktitle =	{Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016)},
  pages =	{11:1--11:14},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-007-1},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{52},
  editor =	{Manuel Carro and Andy King and Neda Saeedloei and Marina De Vos},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6741},
  URN =		{urn:nbn:de:0030-drops-67411},
  doi =		{10.4230/OASIcs.ICLP.2016.11},
  annote =	{Keywords: grounded fixpoints, active integrity constraints}
}

Keywords: grounded fixpoints, active integrity constraints
Collection: Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016)
Issue Date: 2016
Date of publication: 11.11.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI