PaperlayerView exact revision on arXiv

Source-linked AI summary

Prioritized Repairing and Consistent Query Answering in Relational Databases

Slawomir Staworko, Jan Chomicki, Jerzy Marcinkowski

arXiv:0908.0464v3cs.DB

TL;DR

Integrity violations can make query answers misleading, while users may prefer particular ways of resolving conflicts. The paper defines preferred repairs and three optimality families, then analyzes their algorithms and complexity. Complexity varies by family, with a tractable case for a restricted query and constraint setting.

  • Problem

    Integrity violations may make query answers meaningless or misleading, and users can have preferences about how conflicts should be resolved.

    Source: §1 · pp. 2–3

  • Method

    The paper extends repairs and consistent query answering with user preferences, defining preferred repairs through global, Pareto, and completion optimality.

    Source: §1 · pp. 3, 6

  • Results

    Global-optimal preferred consistent query answering is Πp2-complete, while Pareto- and completion-optimal preferred consistent query answering are coNP-complete; all three are in PTIME for quantifier-free ground queries with one functional dependency per relation.

    Source: §1 · pp. 5–6

  • Takeaways & Limitations

    The framework supplies sound and complete repairing algorithms for each family and identifies a tractable query-and-constraint case shared by all three.

    Source: §1 · p. 6

    The paper considers only families of preferred repairs satisfying conservativeness property P5.

    Source: P5 Conservativeness · p. 14

Abstract

from arXiv · show

A consistent query answer in an inconsistent database is an answer obtained in every (minimal) repair. The repairs are obtained by resolving all conflicts in all possible ways. Often, however, the user is able to provide a preference on how conflicts should be resolved. We investigate here the framework of preferred consistent query answers, in which user preferences are used to narrow down the set of repairs to a set of preferred repairs. We axiomatize desirable properties of preferred repairs. We present three different families of preferred repairs and study their mutual relationships. Finally, we investigate the complexity of preferred repairing and computing preferred consistent query answers.

1 Introduction

Integrity violations can make query answers misleading, and ordinary consistent answers consider every repair even when users have preferences. The paper defines preferred repairs, studies three ways to select them, and analyzes their computational complexity.

1 Introduction

  • The framework addresses misleading answers from integrity violations and the drawback that ordinary consistent answers consider all possible conflict resolutions.Repairs are minimally different consistent databases, and the framework does not physically remove facts.Source: §1 · pp. 2–3
  • User preferences narrow all repairs to preferred repairs, and answers present in every preferred repair are preferred consistent query answers.The introduction’s example yields false as the preferred consistent answer to Q0.Source: §1 · p. 3
  • The introduction notes that one conflict’s resolution can affect the available resolutions for another, allowing more than one way to select preferred repairs.Source: §1 · p. 3
  • The paper axiomatizes desirable properties and defines global-, Pareto-, and completion-optimal repairs, which differ in how they compare preference compliance.Global optimality requires each replaced fact to be matched by a more preferred fact; Pareto optimality requires every replacement fact to be preferred over every removed fact; completion optimality extends preferences to a total preference.Source: §1 · pp. 4–5
  • Each family has a sound and complete repairing algorithm; pre-orders characterize the globally and Pareto optimal repairs, while the corresponding order for completion optimality remains open.The algorithms produce repairs in their respective families and can construct every repair in those families.Source: §1 · p. 5
  • Global-optimal preferred consistent query answering is Πp2-complete and preferred repair checking is coNP-complete; Pareto optimality lowers these to coNP-complete and LOGSPACE, respectively.For completion optimality, preferred consistent query answering is coNP-complete and preferred repair checking is in PTIME; whether the latter is PTIME-complete or in LOGSPACE is open.Source: §1 · pp. 5–6
  • For quantifier-free ground queries with one functional dependency per relation, preferred consistent query answering is in PTIME for all three families.Source: §1 · p. 6
  • The paper extends earlier work to denial constraints, supplies sound and complete algorithms for every family, and identifies LOGSPACE preferred repair checking for one family.The LOGSPACE result offers a possibility of parallel implementation for that decision problem.Source: §1 · p. 6

2 Preliminaries

The preliminaries establish the database, constraint, query, and repair notions used throughout the paper. They also describe conflict-based representations of repairs and the data-complexity classes used in the analysis.

2.1 Integrity constraints

  • Denial constraints are the constraint class considered, include functional dependencies, and determine consistency through satisfaction of the constraints.Source: §2.1 · pp. 7–8

2.2 Queries

  • Queries are closed formulas with Boolean answers: an instance answers true exactly when it satisfies the query.Source: §2.2 · p. 8

2.3 Repairing

  • Repairs are maximal consistent subsets of the original instance, and the conflict hypergraph represents them through maximal independent sets.With denial constraints, repairs are obtained by deleting facts; a maximal independent set of the conflict hypergraph is exactly a repair.Source: §2.3 · pp. 8–9
  • A greedy procedure scans facts in an order, adding each when it preserves consistency; it is sound and can produce every repair under a suitable ordering.Source: §2.3 · pp. 10–11

2.4 Complexity classes

  • The complexity classes are used to measure data complexity, expressed in terms of database size.The section lists LOGSPACE, PTIME, coNP, and Πp 2.Source: §2.4 · p. 11

3 Conflict resolution preferences

The section represents user preferences as acyclic priorities between conflicting facts. These priorities guide preferred conflict resolution and can be visualized by orienting edges in a conflict graph.

3 Conflict resolution preferences

  • A priority is an acyclic relation on neighboring conflicting facts, indicating which fact the user prefers to keep when resolving a conflict.Cycles are excluded because they can make the choice ambiguous or impossible.Source: §3 · p. 11
  • A prioritized conflict graph adds directed edges for priorities, with an edge indicating which of its conflicting facts is preferred.Source: §3 · p. 12, Figure 3 · p. 12
  • A priority is total exactly when every pair of facts in each conflict is ordered in one direction or the other.Source: §3 · p. 12

3.1 Preferred repairs and consistent query answers

The paper defines preferred repairs as a family of instances selected for an input database, constraints, and priority. Preferred consistent query answers hold across that selected family, recovering ordinary consistent answers when the family is all repairs.

3.1 Preferred repairs and consistent query answers

  • A family of preferred repairs maps an instance, denial constraints, and a priority to a set of database instances.Source: §3.1 · p. 13
  • A preferred consistent query answer is true or false when that answer holds in every instance in the selected preferred-repair family.Source: §3.1 · p. 13
  • Taking the family of all repairs recovers the original notion of a consistent query answer.Source: §3.1 · p. 13

3.2 Desirable properties of preferred repairs

The section introduces desirable properties for arbitrary families of preferred repairs, to be considered for arbitrary instances and denial-constraint sets.

3.2 Desirable properties of preferred repairs

  • The desirable properties are intended to apply to any instance and any set of denial constraints.Source: §3.2 · p. 13

P1 Non-emptiness

The preferred-repair framework requires a nonempty set of preferred repairs for every preference. Extending a preference is intended to narrow that set as knowledge improves.

P1 Non-emptiness

  • For every preference, the preferred-repair set must remain nonempty, so preferred answers are not defined over an empty set.Source: P1 Non-emptiness · p. 13

P2 Monotonicity

  • Extending a preference is described as improving knowledge of the real world, which should yield finer preferred answers.Source: P2 Monotonicity · p. 14
  • A more extended preference should only narrow the set of preferred repairs.Source: P2 Monotonicity · p. 14

P3 Non-discrimination

The criteria require that preferences exclude no repairs when none are given, and that total preferences select a unique preferred repair. Together, monotonicity and non-discrimination keep preferred repairs within the set of ordinary repairs.

P3 Non-discrimination

P4 Categoricity

P5 Conservativeness

  • Monotonicity and non-discrimination together ensure preferred repairs are a subset of all repairs.The paper also states that a consistent instance has only itself as a preferred repair under P1 and P5.Source: P5 Conservativeness · p. 14

3.3 Data complexity

The section formulates two preferred-repair decision problems for data-complexity analysis and treats the priority relation as part of the input.

3.3 Data complexity

  • The priority relation is treated as input because its size is quadratic in the database instance.Source: §3.3 · p. 14
  • X-preferred repair checking is formulated as a data-complexity decision problem.Source: §3.3 · p. 14
  • X-preferred consistent query answering is formulated as a second data-complexity decision problem.Source: §3.3 · p. 14

4 Globally-optimal repairs

This section defines and characterizes globally-optimal repairs, establishes that they satisfy P1–P4, and gives a construction with exponential-time and iteration bounds. It also studies preferred-repair checking and consistent query answering through quantified-formula reductions and repair-chain encodings, including a coNP-hardness result for BG_F.

4 Globally-optimal repairs

  • Globally-optimal repairs are consistent repairs that admit no fact replacement improving priority compliance.The family selects all such repairs; the replacement set must be more preferred than the facts it replaces.Source: §4 · p. 15
  • A repair is globally optimal exactly when it is G-maximal; acyclicity of the priority implies acyclicity of the induced G relation.The characterization also links failure of global optimality to the existence of a repair witnessing an improving replacement.Source: §4 · p. 15
  • The globally-optimal repair family satisfies properties P1–P4.The proof uses acyclicity of the induced G relation and the definition of global optimality; the total-priority case establishes uniqueness.Source: §4 · p. 16
  • Algorithm 2 soundly and completely constructs globally-optimal repairs in exponential time.It starts from an arbitrary repair and iteratively replaces facts with a more preferred subset while preserving consistency, then extends the result to a repair.Source: §4 · pp. 16–17
  • Algorithm 2 may require exponentially many iterations, and G-preferred repair checking is coNP-complete, ruling out tractability unless P = NP.The exponential-length chain construction emulates an n-bit binary counter.Source: §4 · pp. 17–18

Globally-optimal repairs

  • The constructed G-chain represents successive natural numbers, including carry-propagation repairs, and the algorithm may traverse its full length.In this example, however, the globally optimal repair may be reached in one main-loop iteration.Source: §4 · pp. 18–20
  • G-preferred repair checking is coNP-complete, and G-preferred consistent query answering is Π_2^p-complete.The section gives the upper bounds and states that they are tight, with hardness for a set of four functional dependencies and an atomic query.Source: §4 · p. 20
  • The hardness reduction makes true a G-preferred consistent answer exactly when the quantified formula is valid.It partitions repairs into classes representing existential and universal valuations, with global dominance corresponding to satisfaction of the matrix formula.Source: §4 · pp. 21–22
  • Strict universal-variable repairs are exactly the G-maximal universal-variable repairs.Strict repairs correspond one-to-one with total valuations of universal variables, allowing non-strict repairs to be excluded from consideration.Source: §4 · pp. 22–23

4 Globally-optimal repairs

  • For any total valuation V, the constructed repair I_r[V] exists exactly when V satisfies the formula’s existential part.The lemma states the equivalence between I_r[V] and V satisfying the quantified formula.Source: §4 · p. 23
  • The section characterizes validity of QBF Ψ first through strict repairs and then, more generally, through all repairs.Corollary 1 gives a condition over strict repairs; Corollary 2 extends the characterization to any repair.Source: §4 · p. 24
  • The reduction is polynomial-time and establishes coNP-hardness of BG_F using the complement of 3SAT.For the constructed instance IΦ, whether {p} is globally optimal is characterized by a condition on Φ’s 3SAT status.Source: §4 · p. 24

5 Pareto-optimal repairs

This section studies Pareto-optimal repairs, which use a set-based preference lift to select repairs that cannot be improved by consistent fact replacements, and relates them to globally optimal repairs. It provides characterizations and complexity results, including an exponentially long possible improvement process, a sound and complete polynomial-time algorithm, and bounds for repair checking and preferred consistent query answering.

5 Pareto-optimal repairs

  • A repair is Pareto optimal when no nonempty set of its facts can be replaced by a more preferred set while preserving consistency; PRep selects all such repairs.The notion lifts priorities to sets of facts, following the construction of Pareto-optimal vector sets.Source: §5 · pp. 24–25
  • PRep satisfies P1–P4 and contains GRep, but the inclusion is strict: some repairs are Pareto optimal without being globally optimal.Source: §5 · p. 25
  • A repair is Pareto optimal exactly when it is maximal under the induced repair preference; if the priority is acyclic, that induced preference is also acyclic.Source: §5 · p. 26
  • For any family of Pareto-optimal repairs satisfying P1 and P2, preferred consistent query answering is intractable even for an atomic query and two functional dependencies.Theorem 3 establishes this hardness for a family of instances and constraints.Source: §5 · p. 26
  • A repair is not Pareto optimal exactly when some outside fact is preferred to a fact in every conflict of that repair.This characterization supports a tractable procedure for repair checking.Source: §5 · p. 28
  • P-preferred repair checking is in LOGSPACE, while P-preferred consistent query answering is coNP-complete.Source: §5 · p. 28
  • P-preferred repair checking is in LOGSPACE, while deciding preferred consistent query answers is coNP-complete.Source: §5 · p. 28
  • Iteratively improving an arbitrary repair may require exponentially many steps because an exponential-length P-chain can occur.The approach checks Pareto optimality at each step, but the sequence of repairs in Example 4 has exponential length.Source: §5 · p. 29
  • Algorithm 3 constructs Pareto-optimal repairs soundly and completely in polynomial time.It returns an arbitrary repair if Pareto-optimal; otherwise, it constructs a completion-optimal repair, which is also Pareto-optimal.Source: §5 · p. 29

6 Completion-optimal repairs

This section defines completion-optimal repairs via total extensions of user priorities and establishes their structural properties, including a sound, complete polynomial-time construction algorithm. It also examines their complexity and their place in the hierarchy of preferred-repair families, including conditions under which that hierarchy collapses.

6 Completion-optimal repairs

  • A repair is completion-optimal when some total extension of the given priority makes it the sole globally optimal repair; the definition is unchanged if Pareto optimality is used.For total priorities, globally and Pareto-optimal repairs coincide.Source: §6 · p. 29
  • CRep is the smallest family of globally optimal repairs satisfying P1 and P2: it is contained in every such family.A repair belongs to CRep exactly when it belongs to every globally optimal repair family satisfying P1 and P2.Source: §6 · p. 31

P XRep pI, F, ¡

  • CRep satisfies P1–P4 and is a subset of GRep.Source: P XRep pI, F, ¡ · p. 31
  • Algorithm 4 soundly and completely constructs completion-optimal repairs in time polynomial in the input instance and priority relation.They can also be characterized as repairs obtained by iteratively accumulating facts selected with the winnow operator.Source: P XRep pI, F, ¡ · p. 32
  • C-preferred repair checking is in PTIME, while C-preferred consistent query answering is coNP-complete.The exact repair-checking complexity—PTIME-complete or in LOGSPACE—remains open.Source: P XRep pI, F, ¡ · p. 33
  • The hierarchy is proper: CRep is contained in GRep, which is contained in PRep, and the reverse inclusions fail.The text notes that not all globally optimal repairs are completion optimal, and that PRep is not contained in GRep.Source: P XRep pI, F, ¡ · p. 33
  • PRep, GRep, and CRep coincide with one key dependency or when priorities extend only to acyclic priorities; GRep and CRep also coincide with one functional dependency.Source: P XRep pI, F, ¡ · pp. 33–34

P CRep pI, F, ¡

  • These collapse conditions are sufficient but not necessary; for example, the hierarchy collapses with denial constraints and an empty priority relation.Source: P CRep pI, F, ¡ · p. 34

7 Tractable case

The section studies preferred query answering under a single functional dependency, after noting that earlier intractability proofs require at least two. It establishes a polynomial-time result for quantifier-free queries under the stated constraint restriction.

7 Tractable case

  • The section moves from conjunctions of ground literals to arbitrary ground queries when studying the one-functional-dependency case.The earlier intractability proofs use at least two functional dependencies.Source: §7 · p. 34
  • For functional dependencies, conflicts occur only within a relation, so the analysis assumes one relation R with functional dependency X → Y.The section uses X-clusters and (X,Y)-clusters to organize the analysis.Source: §7 · p. 34
  • Preferred consistent answers to quantifier-free queries are computable in PTIME with at most one functional dependency per relation and no other constraints, for PRep, GRep, and CRep.The proof assumes a constant-size query.Source: §7 · p. 36
  • The query procedure converts the query to CNF and tests whether a preferred repair satisfies the negation of each clause.It uses the tests for globally optimal or Pareto-optimal repairs; the tests are polynomial in the instance size when query size is constant.Source: §7 · p. 36

8 Related work

The related work considers several ways to incorporate priorities into inconsistency handling, contrasting how they restrict repairs, assign preferences, or resolve conflicts. The section also identifies settings that are difficult to compare directly with this framework.

8 Related work

  • The approaches in and assume transitive priorities, a stronger restriction than acyclicity that brings no computational benefit in this framework.[9] handles partial orders by considering their extensions to weak orders.Source: §8 · p. 37
  • Repair constraints in restrict deletions across relations; weakening them restores P1 but loses P3, while the original approach satisfies P3 but not P1.Source: §8 · p. 38
  • The probabilistic framework in weights conflicting facts and assigns probabilities to repairs, but generally retains all repairs and is difficult to compare with this approach.It considers one key dependency per relation; repairs are excluded only when their probability is zero.Source: §8 · p. 38
  • In the community-database setting of, acyclic mapping networks yield a unique solution, whereas cyclic networks may yield several and can produce cyclic priorities.Negative facts and conflicts between negative and positive facts also distinguish that setting from denial-constraint-based priorities.Source: §8 · p. 38

9 Conclusions and future work

The paper introduces preferred repairs and preferred consistent answers, with three repair families based on different notions of priority compliance. It reports sound and complete repairing algorithms and identifies extensions and complexity questions for future work.

9 Conclusions and future work

  • The paper presents PRep, GRep, and CRep as preferred-repair families based on different notions of optimality with respect to priorities.Source: §9 · p. 38
  • Each family has a sound and complete repairing algorithm, and Figure 9 summarizes the computational complexity results.The figure’s first row is taken from.Source: Figure 9 · p. 39, §9 · p. 39
  • Extending the approach to cyclic priorities remains an open direction, and adding priorities to similar preference frameworks can lose monotonicity (P5).The authors suggest conditional monotonicity may be needed to capture non-trivial repair families.Source: §9 · p. 39
  • Further work could study complexity under BCNF-conforming functional dependencies and extend the constraint class to universal constraints.Universal constraints can express conflicts involving both the presence and simultaneous absence of facts.Source: §9 · p. 39
Loading 0908.0464v3…