PaperlayerView exact revision on arXiv

Source-linked AI summary

Data Cleaning and Query Answering with Matching Dependencies and Matching Functions

Leopoldo Bertossi, Solmaz Kolahi, Laks V. S. Lakshmanan

arXiv:1008.3743v1cs.DB

TL;DR

The paper formalizes data cleaning with matching dependencies by using matching functions and a chase-like procedure, with semantic domination organizing the resulting instances. It defines clean query answers using bounds over possible clean instances, finds exact computation intractable in general, and gives polynomial-time approximations for monotone queries.

  • Problem

    Earlier MD semantics do not fully prescribe cleaning when multiple dependencies interact, and computing clean answers can be intractable even for simple cases.

    Source: §2 · p. 3, Complexity of Computing Clean Answers · p. 7

  • Method

    The paper uses matching functions in a chase-like cleaning process and defines clean query answers as lower and upper bounds over the resulting clean instances.

    Source: §8 · p. 11

  • Results

    Exact clean-answer computation is intractable in general, while polynomial-time under- and over-approximations are provided for queries monotone under semantic domination.

    Source: §8 · p. 11

  • Takeaways & Limitations

    Matching functions induce a lattice on attribute domains and semantic domination between instances, supporting clean-answer bounds and query relaxation.

    Source: §1 · p. 1, §8 · p. 11

    Iterative enforcement may break similarities present in the dirty instance, a trade-off the paper accepts for interacting MDs.

    Source: §4 · p. 5

Abstract

from arXiv · show

Matching dependencies were recently introduced as declarative rules for data cleaning and entity resolution. Enforcing a matching dependency on a database instance identifies the values of some attributes for two tuples, provided that the values of some other attributes are sufficiently similar. Assuming the existence of matching functions for making two attributes values equal, we formally introduce the process of cleaning an instance using matching dependencies, as a chase-like procedure. We show that matching functions naturally introduce a lattice structure on attribute domains, and a partial order of semantic domination between instances. Using the latter, we define the semantics of clean query answering in terms of certain/possible answers as the greatest lower bound/least upper bound of all possible answers obtained from the clean instances. We show that clean query answering is intractable in some cases. Then we study queries that behave monotonically wrt semantic domination order, and show that we can provide an under/over approximation for clean answers to monotone queries. Moreover, non-monotone positive queries can be relaxed into monotone queries.

1. INTRODUCTION

Matching dependencies encode expert knowledge as conditional rules for making values equal, but their earlier formulation did not specify how matching should be performed. This paper studies matching functions as the mechanism for enforcement and uses their properties to structure data cleaning and query answering.

1. INTRODUCTION

  • MDs make values in two tuples equal when other tuple values are sufficiently similar, extending entity resolution beyond whole-tuple merging.They were introduced to codify domain-expert knowledge for improving data quality.Source: §1 · p. 1
  • Matching functions address the unspecified value-identification step by combining inputs into a value that contains their information and semantically dominates them.The paper studies functions satisfying natural axioms rather than particular implementations.Source: §1 · p. 1
  • The address example applies a matching function to two addresses after name and phone similarities trigger an MD.The resulting address combines information from the two prior values.Source: §1 · p. 1

25 Main St., Ottawa

The paper extends matching dependencies with matching functions to define iterative data cleaning and clean query answering. It establishes the general complexity challenge and develops approximation and query-relaxation approaches, while connecting the framework to Swoosh.

25 Main St., Ottawa

  • The original MD framework leaves cleaning implementation unspecified; matching functions address limitations involving multiple MDs and support intended clean instances produced by a chase-like procedure.The chase can produce several stable clean instances, each semantically dominating the dirty instance.Source: §25 · p. 2
  • Clean answers use tight lower and upper bounds across answers from possible clean instances, but computing exact bounds is intractable in general.For queries monotone under semantic domination, polynomial-time under- and over-approximations are available.Source: §25 · p. 2
  • New relational algebra operators use the domain lattice to relax regular positive queries into queries monotone under semantic domination.The paper argues that monotone queries provide more informative answers on instances cleaned with MDs and matching functions.Source: §25 · p. 2
  • Matching functions induce a lattice on attribute domains and a partial order over instances called semantic domination.The paper studies matching functions through natural and intuitive axioms.Source: §25 · p. 2
  • The framework reconstructs Swoosh’s union-and-merge case using matching dependencies with matching functions.Swoosh is presented as a generic entity-resolution framework.Source: §25 · p. 2

2. BACKGROUND

The background presents matching dependencies as conditional identification rules and explains why the earlier pair-of-instances semantics is insufficient for cleaning with interacting dependencies. The paper motivates an iterative enforcement process that avoids unjustified changes.

2. BACKGROUND

  • An MD requires matching right-hand-side attribute values when corresponding left-hand-side values are similar; the earlier semantics describes one-step enforcement through a pair of instances.The definition does not fully prescribe updates when several MDs interact.Source: §2 · pp. 2–3
  • Enforcing one MD can break a similarity needed by another, so the earlier definition may fail to capture iterative enforcement of a set of interacting MDs.The example shows that subsequent changes may not satisfy all dependencies once a relevant similarity is broken.Source: §2 · p. 3
  • Stable instances lack a minimality criterion and can include changes unrelated to enforcing the MDs.The paper identifies changing an otherwise unaffected value as an unjustified update.Source: §2 · p. 3

3. MATCHING FUNCTIONS AND SEMANTIC DOMINATION

Matching functions satisfying idempotency, commutativity, and associativity induce a semilattice on attribute values, interpreted through semantic domination. The paper lifts this structure to instances and establishes a lattice framework relevant to query answering.

3. MATCHING FUNCTIONS AND SEMANTIC DOMINATION

  • Idempotent, commutative, and associative matching functions induce a partial order in which their output is the least upper bound of the input values.Under these axioms, each attribute domain forms a join semilattice.Source: §3 · p. 3
  • Semantic domination interprets the attribute-value order: a matching result dominates both values it replaces.The paper relates this notion to relative information contents.Source: §3 · p. 3
  • The paper assumes attribute domains are lattices with both greatest lower bounds and least upper bounds for query-answer semantics.It also assumes a bottom element that leaves any value unchanged under matching; a top element for inconsistency is not essential.Source: §3 · pp. 3–4
  • Matching functions can combine strings by taking the union of their represented sets or by producing a merged string that contains both inputs.For numeric values represented as intervals, the matching function returns the smallest interval containing both; for Boolean values, matching 0 and 1 can return an inconsistency marker.Source: §3 · p. 4
  • Similarity preservation is a strong optional assumption; unless specified otherwise, the paper does not require matching functions to preserve similarity.When preserved, the result remains similar to the values being replaced.Source: §3 · p. 4
  • For reduced instances, the instance ordering forms a lattice: the paper characterizes instance join as the least upper bound and instance meet as the greatest lower bound.The theorem states that the set of reduced instances under this ordering forms a lattice.Source: §3 · p. 4

4. ENFORCEMENT OF MDS AND CLEAN INSTANCES

The paper defines cleaning as a chase-like sequence of matching-dependency enforcement steps ending in a stable instance. Different enforcement orders can yield different clean instances, although specific conditions guarantee uniqueness.

4. ENFORCEMENT OF MDS AND CLEAN INSTANCES

  • Enforcing a matching dependency updates the identified attribute values with a matching function while leaving other tuple and attribute values unchanged.The chase repeats such steps until the instance is stable; under the matching-function assumptions, it terminates in polynomially many steps.Source: §4 · p. 5
  • Different enforcement orders can produce multiple clean instances, and enforcing interacting dependencies can break similarities that held in the original instance.A clean instance is stable, but need not satisfy the original instance-to-result condition for the dependencies.Source: §4 · p. 5
  • Similarity-preserving matching functions or interaction-free dependencies each guarantee a unique clean instance that satisfies the dependencies relative to the original instance.Interaction-free means no dependency’s right-hand-side attributes overlap another dependency’s left-hand-side attributes.Source: §4 · p. 5
  • The chase makes only changes required by the dependency semantics, but clean instances are not necessarily minimal under semantic domination.The paper gives clean outputs where one dominates another without the reverse domination holding.Source: §4 · p. 5

5. CLEAN QUERY ANSWERING

Clean query answering accounts for the possibility of several clean instances by bounding their query answers in the semantic-domination order. These bounds can preserve information that ordinary set intersection would discard.

5. CLEAN QUERY ANSWERING

  • The framework addresses query answering on dirty instances when dependencies may have multiple clean outcomes, a problem the paper says has received less attention than producing a clean instance.It seeks answers consistent with enforcing the dependencies.Source: §5 · p. 6
  • Unlike consistent query answering over repairs, clean query answering uses the semantic-domination order between the dirty instance and its clean instances.The paper relates its setup to certain and possible answers in consistent query answering.Source: §5 · p. 6
  • Certain and possible answers are the greatest lower bound and least upper bound of query results over all clean instances, rather than their set intersection and union.The bounds exist for the finite set of clean instances and are themselves reduced.Source: §5 · p. 6
  • The certain answer can retain “25 Main St.” even when the set-theoretic intersection of the two clean-instance answer sets is empty.The least upper bound in the example is the union of the two answer sets.Source: §5 · pp. 6–7
  • The lower and upper bounds collapse to one query result when matching functions are similarity preserving or dependencies are non-interacting.Source: §5 · p. 7

Complexity of Computing Clean Answers

Computing exact clean answers can be intractable even for simple dependencies and queries. The paper establishes coNP-completeness for deciding membership in the certain-answer set in one such setting.

Complexity of Computing Clean Answers

6. MONOTONE QUERIES

The section studies queries under semantic domination: monotone queries support bounds on clean answers, and positive queries can be relaxed to become monotone. It then gives procedures for approximating certain and possible answers.

6. MONOTONE QUERIES

  • For monotone queries, applying the query to the greatest lower and least upper bounds of clean instances under- and over-approximates certain and possible answers, respectively.The paper explicitly does not claim these approximations are polynomial-time in this general result.Source: §6 · p. 7, §6.2 · p. 8
  • A positive query selecting names by exact address can be non-monotone: it returns “J. Doe” on the dirty instance but nothing on either clean instance.Source: §6 · p. 7

6.1 Query relaxation

  • Relaxation replaces hard equality selections with lattice-based selections, and queries built from the relaxed operators are monotone under semantic domination.For example, σA=a becomes σa⪯A and σA1=A2 becomes σA1✶⪯A2.Source: §6.1 · p. 8
  • For the address example, the relaxed query returns “J. Doe” and “Jane Doe” as its certain answer, whereas the original query returns no answer on the clean instances.Source: §6.1 · p. 8

6.2 Approximating Clean Answers

7. A CASE FOR SWOOSH’S ENTITY

The section reconstructs Swoosh’s union match-and-merge case within the matching-dependency framework. It relates the frameworks’ domination orders and compares the clean instances they produce.

RESOLUTION

  • Swoosh operates on records, while this MD framework operates on attributes and retains tuple identifiers; Swoosh may prune dominated records.The reconstructed MD framework produces a single clean instance and keeps only the new version of a tuple when MDs are applied.Source: RESOLUTION · pp. 9–10
  • In the union case, attribute domains contain nonempty finite sets of values, initial records use singleton sets, and matching functions merge values by union.These matching functions are total, idempotent, commutative, associative, and similarity preserving.Source: RESOLUTION · p. 10
  • The constructed match and merge functions have Swoosh’s ICAR properties, including commutativity, associativity, and representativity.The matching relation is reflexive and commutative, and matching records produce the same merge regardless of their order.Source: RESOLUTION · p. 10
  • The general semantic domination relation on records coincides with Swoosh’s merge domination relation.The section also relates the resulting clean instances: each Swoosh record corresponds to an MD-clean tuple, and each MD-clean tuple has a Swoosh record that dominates its record values.Source: RESOLUTION · p. 10

8. CONCLUSIONS

The paper formalizes cleaning with matching dependencies and matching functions, using semantic domination to define clean instances and query answers. It establishes general intractability, identifies a tractable case, and gives polynomial-time approximations.

CONCLUSIONS

  • Matching functions induce lattice-theoretic structures on attribute domains, which yield a partial order of semantic domination between instances.The order compares instances in terms of information content and is also applied to sets of query answers.Source: §8 · p. 11
  • A chase-like procedure defines admissible clean instances by enforcing matching dependencies without unjustified changes to other attribute values.The procedure stepwise increases information content with respect to the domination order.Source: §8 · p. 11
  • Clean answers are tight lower and upper bounds on query answers across the possibly many clean instances, corresponding to certain and possible answers.The bounds are defined in terms of information content under semantic domination.Source: §8 · p. 11
  • The paper studies queries monotone under semantic domination and relaxes queries into monotone ones that provide more informative answers.The studied relaxation applies to a query posed over the dirty database.Source: §8 · p. 11
  • Clean query answering is intractable in general, though it is tractable when there is a single clean instance, and polynomial-time approximations are proposed.The paper describes under-approximations for certain answers and over-approximations for possible answers.Source: §8 · p. 11
  • More tractable cases and efficient approaches to intractable cases remain under investigation; connections between the domination-monotone language and other query settings remain open.The paper identifies connections to querying partially ordered domains, incomplete information, query relaxation, and similarity-based relational languages as open questions.Source: §8 · p. 11

A. SOME PROOFS

The proofs establish structural guarantees for matching-function cleaning and show that clean-query answering can be hard, while monotone queries support answer bounds. They also connect the matching-function formulation to entity-resolution semantics.

A. SOME PROOFS

  • Instance joins provide least upper bounds under semantic domination, while tuple meets support the corresponding lower-bound construction.The proof shows the join dominates both input instances and is below any common upper bound.Source: A. SOME PROOFS · p. 12
  • The cleaning sequence strictly dominates its predecessor, terminates after finitely many steps, and needs polynomially many matching applications to reach an upper bound.The proof constructs an upper-bounding instance by matching active-domain values for each attribute and comparable attributes.Source: A. SOME PROOFS · p. 12
  • Any two clean instances for the same initial instance and matching dependencies are identical, using the least-upper-bound property of matching functions.The proof establishes domination in both directions for every tuple identifier and attribute.Source: A. SOME PROOFS · p. 12
  • For interaction-free dependencies, enforcement leaves the left-hand-side attributes unchanged, a condition used in the under-clean-instance argument.The proof also establishes that values along the derivation are dominated by those in a clean instance.Source: A. SOME PROOFS · pp. 13–14
  • A reduction from 3SAT establishes the satisfiability correspondence used to prove hardness for clean-query answering.A formula is satisfiable exactly when ⊤ is absent from the certain answers in the constructed instance.Source: A. SOME PROOFS · p. 13
  • Monotone queries preserve the instance bounds when mapped to query answers, and the relational-algebra operators in RA⪯ are monotone.The proof checks projection, Cartesian product, union, and the two described selection forms.Source: A. SOME PROOFS · p. 13
  • Matching-function enforcement and the tuple-combination operation μ can simulate one another by finite sequences, relating the resulting instances to entity-resolution semantics.The proof uses this relationship to show the constructed entity-resolution instance meets the stated containment and domination conditions.Source: A. SOME PROOFS · p. 14
Loading 1008.3743v1…