Matching Dependencies (MDs) are a relatively recent proposal for declarative entity resolution. They are rules that specify, given the similarities satisfied by values in a database, what values should be considered duplicates, and have to be matched. On the basis of a chase-like procedure for MD enforcement, we can obtain clean (duplicate-free) instances; actually possibly several of them. The resolved answers to queries are those that are invariant under the resulting class of resolved instances. In previous work we identified some tractable cases (i.e. for certain classes of queries and MDs) of resolved query answering. In this paper we further investigate the complexity of this problem, identifying some intractable cases. For a special case we obtain a dichotomy complexity result.
We assume we are dealing with relational schemas and instances. Matching dependencies (MDs) are symbolic rules of the form: ∧ R[Ai] ≈ij S[Bj ] → ∧ R[Ak] =: S[Bl]; (1) i;j k;l where R; S are relational predicates, and the Ai; ::: are attributes for them. The LHS captures similarity conditions on a pair of tuples belonging to the extensions of R and S in an instance D. We abbreviate this formula as: R[A] ≈ S[B] → R[C] =: S[E]. MDs have a dynamic interpretation requiring that those values on the RHS should be updated to some (unspecified) common value. Those attributes on a RHS of an MD are called changeable attributes.
The similarity predicates ≈ (there may be more than one in an MD depending on the attributes involved) are treated here as built-ins, but are assumed to satisfy: (a) symmetry: if x ≈ y, then y ≈ x; and (b) equality subsumption: if x = y, then x ≈ y. However, transitivity is not assumed (and in some application it may not hold).
MDs are to be “applied” iteratively until duplicates are solved. In order to keep track of the changes and comparing tuples and instances, we use global tuple identifiers, a non-changeable surrogate key for each database predicate that has changeable attributes. The auxiliary, extra attribute (when shown) appears as the first attribute in a relation, e.g. t is the identifier in R(t; x). A position is a pair (t; A) with t a tuple id, and A an attribute (of the relation where t is an id). The position’s value, t[A], is the value for A in tuple (with id) t.
A semantics for MDs acting on database instances was proposed in [
D 7→ D1 7→ D2 7→ · · · 7→ D′; (2)
terminating in D′, that satisfies the MDs as equality generating dependencies [
: replacing = by equality.
The semantics specifies the one-step transitions or updates allowed to go from Di−1
to Di, i.e. “7→” in (2). Only modifiable positions within the instance are allowed to
change their values in such a step, and as forced by the MDs. Actually, the modifiable
positions syntactically depend on a whole set M of MDs and instance at hand; and
can be recursively defined (see [
R(D) A B t1 a b t2 a c 7→
R(D′) A B t1 a d t2 a d
D′ is a resolved instance since it satisfies the MD interpreted as an FD (the update value d is arbitrary).
D′ has no modifiable positions with unresolved values: the values for B are already the same, so there is no reason to change them.
More formally, the single step semantics is a follows. Each pair Di; Di+1 in an update sequence (2), i.e. a chase step, must satisfy the set M of MDs, modulo unmodifiability, denoted (Di; Di+1) |=um M , which holds iff: (a) For every MD, say R[A] ≈ S[B] → R[C] =: S[D] and pair of tuples tR and tS , if tR[A] ≈ tS [B] in Di, then tR[C] = tS [D] in Di+1; and (b) The value of a position can only differ between Di and Di+1 if it is modifiable wrt Di.
This semantics stays as close as possible to the spirit of the MDs as originally
introduced [
: R[B] = R[B] → R[C] = R[C]: to change its value in one step on the basis of an MD and D. However, position (t1; C) is modifiable. We obtain two resolved instances for D: D1 and D2 below.
R(D1) A B C R(D2) A B C D1 cannot be obtained in a single (one t1 a b d t1 a b e step) update since the underlined value is t2 a b d t2 a b e for a non-modifiable position. However, t3 a b d t3 a b e D2 can.
Among the resolved instances we prefer those that are closest to the original instance. Accordingly, a minimally resolved instance (MRI) of D is a resolved instance D′ such that the number of changes of attribute values comparing D with D′ is a minimum. In Example 3, instance D2 is an MRI, but not D1 (2 vs. 3 changes). We denote with Res(D; M ) and MinRes(D; M ) the classes of resolved, resp. minimally resolved, instances of D wrt M .
Given a conjunctive query Q, a set of MDs M , and an instance D, the resolved answers to Q from D are those that are invariant under the entity resolution process, i.e. they are answers to Q that are true in all MRIs of D: ResAnsM (Q; D) := {c | D′ |= Q[c]; for every D′ ∈ MinRes(D; M )}. We denote with RA(Q; M ) the decision problem {(D; c) | c ∈ ResAnsM (Q; D)}.
The definition of resolved answer is reminiscent of that of consistent query answers
(CQA) in databases that may not satisfy given integrity constraints (ICs) [
Doing something similar for resolved query answering (RQA) under MDs brings new challenges: (a) MDs contain the non-transitive similarity predicates. (b) Enforcing consistency of updates requires computing the transitive closure of such operators. (c) The minimality of value changes (that is not always used in CQA or considered for consistent rewritings). (d) The semantics of resolved query answering for MD-based entity resolution is given, in the end, in terms of a chase procedure.2 However, the semantics of CQA is model-theoretic, given in terms repairs that are not operationally defined, but arise from set-theoretic conditions.3 3
In [
Here cycles help us, because the termination condition for the chase imposes a
simple form on the minimally resolved instances (easier to capture and characterize) [
The case of a set of MDs consisting of
R[A] ≈ R[A] → R[B] =: R[B] and R[B] ≈ R[B] → R[C] =: R[C]; (3)
which is neither non-interacting nor cyclic, is not covered by the positive cases for
Datalog rewriting above. Actually, for this set RQA becomes intractable for very simple
queries, like Q(x; z) : ∃yR(x; y; z), that is UJCQ [
For all sets M of MDs we consider below, at most two relational predicates appear
in M , and when there are two predicates, both appear in all MDs in M . According to
the syntactic restrictions for MDs in (1), those two predicates occur in all conjuncts
of an MD in M . Furthermore, all the sets of MDs considered below will turn out to
2 For some implicit connections between repairs and chase procedures, e.g. as used in data
exchange see [
Definition 1. Consider a set M of MDs involving the predicates R and S. A changeable attribute query Q is a (conjunctive) query in UJCQ, containing a conjunct of the form R(x) or S(y) with all variables free. Such a conjunct is called a free occurrence of the predicate R or S.
By definition, the class of changeable attribute queries (CHAQ) is a subclass of UJCQ. Both classes depend on the set of MDs at hand. For example, for the MDs in (3), ∃yR(x; y; z) ∈ UJCQ r CHAQ, but ∃w∃t(R(x; y; z) ∧ S(x; w; t)) ∈ CHAQ. We confine attention to UJCQ and subsets of it because, as mentioned in the previous section, intractability limits the applicability of the duplicate resolution method for queries outside UJCQ. The requirement that the query contains a free occurrence of R or S eliminates from consideration certain queries in UJCQ for which the resolved answer problem is trivially tractable. For example, for MDs in (3), the query ∃y∃zR(x; y; z) is not in CHAQ, but is tractable simply because it does not return the values of a changeable attribute (the resolved answers are the answers in the usual sense). Definition 2. A set M of MDs is hard if for every CHAQ Q, RA(Q; M ) is NP-hard. M is easy if for every CHAQ Q, RA(Q; M ) is in PTIME.
Of course, a set of MDs may not be hard or easy. In the following we give some syntactic conditions that guarantee hardness for classes of MDs.
Definition 3. Let m be an MD. The symmetric binary relation LRel (m) (RRel (m)) relates each pair of attributes A and B such that a conjunct of the form R[A] ≈ S[B] (resp. R[A] =: S[B]) appears in LHS (m) (resp. RHS (m)). An L-component (R-component) of m is an equivalence class of the reflexive and transitive closure, LRel (m)eq (resp. RRel (m)eq ), of LRel (m) (resp. RRel (m)).
The first results concern linear pairs of MDs, i.e. those whose graph MDG (M ) consisting of the vertices m1 and m2, say
m1: R[A] ≈1 S[B] → R[C] =: S[E]; and m2: R[F ] ≈2 S[G] → R[H] =: S[I]; (4) with only an edge from m1 to m2, i.e. (R[C] ∪ S[E]) ∩ (R[F ] ∪ S[G]) ̸= ∅, whereas (R[H] ∪ S[I]) ∩ (R[A] ∪ S[B]) = ∅. The linear pair is denoted by (m1; m2). Definition 4. Let (m1; m2) be a linear pair as in (4). (a) BR is a binary (reflexive and symmetric) relation on attributes of R: (R[U1]; R[U2]) ∈ BR iff R[U1] and R[U2] are in the same R-component of m1 or the same L-component of m2. Similarly for BS . (b) An R-equivalent set (R-ES) of attributes of (m1; m2) is an equivalence class of TC (BR), the transitive closure of BR, with at least one attribute in the equivalence class belonging to LHS (m2). The definition of an S-equivalent set (S-ES) is the same, with R replaced by S. (c) An (R or S)-ES E of (m1; m2) is bound if E ∩ LHS (m1) is non-empty. Theorem 1. Let (m1; m2) be a linear pair as in (4), with R and S distinct predicates. Assume that each similarity relation has an infinite set of mutually dissimilar elements. Let ER and ES be the classes of R-ESs and S-ESs, resp. The pair (m1; m2) is hard if RHS (m1) ∩ RHS (m2) = ∅, and at least one of the following does not hold: (a) At least one of the following is true: (i) there are no attributes of R in RHS (m1) ∩ LHS (m2 ); (ii) all ESs in ER are bound; or (iii) for each L-component L of m1, there is an attribute of R in L ∩ LHS (m2). (b) At least one of the following is true: (i) there are no attributes of S in RHS (m1) ∩ LHS (m2 ); (ii) all ESs in ES are bound; or (iii) for each L-component L of m1, there is an attribute of S in L ∩ LHS (m2).
Theorem 1 says that a linear pair of MDs is hard unless the syntactic form of the MDs is
such that there is a certain association between changeable attributes in LHS (m2) and
attributes in LHS (m1) as specified by conditions (ii) and (iii). When m1 is applied to
an instance, similarities can be produced among the values of attributes of RHS (m1)
which are not required by the chase but result from a particular choice of update values.
Such accidental similarities affect the subsequent updates made by applying m2,
making the query answering problem intractable [
However, when condition (ii) or (iii) is satisfied, accidental similarities among the values of attributes in RHS (m1) cannot be passed on to values of attributes in RHS (m2).
This result gives a syntactic condition for hardness. It is an important result, because it applies to many cases of practical interest. For example, the linear pair (m1; m2) in (3) turns out to be hard (for all CHAQ queries, in addition to ∃yR(x; y; z)).
All syntactic conditions/constructs on attributes above, in particular, the transitive closures on attributes, are “orthogonal” to semantic properties of the similarity relations. When similarity predicates are transitive, every linear pair not satisfying the hardness criteria of Theorem 1 is easy.
Theorem 2. (dichotomy for transitive similarity) Let (m1; m2) be a linear pair with RHS (m1) ∩ RHS (m2) = ∅. If the similarity operators are transitive, then (m1; m2) is either easy or hard.
The next result concerns pair-preserving acyclic sets of MDs, defined by: M is pairpreserving if, for any attribute R[A] occurring in a MD, there is only one attribute S[B] such that R[A] ≈ S[B] or R[A] =: S[B] occur in an MD. These sets of MDs can be of arbitrary size ( still subject to the condition of containing at most two predicates). The pair-preserving assumption typically holds in a duplicate resolution setting, since the values of pairs of attributes are normally compared only if they hold the same type of information (e.g. they are both addresses or both names).
Definition 5. Let M be pair-preserving and acyclic, B an attribute in M , and M ′ ⊆ M . B is non-inclusive wrt. M ′ if, for every m ∈ M rM ′ with B ∈ RHS (m), there is an attribute C such that: (a) C ∈ LHS (m), (b) C ̸∈ ∪m′∈M′ LHS (m′), and (c) C is non-inclusive wrt. M ′.
This is a recursive definition of non-inclusiveness. The base case occurs when C is not in RHS (m) for any m, and so must be inclusive (i.e. not non-inclusive). Because C ∈ LHS (m) in the definition, for any m1 such that C ∈ RHS (m1), there is an edge from m1 to m. Therefore, we are traversing an edge backwards with each recursive step, and the recursion terminates by the acyclicity assumption.
Non-inclusiveness is a generalization of conditions (a) (iii) and (b) (iii) in Theorem 1 to a set of arbitrarily many MDs. It expresses a condition of inclusion of attributes in the left-hand side of one MD in the left-hand side of another. Theorem 3 tells us that a set of MDs that is non-inclusive in this sense is hard. Notice that the condition of Theorem 1 that there exists an ES that is not bound does not appear in Theorem 3. This is because, by the pair-preserving requirement, there cannot be a bound ES for any pair of MDs in the set. For linear pairs, Theorem 3 becomes Theorem 1.
Theorem 3. Let M be pair-preserving and acyclic. Assume there is {m1; m2} ⊆ M , and attributes C ∈ RHS (m2), B ∈ RHS (m1) ∩ LHS (m2) with: (a) C is noninclusive wrt {m1; m2}, and (b) B is non-inclusive wrt {m2}. Then, M is hard. Acknowledgments: Research supported by the NSERC Strategic Network on Business Intelligence (BIN ADC05), NSERC/IBM CRDPJ/371084-2008, and NSERC Discovery.