REPLACE: A Logical Framework for Combining Collective Entity Resolution and Repairing

1 Introduction

Data quality is one of the most fundamental problems in data management as dirty data can lead to incorrect decisions based on faulty retrieved answers from information systems, and unreliable data analysis, engendering huge costs to the private and public sectors [Fan and Geerts, 2012; Ilyas and Chu, 2019]. It is also a multi-faceted problem, encompassing several distinct issues: multiple representations of the same entity (deduplication), conflicting and/or erroneous information (consistency / accuracy), missing information (completeness), and outdated information (currency) [Fan and Geerts, 2012]. While far from solved, each facet of the data quality problem has given rise to a sizeable literature and increasingly sophisticated methods. We give a brief (and necessarily incomplete) introduction to the issues central to our work: deduplication and consistency.

Deduplication, also called record linkage or entity resolution (ER), was originally formulated as the task of identifying duplicate records in a table, and traditionally handled by comparing attribute values using similarity measures [Newcombe et al., 1959]. Over time, however, variants of the problem have been explored, in which we may identify (match, merge) pairs of entity references or values, rather than whole tuples, and treat multiple tables and/or entity types together (so-called collective entity resolution [Bhattacharya and Getoor, 2007]), e.g. using a match of two authors infer that a pair of paper ids should be merged. Moreover, some recent approaches to collective ER [Deng et al., 2022; Bienvenu et al., 2022] are able to exploit recursive dependencies, e.g. a merge of authors may trigger merges of papers which in turn may trigger new author merges. Diverse techniques have been applied to (collective) ER, including similarity measures, deep learning, probabilistic formalisms, and declarative frameworks based upon logical rules and constraints, see [Christophides et al., 2021] for a recent survey.

There is likewise a vast body of work aimed at identifying and removing conflicting facts to restore consistency. Declarative constraints (such as functional dependencies, or the broader class of denial constraints) are often employed to specify consistency requirements [Chu et al., 2013], and the goal is to produce a consistent version of the data (called a repair) through deletion or modification of facts. However, due to lack of information, one typically cannot definitively identify the 'true' repair, so data cleaning often relies upon heuristics to produce a unique result [Ilyas and Chu, 2019]. By contrast, the well-known consistent query answering (CQA) paradigm [Arenas et al., 1999; Bertossi, 2011] allows for meaningful answers to be obtained without committing to a single repair, by reasoning over the space of all (preferred) repairs and returning those answers which hold w.r.t. every such repair. The approach follows the skeptical mode of reasoning often considered in knowledge representation and reasoning (KR), and it has in turn inspired a line of KR research on inconsistency-tolerant ontology-based data access [Bienvenu, 2020; Lukasiewicz et al., 2022]. While CQA has higher complexity than data cleaning methods, SAT-based implementations show promising results [Dixit and Kolaitis, 2022].

The different facets of the data quality problem have mostly been considered in isolation, whereas in practice, datasets can be expected to suffer from multiple data quality issues. A pipeline approach, which applies different methods in sequence, has the disadvantage that useful synergies may be missed, as noted in [Chu et al., 2013; Fan et al., 2014]. For example, by merging two constants, we may resolve a violation of a functional dependency (FD) without the need to delete facts, while conversely, by deleting incorrect facts, we may enable some desirable merges. The interest of combining ER with repairs has been advocated in [Fan et al., 2014]: "When taken together, record matching and data repairing perform much better than being treated as separate processes". They propose to interleave repair operations (value updates) with merges of values inferred using matching dependencies, and study when this combined process terminates and how to generate a single repair of optimal cost.

We believe that the development of holistic approaches for jointly tackling the ER and repairing tasks, pioneered in [Fan et al., 2014], merits further investigation. Indeed, given the vast number of different ER and repair methods, there are many options for which methods to use and how to integrate them. Moreover, to the best of our knowledge, no work has explored how to reason over a space of alternative solutions (in the spirit of CQA) for the combined task. These considerations motivate us to introduce REPLACE, a logic-based framework for collective entity resolution and repairing.

The REPLACE framework adopts the expressive class of denial constraints (which generalize the conditional FDs considered in [Fan et al., 2014]) and subset repairs (obtained via deletion of facts, rather than updates), the most commonly considered repair notion in the CQA literature. The ER mechanism in REPLACE is based on the recently proposed LACE framework [Bienvenu et al., 2022], which employs hard and soft rules to define mandatory and possible merges of constants. Differently from [Fan et al., 2014] and other works using matching dependencies [Fan et al., 2009; Bertossi et al., 2013], the semantics is global in the sense that we merge all occurrences of the matched constants [Arasu et al., 2009; Burdick et al., 2016], rather than only those constant occurrences used in deriving the match. Such a semantics is geared towards merging of constants that are entity references (e.g. authors, publications), whereas the local one is more appropriate for merging attribute values (e.g. titles and addresses) (see [Bienvenu et al., 2022] for a detailed discussion). REPLACE's semantics further follows the standard desiderata of maximizing merges and minimizing deletions. As these two criteria may conflict, REPLACE implements three natural ways to compare solutions: give priority to the maximization of merges (MER), give priority to the minimization of deletions (DEL), or adopt the Pareto principle (PAR).

Aside from introducing the new framework, our main contribution is the investigation of the data complexity of the main reasoning tasks associated with REPLACE. First, we show that the problem of recognizing optimal solutions is coNP-complete, for all three optimality notions. Next, we consider how to query the space of optimal solutions and determine the complexity of recognizing certain and possible query answers, i.e. those answers which hold in all or some optimal solution, respectively. The certain answer tasks are Πp2 -complete for the three optimality notions, while for possible answers, the recognition problem Σp2 -complete for MER

and DEL, but NP-complete for PAR. We further consider a restricted setting in which inequality atoms are disallowed in denial constraints. This restriction does not yield better complexity for these problems, if we consider the MER preorder, whereas for DEL and PAR, the complexity improves in almost all cases. As a further contribution, we introduce a novel notion of most informative answer to obtain a more compact presentation of query results and show that the improved format leads to a slight increase in the complexity of certain and possible answer recognition tasks. We conclude the paper with some directions for future work.

2 Preliminaries

A (relational) schema S is a finite set of relation symbols, with each R ∈ S having an associated arity and list of attributes. As is standard, we use R/k and R(A1, . . . ,Ak) to indicate, respectively, that R has arity k and that its attributes are A1, . . . ,Ak. A database instance over a schema S (or (S-)database for short) assigns to each k-ary relation symbol R ∈ S a finite k-ary relation over a fixed, denumerable set of constants. Equivalently, we view an S-database D as a finite set of facts of the form R(c1, . . . , ck), where (c1, . . . , ck) is a tuple of constants of the same arity as R. We use the notations R(c1, . . . , ck) ∈ D and D ⊆ D′ with their obvious meanings. The active domain of a database D, denoted by dom(D), is the set of constants occurring in D.

When we speak of queries in this paper, unless otherwise stated, we mean a conjunctive query (CQ). Recall that a CQ over a schema S takes the form q(x) = ∃y.ϕ(x, y), where x and y are disjoint lists of variables, and ϕ is a finite conjunction of relational atoms over S, i.e. atoms of the form R(t1, . . . , tk) with R ∈ S and each ti is either a constant or a variable from x ∪ y. The arity of a query q(x) is the arity of x, and a query with arity 0 is called Boolean. Given an n-ary query q(x1, . . . , xn) and n-tuple of constants c = (c1, . . . , cn), we denote by q[c] the Boolean query obtained by replacing each xi by ci. The answers to an n-ary query q(x) over a database D is defined as the set of n-tuples of constants c from dom(D) such that the Boolean CQ q[c] holds in D. We use q(D) to denote the answers to q over D.

When formulating entity resolution rules, we will consider queries that may also contain atoms built from a set of externally defined binary similarity predicates. The preceding definitions and notations extend to such queries, the only difference being that similarity predicates have a fixed meaning (typically defined by applying a similarity metric, e.g. edit distance, and keeping those pairs of values whose score exceeds a given threshold).

Our framework will also make use of denial constraints [Bertossi, 2011; Fan and Geerts, 2012]. Recall that a denial constraint over a schema S takes the form ∀x.¬(φ(x)), where φ(x) is a finite conjunction of relational atoms over S and inequality atoms t1 ̸= t2.

3 Existing LACE Framework

In this section, we recall the salient features and definitions of the LACE framework [Bienvenu et al., 2022] for collective entity resolution, as it will form the basis for our new REPLACE framework, presented in Section 4.

Entity resolution consists in determining pairs of database constants that refer to the same entity and can thus be identified. We will use the term merge to speak about such pairs. The LACE framework employs hard and soft rules to indicate, respectively, required or potential merges. A hard rule (w.r.t. a schema S) takes the form q(x, y) ⇒ EQ(x, y), where q(x, y) is a CQ, whose atoms may use relation symbols in S as well as similarity predicates, and EQ is a special relation symbol (not in S) used to store merges. Intuitively, such a rule states that (c1, c2) being an answer to q is sufficient to conclude that c1 and c2 refer to the same entity. A soft rule has a similar form: q(x, y) --⇢ EQ(x, y), but states instead that (c1, c2) being an answer to q provides reasonable evidence for c1 and c2 denoting the same entity. Soft rules suggest potential (but not mandatory) merges of constants. In what follows, we use the notation q(x, y) → EQ(x, y) for a generic (hard or soft) rule, and shall omit quantifiers in rule bodies for brevity.

In addition to rules for generating merges, the LACE framework employs denial constraints to define consistency requirements. Together they form a specification:

Definition 1 ([Bienvenu et al., 2022]). A data quality (DQ) specification Σ over a schema S takes the form Σ = 〈Γ, ∆〉, where Γ = Γh ∪ Γs is a finite set of hard and soft rules over S, and ∆ is a finite set of denial constraints over S.

Example 1. Figure 1 introduces the schema Sex, database Dex, and DQ specification Σex = 〈Γex,∆ex〉 of our running example. Informally, the hard rule ρ1 states that paper identifiers with similar titles, same year, same venue, same first author, and same conference chair must refer to the same paper. The soft rule σ1 states that author ids associated with similar emails and the same institution likely refer to the same person. Finally, the denial constraint δ1 enforces that there is a single chair for a given venue and year, while δ2 states that the first author of a paper cannot be the same as the chair of the event where the paper was published.

The semantics of LACE is based upon solutions, which take the form of equivalence relations over the constants, with the meaning that all constants from the same equivalence class are deemed to be references to the same entity. Solutions equate constants, rather than occurrences of constants, because LACE focuses specifically on merging constants that are entity references (e.g. paper and author ids). Intuitively, each solution is obtained by 'deriving' new merges via rule applications and closure operations. Importantly, rule bodies are evaluated on the database induced by previously derived merges, which makes it possible for new rules to become applicable, i.e. merges can enable additional merges.

In order to formally define solutions, we must first introduce some preliminary notions. Given a set S of pairs of constants from a database D, we denote by EqRel(S,D) the least equivalence relation E ⊇ S over dom(D), i.e. we close S under reflexivity, symmetry, and transitivity. We assume that each equivalence relation E is equipped with a function rpE that maps each element to a representative of its equivalence class in E. Given a database D and an equivalence relation E over dom(D), the database induced by D and E, denoted by DE, is the database obtained from D by replacing each constant c by rpE(c). Moreover, for a tuple c of constants (resp. query q, denial constraint δ), we denote by cE (resp. qE, δE) the tuple of constants (resp. query, denial constraint) obtained by replacing each constant c mentioned also in an equivalence relation E by rpE(c). We then define the set q(D, E) of answers to a query q(x) w.r.t. D and E as:

A set of denial constraints ∆ is satisfied in (D,E), written (D,E) |= ∆, if DE |= δE for every δ ∈ ∆. A rule γ = q(x, y) → EQ(x, y) ∈ Γ is satisfied in (D,E), written (D,E) |= γ, if q(D,E) ⊆ E, and (D,E) |= Γ′ if all rules in Γ′ ⊆ Γ are satisfied. We call a pair (c, c′ ) of constants active in (D,E) w.r.t. Γ if there exists a rule q(x, y) → EQ(x, y) ∈ Γ such that (c, c′ ) ∈ q(D, E).

Remark 1. There is in fact an additional syntactic condition placed on LACE rulesets (and which we shall adopt also in this paper), namely, that attributes that are involved in merges cannot participate in similarity atoms. We refer to [Bienvenu et al., 2022] for a formal definition and discussion, simply noting that this condition ensures an unambiguous evaluation of similarity atoms in induced databases.

We can now give the formal definition of LACE solutions: Definition 2 ([Bienvenu et al., 2022]). Given a DQ specification Σ over a schema S and an S-database D, we say that an equivalence relation E over dom(D) is an ER candidate solution for (D,Σ) if it satisfies one of the two conditions:

• (i) E = EqRel(∅,D);
• (ii) E = EqRel(E′ ∪ {α},D), where E′ is a candidate solution for (D,Σ) and α = (c1, c2) is active in (D,E′ ) w.r.t. Γ.

An ER solution for (D, Σ) is a candidate solution E that further satisfies (a) (D,E) |= Γh and (b) (D,E) |= ∆. We denote by ERSol(D, Σ) the set of ER solutions for (D, Σ).

Notice that each pair of constants that is deemed equivalent by the ER solution is obtained by a sequence of rule applications and closure operations. Moreover, solutions must be coherent in the sense that all of the hard rules and denial constraints have to be satisfied w.r.t. the induced database.

Example 2. Continuing our running example, let D′ex be the Sex-database obtained from Dex by removing the tuples regarding papers p1, p2, p3, and p4. Due to the tuples involving p6, p7, and p8, we have (D′ex ,E0) ̸|= δ1, for the initial relation E0 = EqRel(∅,D′ex ). However, we can resolve this violation by merging authors a4 and a5. Indeed, one can verify that ϵ = (a4, a5) is active in (D′ex , E0) w.r.t. Γex due to σ1. Also α = (a1, a2) and β = (a2, a3) are active due to σ1.

However, we cannot include both α and β, otherwise by transitivity we would have a1 = a3, implying that the first author of paper p5 would be the same as the chair, in violation of δ2. Now, consider E1 = EqRel({β, ϵ},D′ex ) and E2 = EqRel({α, ϵ}, D′ex ). While E1 ∈ ERSol(D′ex , Σex), we have E2 ̸∈ ERSol(D′ex , Σex). This is because (D′ex , E2) ̸|= ρ1 since ζ = (p6, p7) is now active in (D′ex ,E2) w.r.t. Γex. One can verify that E1 and E3 = EqRel({α, ϵ, ζ},D′ex ) are the

δ1 = ¬(∃p, t, f , y, v, c, p′ , t′ , f ′ , c ′ .Paper(p, t, f , y, v, c) ∧ Paper(p′ , t′ , f ′ , y, v, c ′ ) ∧ c ̸= c ′ )

δ2 = ¬(∃p, t, a, y, v.Paper(p, t, a, y, v, a))

ρ1 = Paper(x, t, f , y, v, c) ∧ Paper(y, t′ , f , y, v, c) ∧ t ≈1 t′ ⇒ EQ(x, y)

σ1 = Author(x, e, i) ∧ Author(y, e′ , i) ∧ e ≈2 e′ --⇢ EQ(x, y)

Figure 1: A schema Sex, Sex-database Dex, and DQ specification Σex = 〈Γex, ∆ex〉 over Sex with Γex = {ρ1, σ1} and ∆ex = {δ1, δ2}. The extension of the similarity predicates ≈1 and ≈2 (both restricted to dom(Dex)) are the symmetric and reflexive closures of {(e1, e2), (e2, e3), (e4, e5)} and {(t1, t2), (t3, t4), (t6, t7), (t7, t8)}, respectively, where ei and ti are the email of author ai and title of paper pi, respectively.

only maximal ER solutions for ERSol(D′ex , Σex), i.e. they belong to ERSol(D′ex ,Σex) and there is no other solution in ERSol(D′ex , Σex) containing strictly more merges.

Now reconsider the original database Dex. One can verify that Sol(Dex,Σex) = ∅. This is because the tuples with p1 and p2 violate δ1, and, if a1 and a2 are merged to solve this violation, then δ2 is violated due to the tuples with p3 and p4.

4 REPLACE: Adding Delete Operations

In practice, a given database may suffer from multiple data quality issues. Some constraint violations may result from the use of different constants for the same entity, and thus may be resolved through merging constants. However, other constraint violations stem from the presence of erroneous facts and can only be resolved by removing information. In this section, we introduce a holistic approach to data quality that allows for both merge and fact deletion operations. Our new REPLACE framework can be viewed as the marriage of LACE with the well-known consistent query answering approach.

Extending LACE with fact deletions allows us to obtain meaningful solutions when ERSol(D, Σ) = ∅, but also to discover merges that were blocked due to constraint violations:

Example 3. Recall the database D′ex from the previous example and observe that by removing the fact with pid p5, we can now include both α = (a1, a2) and β = (a2, a3) in the set of merges, which will lead to η = (p7, p8) being active.

The REPLACE framework adopts the DQ specifications from LACE, but redefines what constitutes a solution to a database-specification (D,Σ) pair. In addition to an equivalence relation E that specifies merges, solutions will additionally contain a set R of facts to delete from D. We shall require that (i) E ∈ ERSol(D \ R,Σ), i.e. E is an ER solution for (D \ R, Σ) and (ii) if a fact ϕ ∈ R is equivalent to a fact ψ ∈ D w.r.t. E, then ψ ∈ R. A fact ϕ = P(c) is said to be equivalent to ψ = P ′ (c′ ) w.r.t. E, denoted ϕ ≡E ψ, if P = P ′ and cE = c′E.

We are now ready to formally define the new notion of solutions employed by REPLACE:

Definition 3. Given a DQ specification Σ over a schema S and an S-database D, we say that a pair W = (R,E) is a solution for (D, Σ) if (i) R ⊆ D, (ii) E ∈ ERSol(D \ R, Σ), and (iii) for all ϕ, ψ ∈ D with ϕ ≡E ψ, ϕ ∈ R iff ψ ∈ R. We denote by Sol(D, Σ) the set of solutions for (D, Σ).

Example 4. Let W1 = (R1,E1) and W2 = (R2,E2) be such that R1 (resp. R2) consists of the Paper fact with pid p1 (resp. p2), E1 = EqRel({β, ϵ, θ}, (Dex \ R1)), and E2 = EqRel({β, ϵ, θ}, (Dex \ R2))), where β = (a2, a3), ϵ = (a4, a5), and θ = (p3, p4). One can verify that W1 ∈ Sol(Dex, Σex) and W2 ∈ Sol(Dex, Σex).

Rather than considering all solutions, it is natural to focus on the 'best' ones. But what makes a solution better than another? Similarly to LACE, we will prefer solutions that contain more merges, since we aim to tackle the ER problem. However, we also want to retain as much information as possible, hence should minimize fact deletions, as is done when defining repairs. These two criteria may conflict, as deleting more facts may enable more merges. This leads us to consider three natural ways to compare solutions: give priority to the maximization of merges (MER), give priority to the minimization of deletions (DEL), or adopt the Pareto principle and accord equal priority to both criteria (PAR). The following definition formalizes the three preorders for comparing solutions and the resulting notions of optimal solution, using set inclusion for comparing the sets of merges and deletions.

Definition 4. Consider a DQ specification Σ over schema S and S-database D. The preorders ≺MER, ≺DEL, and ≺PAR over Sol(D, Σ) are defined as follows:

• (R,E) ≺MER (R′ ,E′ ) iff either (i) E ⊂ E′ or (ii) E ⊆ E′ and R′ ⊂ R;
• (R,E) ≺DEL (R′ ,E′ ) iff either (i) R′ ⊂ R or (ii) R′ ⊆ R and E ⊂ E′ ;
• (R,E) ≺PAR (R′ ,E′ ) iff either (i) E ⊂ E′ and R′ ⊆ R or (ii) R′ ⊂ R and E ⊆ E′ .

For X ∈ {MER, DEL, PAR}, we call a solution W for (D, Σ) an ⪯X-optimal solution for (D, Σ) if there is no solution W ′ for (D, Σ) such that W ≺X W ′ , and denote by SolX(D, Σ) the set of ⪯X-optimal solutions for (D, Σ).

It is easy to verify that both SolMER(D, Σ) ⊆ SolPAR(D, Σ) and SolDEL(D,Σ) ⊆ SolPAR(D,Σ) hold for any databasespecification pair (D,Σ). The next example shows that the converse inclusions do not necessarily hold. Furthermore, using analogous arguments, it is not hard to construct a case where W ∈ SolPAR(D, Σ) but neither W ∈ SolMER(D, Σ) nor W ∈ SolDEL(D, Σ).

Example 5. Returning to our running example, it can be verified that W1 and W2 from Example 4 both belong to SolX(Dex, Σex) for each X ∈ {MER, DEL, PAR}.

Next consider W3 = (R3,E3), in which R3 consists of the tuples with pids p3 and p4 and E3 = EqRel({α, µ, ϵ, ζ, }, (Dex \ R3)), where α = (a1, a2), µ = (p1, p2), ϵ = (a4, a5), and ζ = (p6, p7). One can show that W3 ∈ SolDEL(Dex,Σex) (hence, W3 ∈ SolPAR(Dex,Σex)) because the violation of δ1 involving the p1 and p2 tuples is resolved by merging a1 and a2, rather than via deletion. We claim however that W3 ̸∈ SolMER(Dex,Σex). To see why, let W4 = (R4, E4) be such that R4 contains the tuples with pids p3, p4, and p5 and E4 = EqRel({α, µ, β, ϵ, ζ, η}, (Dex\R4)), where β = (a2, a3) and η = (p7, p8). One can verify that W4 ∈ Sol(Dex, Σex) and W3 ≺MER W4 (while W4 ≺DEL W3 and W3 and W4 are incomparable w.r.t. the ⪯PAR preorder).

Overall, we obtain the following: SolPAR(Dex,Σex) = {W1,W2,W3,W4}, SolDEL(Dex,Σex) = {W1,W2,W3}, and SolMER(Dex, Σex) = {W1, W2, W4}.

We conclude this section by situating REPLACE w.r.t. existing frameworks. First, observe that for any databasespecification pair (D, Σ), we have (∅, E) ∈ SolDEL(D, Σ) iff (∅, E) ∈ SolPAR(D, Σ) iff E is a maximal ER solution in the sense of [Bienvenu et al., 2022, Definition 3]. Thus, the maximal solutions considered in LACE can be seen as special case of ⪯DEL- and ⪯PAR-optimal solutions. It is not hard to see that an analogous property does not hold for ⪯MER preorder.

Next we relate REPLACE solutions with the subset repairs employed in consistent query answering. Consider any database-specification pair (D,Σ) such that Σ = 〈∅,∆〉. Then, SolMER(D, Σ), SolDEL(D, Σ), and SolPAR(D, Σ) all coincide and contain only solutions of the form (R, trivE), where trivE = {(c, c) | c ∈ dom(D \ R)}. It is readily verified that (R, trivE) ∈ SolMER(D,Σ) = SolDEL(D,Σ) = SolPAR(D, Σ) iff D \ R is a repair in the sense of [Chomicki and Marcinkowski, 2005, Definition 2.2].

5 Reasoning about Solutions

In this section, we analyze the computational complexity of the central decision problems associated with the REPLACE framework, namely, checking whether a given set of merges and deletions is an (optimal) solution, and whether a candidate tuple is a certain or possible answer w.r.t. the space of optimal solutions. As is common when considering data-centric tasks, we employ the data complexity measure [Vardi, 1982], i.e. complexity is measured w.r.t. the size of the database D (and also the pair W = (R, E) when it is part of the input).

Our results, summarized in Table 1, consider the three notions of optimality, as well as the impact of adopting a syntactically restricted form of specification (defined further).

5.1 Solution Recognition

We first consider the solution recognition problem (REC): given Σ, D, and W, decide whether W ∈ Sol(D,Σ). Tractability easily follows from the P-completeness of the analogous problem for ERSol [Bienvenu et al., 2022]:

Theorem 1. REC is P-complete.

Next we determine the complexity of the problem XOPTREC of deciding whether W ∈ SolX(D,Σ), where X ∈ {MER, DEL, PAR} is the chosen optimality notion.

Theorem 2. X-OPTREC is coNP-complete for any X ∈ {MER, DEL, PAR}.

The upper bounds employ a guess-and-check approach, exploiting Theorem 1. We transferred an existing coNP lower bound for maximal ER solutions to X-OPTREC when X ∈ {DEL, PAR}, while MER-OPTREC required a new proof.

5.2 Query Answering

In an ideal world, we would determine which solution corresponds to the true data, and query the resulting clean instance. When this is infeasible, due to lack of time or knowledge, a reasonable approach is to query the space of optimal solutions to identify those tuples that are answers w.r.t. every solution (in line with CQA semantics and the skeptical mode of inference employed in non-monotonic reasoning) or at least one solution (a form of credulous / brave reasoning).

This leads us to define the following notions of certain and possible answers. Note that given a solution W = (R, E) to (D, Σ), we shall use q(D,W) to refer to q(D \ R, E).

Definition 5. Given a DQ specification Σ, database D, and query q, all over schema S, and X ∈ {MER, DEL, PAR}, we say that a tuple c of constants is an X-certain (resp. Xpossible) answer to q on D w.r.t. Σ if c ∈ q(D,W) for every (resp. some) W ∈ SolX(D, Σ). We use X-certAns(q, D, Σ) and X-possAns(q, D, Σ) to denote, respectively, the set of Xcertain answers and X-possible answers to q on D w.r.t. Σ.

Example 6. First consider the query q1 ex (x, y, z) = ∃t, v, e, m.Paper(x, t, y, 2023, v, e) ∧ Author(y, m, z), which returns the id of papers written in 2023 along with the institution and the id of its first author. For the tuple t = (p6, a3, Tokyo), we have the following:

• t ∈ MER-certAns(q1 ex , Dex, Σex);
• t ̸∈ DEL-certAns(q1 ex ,Dex,Σex), as t ̸∈ q1 ex (Dex, W3), hence also t ̸∈ PAR-certAns(q1 ex , Dex, Σex);
• t∈X-possAns(q1 ex , Dex, Σex) (X ∈{MER, DEL, PAR}).

Next let q2 ex (x, y) = ∃t, f , v, m, i. Paper(x, t, f , 2012, v, y) ∧ Author(y,m, i) be the query that returns the ids of papers written in 2012 and the venue chair. Observe that XcertAns(q2 ex ,Dex,Σex) = ∅ for X ∈ {MER, PAR}, while DEL-certAns(q2 ex ,Dex,Σex) = {(p5, a3)}. Notice moreover that X-possAns(q2 ex ,Dex,Σex) = {(p5, a2), (p5, a3)} for each X ∈ {MER, DEL, PAR}.

Our next theorem provides the complexity of the decision problems X-CERTANS and X-POSSANS of checking whether a given tuple of constants belongs to the set of Xcertain answers and X-possible answers, respectively. We remind the reader that whenever we speak of queries we refer to CQs.

Theorem 3. X-CERTANS is Πp2 -complete for any X ∈ {MER, DEL, PAR}, PAR-POSSANS is NP-complete, and XPOSSANS is Σp2 -complete for X ∈ {MER, DEL}.

The Πp2 and Σp2 membership proofs involve guessing a potential solution W that contains / omit the query tuple and calling an NP oracle to check that W is indeed an optimal solution. The NP upper bound for PAR-POSSANS relies upon showing that it is sufficient to check that W is a solution, rather than a PAR-optimal solution. This is because c ∈ q(D,W) implies c ∈ q(D,W ′ ) for any W ′ such that W ≺PAR W ′ (no such property holds for ≺MER and ≺DEL). While some lower bounds were adapted from analogous results for LACE, others require new ingredients.

5.3 Restricted Specifications

The preceding results show that it is computationally challenging to reason about optimal solutions. Faced with a similar situation, Bienvenu et al. (2022) explored restricted DQ specifications, in which inequality atoms are disallowed in the denial constraints. While such specifications cannot capture keys and functional dependencies, they do allow for other meaningful forms of constraints, e.g. class and property disjointness statements commonly used for Semantic Web data.

Do restricted DQ specifications yield better complexity in our setting? For REC, MER-OPTREC, MER-CERTANS, MER-POSSANS, and PAR-POSSANS, the answer is no, as the lower bound proofs employ restricted DQ specifications. However, for the remaining decision problems, we do find a drop in complexity (under the usual complexity assumptions).

Theorem 4. For restricted DQ specifications, we have that:

• DEL-OPTREC and PAR-OPTREC are P-complete;
• X-CERTANS is coNP-complete for X ∈ {DEL, PAR} and DEL-POSSANS is NP-complete;

Intuitively, this lower complexity is due to constraint violations being preserved under improvements, i.e. if δ is a denial constraint without ̸=-atoms and both W = (R, E) and W ′ = (R′ ,E′ ) belong to Sol(D,E), then (D \ R)E ̸|= δ implies (D \ R′ )E′ ̸|= δ whenever E ⊆ E′ and R′ ⊆ R.

5.4 Comparison with LACE and CQA

Comparing with LACE, we note that in almost all cases, the addition of delete operations does not affect the complexity of recognizing (maximal / optimal) solutions or certain and possible answers. The main exception is if we consider ≺MER-optimal solutions coupled with restricted specifications, where all problems are one level higher in the polynomial hierarchy than the corresponding problems in LACE.

Adding merges to CQA brings a notable increase in complexity. Indeed, the certain query answering and optimal solution recognition tasks are one level higher than the corresponding CQA and repair checking tasks, if one considers general specifications or restricted specifications with the ≺MER preorder. An even larger complexity jump is observed for possible query answering, as the analogous task w.r.t. repairs is easily seen to have polynomial data complexity.

6 Most Informative Answers

While our notions of certain and possible answers (and the corresponding notions in [Bienvenu et al., 2022]) provide a natural way of querying the space of optimal solutions, they present one major drawback from an end user's perspective: the query results may contain multiple distinct tuples that are equivalent w.r.t. the considered solutions, as illustrated next.

Example 7. Consider a scenario in which we have the database-specification pair (D, Σ), the database D contains facts P(c1, c2) and P(c3, c4), and W = (∅,E) with E = EqRel({(c1, c3), (c2, c4)},D) is the only ⪯X-optimal solution for (D,Σ), for every X ∈ {MER, DEL, PAR}. Then, for the query q(x1, x2) = P(x1, x2) and for any X ∈ {MER, DEL, PAR}, we have four X-certain/possible answers to q on D w.r.t. Σ, namely: (c1, c2), (c1, c4), (c3, c2), and (c3, c4). These tuples could be more concisely presented as a a single tuple of sets of constants ({c1, c3}, {c2, c4}).

To address this issue and present query results with as much information (and as little repetition) as possible, we introduce the new notions of most informative (certain / possible) answers. The main idea, evoked in the example, that answers to queries now consist of tuples of sets of constants, each set comprising constants in the same equivalence relation w.r.t. the solution(s) under consideration.

Definition 6. Given a solution W = (R,E) for (D,Σ), an n-ary query q, and an n-tuple C = (C1, . . . ,Cn) of sets of constants from D, we call C a set-answer to q on D w.r.t. W if the following holds: (i) Ci contains constants in the same equivalence class in E, for 1 ≤ i ≤ n, and (ii) there exists a tuple of constants c = (c1, . . . , cn) ∈ q(D,W) such that ci ∈ Ci for every 1 ≤ i ≤ n. We denote by q(D,W) the set of set-answers to q on D w.r.t. W.

Definition 7. For X ∈ {MER, DEL, PAR}, we say that a tuple C of sets of constants is a X-certain set-answer (resp. Xpossible set-answer) to q on D w.r.t. Σ if C ∈ q(D,W) for every (resp. some) W ∈ SolX(D,W). We use XSetCert(q,D,Σ) (resp. X-SetPoss(q,D,Σ)) for the set of X-certain (resp. X-possible) set-answers to q on D w.r.t. Σ.

Example 8. Recall the queries q1 ex and q2 ex from Example 6. The tuple T = ({p6}, {a2, a3}, {Tokyo}) ∈ MERSetCert(q1 ex , Dex, Σex) while T ̸∈ X-SetCert(q1 ex , Dex, Σex) for both X = DEL and X = PAR.

As another example, we have that ({p5}, {a2, a3}) ∈ XSetPoss(q2 ex , Dex, Σex) for each X ∈ {MER, DEL, PAR}.

Among the X-certain and X-possible set-answers, we are interested in presenting the most informative ones. More formally, for two n-tuples C = 〈C1, . . . ,Cn〉 and C′ = 〈C ′1 , . . . ,C ′n 〉 of sets of constants, we say that C′ is strictly more informative than C if (i) Ci ⊆ C ′ i for every 1 ≤ i ≤ n, and (ii) Ci ⊂ C ′ i for some 1 ≤ i ≤ n. Given a set S of ntuples of sets of constants, we say that C ∈ S is most informative in S if there is no C′ ∈ S that is strictly more informative than C. With these notions in hand, we can now formally define most informative certain and possible answers.

Definition 8. Given a DQ specification Σ, database D, and query q, all over schema S, and X ∈ {MER, DEL, PAR}, we say that a tuple C of sets of constants from D is a most informative X-certain answer (resp. most informative X-possible answer) to q on D w.r.t. Σ if C is most informative in XSetCert(q,D,Σ) (resp. in X-SetPoss(q,D,Σ)). We denote by X-MIcertAns(q, D, Σ) (resp. X-MIpossAns(q, D, Σ)) the set of most informative X-certain (resp. X-possible) answers to q on D w.r.t. Σ.

Example 9. Observe that T1 = ({p6}, {a2}, {Tokyo}) ∈ X-MIcertAns(q1 ex ,Dex,Σex) for X ∈ {DEL, PAR}, while T1 ̸∈ MER-MIcertAns(q1 ex ,Dex,Σex) because the tuple T0 = ({p6}, {a2, a3}, {Tokyo}) in MERSetCert(q1 ex ,Dex,Σex) is strictly more informative than T1. In fact, T0 ∈ MER-MIcertAns(q1 ex ,Dex,Σex). Analogously, one can see that T2 = ({p6, p7}, {a1, a2}, {Tokyo}) is such that T2 ∈ X-MIpossAns(q1 ex ,Dex,Σex) for both X = DEL and X = PAR, while T2 ̸∈ MER-MIcertAns(q1 ex , Dex, Σex) because T3 = ({p6, p7, p8}, {a1, a2, a3}, {Tokyo}) occurs in MER-SetPoss(q1 ex ,Dex,Σex) and is strictly more informative than T2. In fact, T3 ∈ MER-MIpossAns(q1 ex , Dex, Σex). For query q2 ex , X-MIcertAns(q2 ex ,Dex,Σex) = ∅ for X ∈ {MER, PAR} while DEL-MIcertAns(q2 ex ,Dex,Σex) = {({p5}, {a3})}. As for possible answers, X-MIpossAns = {({p5}, {a2, a3})} for each X ∈ {MER, DEL, PAR}.

While X-certAns(q,D,Σ) ⊆ X-possAns(q,D,Σ), the inclusion X-MIcertAns(q, D, Σ) ⊆ X-MIpossAns(q, D, Σ) does not hold in general. However, we have the following related property: if C ∈ X-MIcertAns(q,D,Σ), then either C ∈ X-MIpossAns(q,D,Σ) or there exists C′ ∈ XMIpossAns(q, D, Σ) that is strictly more informative than C.

We now consider the decision problems X-MIPOSSANS and X-MIPOSSANS of checking whether a given tuple of sets of constants is a most informative X-certain (respectively, Xpossible) answer. We find that adopting the most informative notions of answers leads to higher complexity compared to the (plain) notions of certain and possible answers.

Theorem 5. X-MICERTANS is DP2-complete 1 for any X ∈ {MER, DEL, PAR}, X-MIPOSSANS is DP2-complete for X ∈ {MER, DEL}, and PAR-MIPOSSANS is DP-complete.

The upper bounds rely on the fact that the set of yesinstances for X-MICERTANS is precisely the intersection of the yes-instances of X-SETCERT (decide whether C ∈ XSetCert(q, D, Σ)) and X-NOBETTERCERT (decides whether there is no C′ ∈ SetCert(q,D,Σ) strictly more informative than C). The latter can be solved by guessing a solution Wi for each possible 'minimal improvement' Ci of C and verifying that Ci ̸∈ q(D,Wi). Similar considerations apply for X-MIPOSSANS. Lower bounds rely on new reductions.

We conclude this section by considering the impact of adopting restricted specifications. While MER-MICERTANS, PAR-MIPOSSANS, and MER-MICERTANS retain their original complexity, the other problems enjoy lower complexity.

Theorem 6. For restricted DQ specifications, the decision problems DEL-MICERTANS, PAR-MICERTANS, and DELMIPOSSANS are DP-complete.

7 Conclusion and FutureWork

We presented REPLACE, a new holistic framework for (possibly recursive) collective entity resolution and repairing, which employs denial constraints coupled with (hard and soft) logical rules to infer merges. The semantics, based upon solutions that take the form of (coherent) sets of merges and deletions, generalizes both LACE and (subset) repairs. In the spirit of CQA, we studied how to query the space of (optimal) solutions. Our complexity analysis shows that while certain and possible answer recognition is harder than the analogous tasks for repairs, it is for the most part on par with existing results for LACE. We also explored an important question (not considered in LACE) of how to present the query results, which is non-trivial due to the merged constants, leading us to propose novel notions of most informative answers.

We view this work as a starting point, with many interesting questions left to explore. First, it could be natural to consider other reasoning tasks, such as identifying certain and possible merges and deletions, which could help guide users towards a unique solution. While some results can be transferred from query answering, other cases require further study. Next, we believe it would be interesting to explore extensions of REPLACE with quantitive information (weight or scores) associated to rules and facts, in particular, so that approximate weighted solutions could be generated. Finally, we would like to develop an efficient prototype based on logic-based technologies, such as answer set programming (ASP) [Gebser et al., 2012]. To this end, we could use LACE's ASP encoding as a steppingstone, but new insights will be needed to handle most informative certain answers, whose DP2 complexity goes beyond what is traditionally supported by ASP. It would also be interesting to use more informative similarity measures by adding ML predicates, in the style of [Deng et al., 2022].

1 We recall that the complexity classes DP (a.k.a. BH(2)) and DP2 (a.k.a. BH3(2)) are the second level of the Boolean hierarchy of NP sets and of Σp2 sets, respectively [Chang and Kadin, 1996].

Acknowledgements

This work has been supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014), by MUR under the PNRR project FAIR (PE0000013), and by the Royal Society (IES\R3\193236).