# Advances in Logic-Based Entity Resolution: Enhancing ASPEN with Local Merges and Optimality Criteria

Zhiliang Xiang, Meghyn Bienvenu, Gianluca Cima, Víctor Gutiérrez-Basulto, Yazmín Ibáñez-García

► To cite this version:

Zhiliang Xiang, Meghyn Bienvenu, Gianluca Cima, Víctor Gutiérrez-Basulto, Yazmín Ibáñez-García. Advances in Logic-Based Entity Resolution: Enhancing ASPEN with Local Merges and Optimality Criteria. KR 2025 - 22nd International Conference on Principles of Knowledge Representation and Reasoning, Nov 2025, Melbourne, Australia. hal-05352328

HAL Id: hal-05352328

https://hal.science/hal-05352328v1

Submitted on 6 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Advances in Logic-Based Entity Resolution: Enhancing ASPEN with Local Merges and Optimality Criteria

Zhiliang Xiang¹, Meghyn Bienvenu², Gianluca Cima³,

Víctor Gutiérrez-Basulto¹, Yazmín Ibáñez-García¹

¹Cardiff University, UK

²Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France

³Sapienza University of Rome, Italy
{xiangz6,gutierrezbasultov,ibanezgarciay}@cardiff.ac.uk, meghyn.bienvenu@labri.fr,
cima@diag.uniroma1.it

## Abstract

We present ASPEN⁺, which extends an existing ASP-based system, ASPEN, for collective entity resolution with two important functionalities: support for local merges and new optimality criteria for preferred solutions. Indeed, ASPEN only supports so-called global merges of entity-referring constants (e.g. author ids), in which all occurrences of matched constants are treated as equivalent and merged accordingly. However, it has been argued that when resolving data values, local merges are often more appropriate, as e.g. some instances of 'J. Lee' may refer to 'Joy Lee', while others should be matched with 'Jake Lee'. In addition to allowing such local merges, ASPEN⁺ offers new optimality criteria for selecting solutions, such as minimizing rule violations or maximizing the number of rules supporting a merge. Our main contributions are thus (1) the formalization and computational analysis of various notions of optimal solution, and (2) an extensive experimental evaluation on real-world datasets, demonstrating the effect of local merges and the new optimality criteria on both accuracy and runtime.

## 1 Introduction

Entity Resolution (ER) is a foundational task in computer science, concerned with identifying and merging references (constants) that refer to the same real-world entity (Singla and Domingos 2006). A variety of ER approaches have been explored, differing in their assumptions, the characteristics of the data they handle, and the techniques they employ (Christophides et al. 2021). One general and expressive variant, known as *collective ER*, involves the joint resolution of entity references across multiple interrelated tables (Bhattacharya and Getoor 2007). Declarative approaches have proven particularly well-suited for such complex, multi-relational settings, as they naturally leverage underlying relational dependencies (Bienvenu, Cima, and Gutiérrez-Basulto 2022; Deng et al. 2022; Fagin et al. 2023; Xiang et al. 2024). Nonetheless, and somewhat surprisingly, there are still relatively few logic-based systems that fully support collective ER (Deng et al. 2022; Xiang et al. 2024).

One such system is ASPEN (Xiang et al. 2024), recently developed within the knowledge representation and reasoning community using answer set programming (ASP) (Brewka, Eiter, and Truszczyński 2011; Gebser et

al. 2012; Lifschitz 2019). ASPEN implements the LACE framework (Bienvenu, Cima, and Gutiérrez-Basulto 2022) for collective ER, a logical approach that supports recursive, global, explainable, and constraint-aware ER. ASPEN builds on the foundational result that LACE solutions can be faithfully represented using ASP stable models. It extends this theoretical insight by tackling key implementation challenges. Most notably, it addresses the efficient computation of similarity facts within rule bodies. As proposed in LACE, it computes not only individual ER solutions but also an entire space of set-maximal solutions, enabling the derivation of both possible and certain merges. To support scalable reasoning, ASPEN approximates hard-to-compute merge sets (e.g., possible and certain merges) using lower- and upper-bound variants that retain formal guarantees. ASPEN supports explanatory reasoning using xclingo (Cabalar and Muñiz 2023), offering justifications for each merge via proof trees, making it a justifiable ER system. Experimentally, ASPEN demonstrates strong performance, particularly in multi-relational settings, outperforming existing rule-based systems like Magellan (Konda et al. 2016) and JedAI (Papadakis et al. 2020) in F1-score across several datasets. It effectively leverages recursion to uncover deeper merges, and its optimized similarity computation approach reduces memory usage by up to 99.6%, when compared to a naive method. Overall, despite higher computation times, ASPEN proves competitive and scalable for complex, real-world ER settings.

The introduction of ASPEN, along with the public release of its code and associated data, opens up new opportunities to further explore and evaluate ASP techniques in the context of ER. In this paper, we introduce ASPEN⁺, which extends ASPEN with two important functionalities: support for local merges and new optimality criteria for preferred solutions. In the original ASPEN, constant identification is global: all occurrences of matched constants are merged, not just those involved in the derivation of the match. This global semantics is particularly well suited for merging constants that serve as entity references, such as author names or paper IDs, and has been adopted in several logic-based frameworks (Arasu, Ré, and Suciu 2009; Burdick et al. 2016; Deng et al. 2022; Fagin et al. 2023;
Bienvenu, Cima, and Gutiérrez-Basulto 2022). However, it has been argued that when resolving data values, local merges are often more appropriate (Bertossi, Kolahi, and Lakshmanan 2013; Fan 2008; Fan et al. 2009; Bienvenu et al. 2023; Fagin et al. 2023). Indeed, a local semantics allows some instances of ‘J. Lee’ may refer to ‘Joy Lee’, while others should be matched with ‘Jake Lee’. ASPEN$^+$ also introduces additional optimality criteria for defining preferred solutions, extending beyond the approach used in ASPEN, which prioritizes solutions with the greatest number of merges (w.r.t. set inclusion). It supports seven optimality criteria, such as minimizing rule violations or maximizing the number of rules supporting a merge. Our main contributions are thus (1) the formalization of various notions of optimal solution and computational analysis of the problem of recognizing optimal solutions w.r.t. the chosen optimality criteria, and (2) an extensive experimental evaluation on real-world datasets, demonstrating the effect of local merges and the new optimality criteria on both accuracy and runtime.

**Related Work** Several declarative systems for ER have been proposed, including Magellan (Konda et al. 2016) and JedAI (Papadakis et al. 2020). However, most of these systems are designed for pairwise ER. Apart from ASPEN, the most closely related logic-based ER approaches supporting multi-relational settings and recursion are Dedupalog (Arasu, Ré, and Suciu 2009) and MRL (Deng et al. 2022). Nevertheless, these implementations are not publicly available and differ from ASPEN$^+$ in key aspects.: i) ASPEN$^+$ explores a space of preferred solutions under multiple optimality criteria, rather than producing a single solution; ii) it supports both local and global merges, unlike these systems which are limited to global merges only. Note that, like ASPEN, ASPEN$^+$ is an implementation of the LACE$^+$ framework (Bienvenu et al. 2023), which extends LACE to support local roles. In addition, ASPEN$^+$ goes beyond LACE$^+$ by exploring a range of optimality criteria. We also note in passing that the framework proposed by Fagin et al. 2023, like LACE$^+$, supports both global and local merges, although no system currently implements it.

Programs, code and data of ASPEN$^+$ are available at (Xiang 2025)

## 2 Preliminaries

**Databases** We assume an infinite set of constants C partitioned into three disjoint sets: a set of objects, O, serving as references to real-world entities, a set V of values, and a set TID of tuple identifiers (tids), used to annotate database facts. A (database) schema S consists of a finite set of relation symbols R, each having an associated arity k ∈ N and type vector {O, V}$^k$. We write R/k ∈ S to indicate that R has arity k and denote by type(R, i) the ith element of R's type vector. If type(R, i) = O (resp. V), we call i an object (resp. value) position of R.

A TID-annotated database over a schema S is a finite set of facts D of the form R(c₀, c₁, ..., cₖ), where R/k ∈ S, c₀ ∈ TID and cᵢ ∈ O ∪ V for 1 ≤ i ≤ k. We require that each t ∈ TID occurs at most once in D. For simplicity, we refer to such a set of facts as a database.

We write Obj(D) to denote the set of objects occurring in D and Cells(D) to denote the set of values cells of D: {⟨t, i⟩ | R(t, c₁, ..., cₖ) ∈ D, type(R, i) = V}.

**Queries** A conjunctive query (CQ) takes the form q(⃗x) = ∃⃗y.φ(⃗x, ⃗y), where ⃗x and ⃗y are disjoint tuples of variables, and φ(⃗x, ⃗y) is a conjunction of relational atoms of the form R(t₀, t₁, ..., tₖ) where R/k is a relation symbol and tᵢ ∈ C ∪ ⃗x ∪ ⃗y for 0 ≤ i ≤ k, as well as similarity atoms.

**Constraints** We will consider denial constraints (DC) of the form ∀⃗x.¬φ(⃗x), where φ(⃗x) is a conjunction of atoms which are either relational atoms or inequality atoms t₁ ≠ t₂ with variables from ⃗x. A database D satisfies a DC if and only if ∃⃗x.φ(⃗x) is not satisfied in D. Notably, DCs generalize the well-known class of functional dependencies (FDs).

## 3 LACE$^+$ Entity Resolution Framework

In this section, we briefly recall LACE$^+$ and introduce new optimality criteria for selecting preferred ER solutions. Due to space constraints, the presentation focuses solely on the material relevant to ASPEN$^+$. For a complete account, we refer the interested reader to (Bienvenu et al. 2023).

### 3.1 ER Specifications

Entity resolution is concerned with identifying pairs of syntactically distinct database constants that refer to the same thing (such pairs will be called merges). In LACE$^+$, a distinction is made between objects and values, and thus the attributes of database relations are typed as object or value attributes. Objects are references to real-world entities, e.g. paper and author identifiers, whereas values specify the properties of such entities, e.g. name and phone number of authors. Crucially, all occurrences of an object (possibly across different database tables) are assumed to refer to the same entity. This means that if objects o and o' are deemed to be the same, then we merge all occurrences of o and o', while the meaning of a value can depend on its context, so e.g. one occurrence of a value J. Lee might be merged with Joy Lee, while another could merge with Jack Lee (or remain unmerged). For this reason, objects and values need to be handled differently during the ER process.

**Rules for Objects** We use hard and soft rules for objects to identify pairs of objects that must or might refer to the same real-world entity. Such rules have the following forms:

$$q(x, y) \Rightarrow \text{EqO}(x, y) \qquad q(x, y) \rightarrow \text{EqO}(x, y)$$

where q(x, y) is a CQ whose free variables x and y occur only in object positions. Note that EqO is a special relation symbol used to store the merged pairs of objects. While hard and soft rules have essentially the same syntactic form (except for the type of arrow), they differ in meaning: hard rules indicate pairs of objects that must be merged, whereas soft rules indicate likely merges.

**Rules for Values** We use hard and soft rules for values to handle local identifications of values which are non-identical representations of the same information. Such rules take the following forms (using ⇒ for hard rules, → for soft rules):

$$q(x_t, y_t) \rightarrow \text{EqV}(\langle x_t, i \rangle, \langle y_t, j \rangle) \qquad \rightarrow \in \{\Rightarrow, \rightarrow\}$$
where $q(x_t, y_t)$ is a CQ whose variables $x_t$ and $y_t$ each occur once in $q$ in position 0 of atoms with relations $R_x$ and $R_y$ respectively, and $i$ and $j$ are value positions of $R_x$ and $R_y$. Here the special relation symbol EqV is used to store pairs of value cells (i.e. tuple-position pairs) which have been merged. Intuitively, the above hard (resp. soft) rule states that a pair of tids $(t_1, t_2)$ being an answer to $q$ provides sufficient (resp. reasonable) evidence for concluding that the values in cells $\langle x_t, i \rangle$ and $\langle y_t, i \rangle$ are non-identical representations of the same information.

**Specifications** In LACE$^+$, ER specifications consist of hard and soft rules for objects and values, together with a set of denial constraints that define what counts as a consistent database.

**Definition 1.** A LACE$^+$ entity resolution (ER) specification $\Sigma$ takes the form $\Sigma = \langle \Gamma_O, \Gamma_V, \Delta \rangle$, where $\Gamma_O = \Gamma_h^o \cup \Gamma_s^o$ is a finite set of hard and soft rules for objects, $\Gamma_V = \Gamma_h^v \cup \Gamma_s^v$ is a finite set of hard and soft rules for values, and $\Delta$ is a finite set of denial constraints.

**Example 1.** Figure 1b shows a specification $\Sigma$. The soft rule $\sigma_o^1$ suggests that author records with similar names and matching birth date and place (dob, pob) likely refer to the same author. The hard rule $\rho_v^1$ enforces merging similar names for identical author IDs, preserving the functional dependency from constraint $\delta_1$.

## 3.2 ER Solutions

In LACE$^+$, a solution to an ER specification $\Sigma$ and database $D$ takes the form of a pair $\langle E, V \rangle$, where $E$ is an equivalence relation over $Obj(D)$ and $V$ is an equivalence relation over $Cells(D)$. Solutions thus specify which pairs of objects and which pairs of value cells are deemed to be the same. Naturally, the rules and constraints of the specification impose requirements on $E$ and $V$. Every solution must be obtained by repeatedly applying the hard and soft rules for objects and values, choosing to stop when no further hard rule can be applied and the denial constraints are satisfied. Importantly, the database and equivalence relations are updated to reflect the already applied rules, which can lead to new rules being applicable and/or constraints becoming (un)satisfied.

The formal definition of solution relies upon the notion of an extended database $D_{E,V}$ induced by $\langle E, V \rangle$. Basically, every occurrence of an object $o$ in the original database $D$ is replaced by the set of objects $\{o' \mid (o, o') \in E\}$ and the value in cell $\langle t, i \rangle \in Cells(D)$ is replaced by the set of values occurring in the merged cells $\{\langle t', i' \rangle \mid (\langle t, i \rangle, \langle t', i' \rangle) \in V\}$ (the tuple identifiers in position 0 are left untouched). The semantics of queries and constraints are then suitably adapted to handle such extended databases, whose cells now contain sets of constants rather than single constants (we refer readers to (Bienvenu et al. 2023) for the details). We say that a pair of objects $(o, o')$ is active in $D_{E,V}$ w.r.t. a (hard or soft) rule for objects $q(x, y) \to EqO(x, y)$ just in the case that $(o, o')$ is an answer to $q(x, y)$ evaluated over $D_{E,V}$. We also say that $D_{E,V}$ satisfies a (hard or soft) rule for objects $r = q(x, y) \to EqO(x, y)$ when all the pairs active in $D_{E,V}$ w.r.t. $r$ occur in $E$. We can define in a similar

fashion what it means for a pair $(\langle t, i \rangle, \langle t', i' \rangle)$ to be active in $D_{E,V}$ w.r.t. a rule for values as well as when $D_{E,V}$ satisfies a (hard or soft) rule for values. We write $D_{E,V} \models \Lambda$ when $D_{E,V}$ satisfies each $\lambda \in \Lambda$. Finally, we will use the notation EqRel($P, S$) for the smallest equivalence relation on $S$ that extends $P \subseteq S \times S$. We are now ready to recall the formal definition of solutions in LACE$^+$.

**Definition 2.** Given an ER specification $\Sigma = \langle \Gamma_O, \Gamma_V, \Delta \rangle$ and a database $D$, we call $\langle E, V \rangle$ a candidate solution for $(D, \Sigma)$ if it satisfies one of the following three conditions:

* $E = \text{EqRel}(\emptyset, \text{Obj}(D))$ and $V = \text{EqRel}(\emptyset, \text{Cells}(D))$;

* $E = \text{EqRel}(E' \cup \{(o, o')\}, \text{Obj}(D))$, where $\langle E', V \rangle$ is a candidate solution for $(D, \Sigma)$ and $(o, o')$ is active in $D_{E,V}$ w.r.t. some rule $r \in \Gamma_O$;

* $V = \text{EqRel}(V' \cup \{(\langle t, i \rangle, \langle t', i' \rangle)\}, \text{Cells}(D))$, where $\langle E, V' \rangle$ is a candidate solution for $(D, \Sigma)$ and $(\langle t, i \rangle, \langle t', i' \rangle)$ is active in $D_{E,V}$ w.r.t. some rule $r \in \Gamma_V$.

A solution for $(D, \Sigma)$ is a candidate solution $\langle E, V \rangle$ such that (a) $D_{E,V} \models \Gamma_h^o$, (b) $D_{E,V} \models \Gamma_h^v$, and (c) $D_{E,V} \models \Delta$. We use $\text{Sol}(D, \Sigma)$ for the set of solutions for $(D, \Sigma)$.

**Example 2.** Consider the database $D$ and specification $\Sigma$ in Figure 1. A trivial candidate solution is $\langle E_0, V_0 \rangle$, with $E_0 = \text{EqRel}(\emptyset, \text{Obj}(D))$ and $V_0 = \text{EqRel}(\emptyset, \text{Cells}(D))$. Note that $(a_1, a_2)$ is active in $D_{E_0, V_0}$ w.r.t. $\sigma_o^1$. Let, $E_1 = \text{EqRel}(E_0 \cup \{(a_1, a_2)\}, \text{Obj}(D))$. However, this causes a violation of $\delta^1$ due to differing names for the same aid in $t_1$ and $t_2$. Applying $\rho_v^1$ merges cells $\langle t_1, 2 \rangle$ and $\langle t_2, 2 \rangle$, yielding $V_1 = \text{EqRel}(V_0 \cup \{(\langle t_1, 2 \rangle, \langle t_2, 2 \rangle)\}, \text{Cells}(D))$. The resulting induced database satisfies $\delta^1$, but $(\langle t_4, 2 \rangle, \langle t_5, 2 \rangle)$ is still active in $D_{E_1, V_1}$ w.r.t. $\sigma_v^2$, allowing the possibility to extend $V_1$ to $V_2 = \text{EqRel}(V_1 \cup \{(\langle t_4, 2 \rangle, \langle t_5, 2 \rangle)\}, \text{Cells}(D))$. Note that, $\langle E_0, V_0 \rangle$, $\langle E_1, V_1 \rangle$ and $\langle E_1, V_2 \rangle$ are all solutions for $(D, \Sigma)$, as their corresponding induced databases satisfy all denial constraints and hard rules in the specification $\Sigma$, whereas $\langle E_1, V_0 \rangle$ is not, as it induced database violated $\delta^1$.

## 3.3 Optimality Criteria for ER Solutions

In general, a LACE$^+$ specification may give rise to zero, one, or many solutions. The absence of solutions results from constraint violations that cannot be resolved through allowed merges, while multiple solutions arise from the choice of which soft rule applications to perform (as the constraints may block some combinations of merges). In the original work on LACE$^+$, a notion of maximal solution was introduced to focus on solutions which contain the most merges (w.r.t. set inclusion). While this notion is quite reasonable, other natural optimality criteria can be used to select preferred solutions. Indeed, we may want to give more importance to a merge that is supported by multiple rules, or compare solutions based upon soft rule violations.

To formalize these alternative criteria, we introduce the notation $\text{actP}(D, E, V, \Gamma)$ for the set of all $(p, r)$ such that pair $p$ is active in $D_{E,V}$ w.r.t. rule $r \in \Gamma$. Our proposed optimality criteria are obtained by associating each solution
<table><thead><tr><th colspan="5">Author(tid, aid, name, dob, pob)</th></tr><tr><th>tid</th><th>aid</th><th>name</th><th>dob</th><th>pob</th></tr></thead><tbody><tr><td>t<sub>1</sub></td><td>a<sub>1</sub></td><td>A. Turing</td><td>23/07/1912</td><td>London</td></tr><tr><td>t<sub>2</sub></td><td>a<sub>2</sub></td><td>Alan Turing</td><td>23/07/1912</td><td>London</td></tr><tr><td>t<sub>3</sub></td><td>a<sub>3</sub></td><td>Clerk Maxwell</td><td>13/06/1831</td><td>Edinburgh</td></tr></tbody></table>

<table><thead><tr><th colspan="3">Awarded(tid, aid, awrd)</th></tr><tr><th>tid</th><th>aid</th><th>awrd</th></tr></thead><tbody><tr><td>t<sub>4</sub></td><td>a<sub>1</sub></td><td>Smith's Prize(1936)</td></tr><tr><td>t<sub>5</sub></td><td>a<sub>2</sub></td><td>Smith's Prize</td></tr><tr><td>t<sub>6</sub></td><td>a<sub>3</sub></td><td>Smith's Prize</td></tr></tbody></table>

The similarity predicate $\approx$ is such that A. Turing $\approx$ Alan Turing and Smith's Prize $\approx$ Smith's Prize(1936)

(a) Database $D$ over the schema $S = \{\text{Author}/4, \text{Awarded}/2\}$

$$ \delta^1 = \forall x_t, y_t, y, n_1, n_2, d_1, d_2, p_1, p_2. \neg (\text{Author}(x_t, y, n_1, d_1, p_1) \land \text{Author}(y_t, y, n_2, d_2, p_2) \land n_1 \neq n_2) $$

$$ \sigma_o^1 = \exists x_t, y_t, n_1, n_2, d, p. \text{Author}(x_t, y_1, n_1, d, p) \land \text{Author}(y_t, y_2, n_2, d, p) \land n_1 \approx n_2 \longrightarrow \text{EqO}(y_1, y_2) $$

$$ \rho_v^1 = \exists y, n_1, n_2, d_1, d_2, p_1, p_2. \text{Author}(x_t, y, n_1, d_1, p_1) \land \text{Author}(y_t, y, n_2, d_2, p_2) \land n_1 \approx n_2 \Rightarrow \text{EqV}(\langle x_t, 2 \rangle, \langle y_t, 2 \rangle) $$

$$ \sigma_v^2 = \exists y, z, w. \text{Awarded}(x_t, y, z) \land \text{Awarded}(y_t, y, w) \land z \approx w \longrightarrow \text{EqV}(\langle x_t, 2 \rangle, \langle y_t, 2 \rangle) $$

(b) LACE$^+$ ER specification $\Sigma = \langle \Gamma_O, \Gamma_V, \Delta \rangle$, with $\Gamma_O = \{\sigma_0^1\}$, $\Gamma_V = \{\rho_v^1, \sigma_v^2\}$ and $\Delta = \{\delta^1\}$

<table><thead><tr><th colspan="5">Author(tid, aid, name, dob, pob)</th></tr><tr><th>tid</th><th>aid</th><th>name</th><th>dob</th><th>pob</th></tr></thead><tbody><tr><td>t<sub>1</sub></td><td>ô<sub>1</sub></td><td>û<sub>1</sub></td><td>{23/07/1912}</td><td>{London}</td></tr><tr><td>t<sub>2</sub></td><td>ô<sub>1</sub></td><td>û<sub>1</sub></td><td>{23/07/1912}</td><td>{London}</td></tr><tr><td>t<sub>3</sub></td><td>{a<sub>3</sub>}</td><td>{Clerk Maxwell }</td><td>{13/06/1831}</td><td>{Edinburgh}</td></tr></tbody></table>

<table><thead><tr><th colspan="3">Awarded(tid, aid, awrd)</th></tr><tr><th>tid</th><th>aid</th><th>awrd</th></tr></thead><tbody><tr><td>t<sub>4</sub></td><td>ô<sub>1</sub></td><td>û<sub>2</sub></td></tr><tr><td>t<sub>5</sub></td><td>ô<sub>1</sub></td><td>û<sub>2</sub></td></tr><tr><td>t<sub>6</sub></td><td>{a<sub>3</sub>}</td><td>{Smith's Prize}</td></tr></tbody></table>

where $\hat{o}_1 = \{a_1, a_2\}$, $\hat{v}_1 = \{\text{A.Turing}, \text{Alan Turing}\}$ and $\hat{v}_2 = \{\text{Smith's Prize}, \text{Smith's Prize}(1936)\}$

(c) Extended database $D_{E,V}$ induced by the merges $(a_1, a_2) \in E$, and $(\langle t_1, 2 \rangle, \langle t_2, 2 \rangle), (\langle t_3, 2 \rangle, \langle t_4, 2 \rangle) \in V$

<caption>Figure 1: A solution to an ER specification in LACE$^+$</caption>

$\langle E, V \rangle$ with one of the following sets (using $\Gamma$ for $\Gamma_O \cup \Gamma_V$):

$$ \text{EQ}(E, V) = E \cup V $$

$$ \text{SUPP}(E, V) = \{ (p, r) \in \text{actP}(D, E, V, \Gamma) \mid p \in E \cup V \} $$

$$ \text{ABS}(E, V) = \{ p \mid (p, r) \in \text{actP}(D, E, V, \Gamma), p \notin E \cup V \} $$

$$ \text{VIOL}(E, V) = \{ (p, r) \in \text{actP}(D, E, V, \Gamma) \mid p \notin E \cup V \} $$

then apply either set-inclusion or cardinality maximization or minimization. Observe that $\text{SUPP}(E, V)$ refines $\text{EQ}(E, V)$ by indicating the supporting rules for merges. Likewise, $\text{ABS}(E, V)$ gives only the active but absent pairs, while $\text{VIOL}(E, V)$ records which soft rules the absent pair violates. The resulting optimality criteria are as follows:

* maxES/maxEC: maximize $\text{EQ}(E, V)$

* maxSS/maxSC: maximize $\text{SUPP}(E, V)$

* minAS/minAC: minimize $\text{ABS}(E, V)$

* minVS/minVC: minimize $\text{VIOL}(E, V)$

where the final $S$ (resp. $C$) indicates comparison using set-inclusion (resp. set cardinality). For example, a solution $\langle E, V \rangle$ is minVC-optimal if there is no other solution $\langle E', V' \rangle$ such that $\text{VIOL}(E', V') < \text{VIOL}(E, V)$. Note that maxES-optimal solutions correspond to the maximal solutions of (Bienvenu et al. 2023). See Appendix A for further intuitions on the criteria. Interestingly, the optimality criteria give rise to different sets of optimal solutions, except for maxES and maxSS, which actually coincide. As a result, there are seven distinct optimality criteria overall.

**Proposition 1.** All pairs of defined criteria produce different sets of optimal solutions, except for maxES and maxSS.

## 3.4 Recognizing Optimal Solutions

A key challenge is determining if a solution is optimal under a given criterion. This problem is coNP-complete in data complexity for maxES (Bienvenu et al. 2023), and we show the same for the other criteria.

**Theorem 1.** For all seven optimality criteria, recognition of optimal solutions is coNP-complete in data complexity.

*Proof sketch.* The upper bound is based on a guess-and-check procedure, analogous to the one in (Bienvenu et al. 2023) for maxES. We now give a reduction from the complement of 3SAT. We use the following fixed schema:

$$ S = \{ R_{fff}/3, R_{ftf}/3, R_{fttf}/3, R_{tfff}/3, R_{ttft}/3, R_{tttf}/3, R_{tft}/3, R_{ttt}/3, V/1, F/1, T/1, B/1 \} $$

with only object attributes. Given an input $\varphi = c_1 \land \dots \land c_m$ to 3SAT over variables $x_1, \dots, x_n$, where $c_i = \ell_{i,1} \lor \ell_{i,2} \lor \ell_{i,3}$, we construct an $S$-database $D^\varphi$ that contains:

* the fact $V(x_i)$ for each $i \in [1, n]$,

* the facts $T(1), F(0), B(0)$, and $B(1)$;

* for each clause $c_i = \ell_{i,1} \lor \ell_{i,2} \lor \ell_{i,3}$ in $\varphi$, the fact $R_{b_1b_2b_3}(x_{i,1}, x_{i,2}, x_{i,3})$ with $\ell_{i,j} = (\neg)x_{i,j}$ and $b_{i,j} = t$ (resp. $b_{i,j} = f$) if $\ell_{i,j}$ is a positive (resp. negative) literal

We consider the fixed ER specification $\Sigma_{3SAT} = \langle \Gamma_O, \emptyset, \Delta \rangle$, where $\Gamma_O$ contains a single soft rule for objects:

$$ \sigma = V(x) \land B(y) \longrightarrow \text{EqO}(x, y) $$
and $\Delta$ contains the following denial constraints (all the variables are implicitly universally quantified):

* $\delta_0 = \neg(F(y) \land T(y))$

* $\delta_1 = \neg(R_{ff}(y_1, y_2, y_3) \land T(y_1) \land T(y_2) \land T(y_3))$

* $\delta_2, \dots, \delta_8$ defined analogously to $\delta_1$, but for relations $R_{fft}$, $R_{ftf}$, $R_{ftt}$, $R_{tff}$, $R_{tft}$, $R_{ttt}$

* $\delta_9 = \neg(V(v) \land B(v) \land V(x) \land T(y) \land F(z) \land x \neq y \land x \neq z)$

The soft rule $\sigma$ allows a variable to merge with 0 or 1 (but not both due to $\delta_0$). Constraints $\delta_1$ to $\delta_8$ ensure that the chosen truth values do not violate any clause. Finally, constraint $\delta_9$ is used to ensure that if even one variable is merged with a truth value, using the sole soft rule $\sigma$, then every variable must be merged with a truth constant. Together, the constraints ensure that the soft rule can only be applied if the formula is satisfiable. It can thus be shown that $\varphi$ is unsatisfiable if and only if $\langle E_{triv}, \emptyset \rangle$ is an X-optimal solution for $(D^\varphi, \Sigma_{3SAT})$, where $E_{triv} = \text{EqRel}(\emptyset, \text{Obj}(D^\varphi))$ and X denotes any of the seven optimality criteria. $\square$

Interestingly, (Bienvenu et al. 2023) also studied the above problem in a *restricted setting*, which forbids the presence of inequality atoms in denial constraints. It was shown that, under this restriction, the problem becomes tractable for maxES, and in fact PTIME-complete in data complexity. We now show that the same holds for all optimality criteria based on set inclusion, but not for those based on cardinality.

**Theorem 2.** In the restricted setting, recognition of optimal solutions becomes PTIME-complete in data complexity for the optimality criteria maxES, minAS, and minVS, while it remains coNP-complete in data complexity for the optimality criteria maxEC, maxSC, minAC, and minVC.

**Proof sketch.** PTIME cases. We provide only a sketch of the upper bound for minAS. Given $(D, \Sigma)$ and $\langle E, V \rangle$, we check whether $\langle E, V \rangle \in \text{Sol}(D, \Sigma)$ (if not, then we return false and we are done). For each $p \in \text{ABS}(E, V)$, we then check whether $E \cup V \cup \{p\}$ can lead to a solution for $(D, \Sigma)$ having a strictly smaller set of active pairs than $\text{ABS}(E, V)$.

To perform this latter check, we iteratively include all the new pairs that become active due to some hard rule (which may already occur in the first iteration due to the addition of $p$ to $E \cup V$) as well as all the new pairs that become active due to some soft rule and were not originally in $\text{ABS}(E, V)$. Once a fixpoint is reached, we check whether the resulting $\langle E', V' \rangle$ is such that $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$, implying that $\langle E', V' \rangle$ is a solution such that $\text{ABS}(E', V') \subseteq \text{ABS}(E, V)$. If for some $p \in \text{ABS}(E, V)$ this is the case, then we return true; otherwise, we return false. The correctness of the above procedure is an immediate consequence of the following property which holds in the restricted setting: if $D_{E',V'} \not\models \Delta$ and $E' \cup V' \subseteq E'' \cup V''$, then $D_{E'',V''} \not\models \Delta$ as well. In particular, this means that if a pair $\langle E', V' \rangle$ obtained as above is such that $D_{E',V'} \not\models \Delta$, then it is not possible to obtain a solution for $(D, \Sigma)$ by adding further merges.

**coNP cases.** We give a reduction from the complement of 3SAT for the optimality criteria based on cardinality. We use the fixed schema $S' = S \cup \{H/2\}$ with only object

attributes, where $S$ is as in the proof of Thm 1. Given an input $\varphi$ to 3SAT over variables $x_1, \dots, x_n$, we construct an $S'$-database $D^\varphi = D^\varphi \cup \{H(c_1, c_2)\}$, where $D^\varphi$ is as in the proof of Theorem 1 while $c_1$ and $c_2$ are two fresh constants.

We consider the fixed ER specification $\Sigma'_{3SAT} = \langle \Gamma, \Delta \rangle$, where $\Gamma$ contains the soft rule $\sigma$ illustrated in the proof of Theorem 1 as well as the following additional soft rule:

* $\sigma' = H(x, y) \dashrightarrow \text{EqO}(x, y)$

and $\Delta$ contains the following denial constraints (all the variables are implicitly universally quantified):

* $\delta_0 = \neg(F(y) \land T(y))$

* $\delta_1 = \neg(R_{ff}(y_1, y_2, y_3) \land T(y_1) \land T(y_2) \land T(y_3) \land H(z, z))$

* $\delta_2, \dots, \delta_8$ defined analogously to $\delta_1$, but for relations $R_{fft}$, $R_{ftf}$, $R_{ftt}$, $R_{tff}$, $R_{tft}$, $R_{ttt}$

Essentially, the denial constraints are similar to those in the proof of Theorem 1, except that $\delta_1, \dots, \delta_8$ also contain the conjunct $H(z, z)$. This latter conjunct holds if and only if $c_1$ merges with $c_2$, which is possible due to $\sigma'$.

Now, let $E^0 = \{(x_i, 0) \mid 1 \le i \le n\}$ and $E = \text{EqRel}(E^0, \text{Obj}(D^\varphi))$. Note that $\langle E, \emptyset \rangle \in \text{Sol}(D^\varphi, \Sigma'_{3SAT})$ (because $(c_1, c_2) \notin E$) and $\text{ABS}(E, \emptyset) = \{(x_i, 1) \mid 1 \le i \le n\} \cup \{(c_1, c_2)\}$ (so, $|\text{ABS}(E, \emptyset)| = n+1$). The only way to get a solution $\langle E', \emptyset \rangle$ such that $|\text{ABS}(E', \emptyset)| < n+1$ is to merge $c_1$ and $c_2$ as well as all the variables with 0 or 1, which is possible if and only if $\varphi$ is satisfiable. It can thus be shown that $\varphi$ is unsatisfiable if and only if $\langle E, \emptyset \rangle$ is a minAC-optimal solution for $(D^\varphi, \Sigma'_{3SAT})$. Similar considerations apply for minVC, while for maxSC and maxEC we need to introduce a copy of each variable into a new unary predicate, an additional soft rule allowing to merge such copies with 0 or 1, and an additional denial constraints specifying that no variable and its copy are assigned to the same truth value. This guarantees that each maxEC-optimal (resp. maxSC-optimal) solution has the same cardinality. $\square$

# 4 ASP Encoding and Implementation

We assume basic familiarity with ASP, see (Gebser et al. 2012; Lifschitz 2019) for a detailed introduction. For our purposes, it suffices to focus on two constructs: normal rules, which have a single atom in the head, and constraints, which are rules with an empty head. We denote an ASP program (a set of such rules) by $\Pi$. Given a program $\Pi$, its grounding is the set of all ground instances of rules in $\Pi$, using the constants that appear in $\Pi$, and $SM(\Pi)$ denotes the set of all its stable models. In addition to solving the decision problem of checking whether $SM(\Pi)$ is non-empty, ASP-solvers also support advanced reasoning features such as enumerating the first $n$ stable models of $\Pi$, projecting models onto a specified set of atoms, and enumerating the first $n$ projected models (Gebser et al. 2018). ASP solvers also support optimization, allowing the computation (or enumeration) of $n$ elements of $SM(\Pi)$ that optimize a specified objective. For example, the directive `#minimize{w, t: L}` instructs the solver to minimize the weighted occurrence of tuples $t$ with weight $w$, subject to a list of literals $L$.
## 4.1 ASP Encoding of Solutions

Given an ER specification $\Sigma$ and a database $D$, we define an ASP program $\Pi_{(D,\Sigma)}$ containing all the facts in $D$, and an ASP rule for each (hard or soft) rule in $\Sigma$. Consider, for example, the specification $\Sigma'$ in Figure 1. Rules are translated as follows:

$$ \sigma_o^1 : \{ \text{eqo}(X, Y); \text{neqo}(X, Y) \} = 1 \leftarrow \text{author}(T, X, N, D, P), \\ \text{author}(T', Y, N', D, P), \text{val}(T, 2, N_1), \text{val}(T', 2, N_2), \\ \text{sim}(N_1, N_2, S), S \geq 95. $$

$$ \rho_v^1 : \text{eqv}(T, 2, T', 2) \leftarrow \text{eqo}(X, Y), \text{sim}(N_1, N_2, S), S \geq 95, \\ \text{author}(T, X, N, D, P), \text{author}(T', Y, N', D', P'), \\ \text{val}(T, 2, N_1), \text{val}(T', 2, N_2). $$

$$ \sigma_v^2 : \{ \text{eqv}(T, 2, T', 2); \text{neqv}(T, 2, T', 2) \} = 1 \leftarrow \text{eqo}(X, Y), \\ \text{awarded}(T, X, A), \text{awarded}(T', Y, A'), \text{val}(T, 2, A_1), \\ \text{val}(T', 2, A_2), \text{sim}(A_1, A_2, S), S \geq 95. $$

$$ \delta^1 : \perp \leftarrow \text{author}(T, X, N, D, P), \text{author}(T', Y, N', D', P'), \\ \text{eqo}(X, Y), \text{not } i(T, 2, T', 2). $$

In brief, each relational atom in the body of a rule is translated into an atom in the body of an ASP rule. The relations eqo and eqv represent mandatory object and value merges, respectively, thereby encoding solutions to $(D, \Sigma)$. Atoms of the form eqo(X, Y) in ASP rule bodies are used to encode that instantiations of X and Y are determined to denote the same object. To capture local semantics, the program includes facts of the form proj(T, i, V), indicating that the i-th position of tuple T has value V. Each proj fact is then assigned to a value set, identified by a cell, through local merges. This is formalized by the rule: $\text{val}(T, I, V) \leftarrow \text{proj}(T, I, V)$, $\text{eqv}(T', J, T, I)$. Importantly, similarity measures over value positions are evaluated not on the original variables in the relational atoms, but on pairs of fresh variables associated with val-atoms. The program also includes rules to ensure that both eqo and eqv form equivalence relations. Soft constraints are implemented using choice rules, allowing the inclusion of a pair $(X, Y)$ (or $(T, 2, T', 2)$, respectively) in either eqo (or eqv) or their respective negations neqo and neqv. Note that, in addition to the encoding format shown above, database atoms (facts) can also be represented in a reified format (see Appendix C.1).

**Practical changes** Following ASPEN, we represent similarity between constants using a ternary relation $sim_3(X, Y, S)$, where X and Y are the constants being compared, and S is the similarity score. Null values are represented using the atom empty(nan), in which, also as in ASPEN, the special constant nan is prevented from participating in any eqo (resp. neqo) and sim atoms. Cells with null values are allowed to participate in eqv. However, when equality between value positions is checked in a rule body, e.g., using $\text{val}(T, i, V)$, $\text{val}(T, j, V)$, we include the condition not empty(V) to exclude nulls from the comparison. This encoding blocks merges that would arise from treating two nulls as equivalent in rule bodies. Moreover, to capture the local semantics of inequalities in DCs, the encoding must ensure that the value sets of the two cells are disjoint. This requirement was overlooked in (Bienvenu et al. 2023). To this end, for each pair of variables v and v' associated with

cells $\langle t, i \rangle$ and $\langle t', j \rangle$, we add the following rule to capture value overlap:

$$ i(T, i, T', j) \leftarrow \text{val}(T, i, V), \text{val}(T', j, V), \text{not empty}(V). $$

This rule asserts that the predicate $i(T, i, T', j)$ holds if the two cells share a non-null value—that is, their value sets intersect. Consequently, inequality between the two positions can be expressed by the absence of such an intersection: not $i(T, i, T', j)$ like in $\delta^1$.

## 4.2 Computing Optimal Solutions

To compute solutions under the maxSC criterion, we extend the predicates eqo and eqv (or neqo and neqv) by adding an extra argument to represent the rule label. Each hard or soft rule in $\Pi_{(D,\Sigma)}$ is assigned a unique label constant, which is included in the head atom to distinguish merges derived from different rules. In rule bodies, any occurrence of eqo or eqv uses an anonymous variable in the label position to avoid hard-coding the label. Finally, for each rule labeled r that applies to objects (respectively, to values), we add a corresponding rule to $\Pi_{(D,\Sigma)}$: $w(X, Y, l, w) \leftarrow \text{eqo}(X, Y, r)$. (resp. $w(T, i, T', j, r, w) \leftarrow \text{eqv}(T, i, T', j, r)$). This assigns a weight w to merges derived from rule r.

The transformation for encoding rule violations under the minV criterion follows a similar approach. Specifically, the head atoms of hard rules are annotated with a default label constant $r'$, while those of soft rules are assigned distinct labels. For example, in Section 4.1, the head of the soft rule $\sigma_o^1$ is replaced by $\{ \text{eqo}(X, Y, \sigma_o^1); \text{neqo}(X, Y, \sigma_o^1) \} = 1$, similarly for $\sigma_v^2$. In contrast, the head of the hard rule $\rho_v^1$ is expanded with the default label $r'$. Moreover, rules that aggregate weights (e.g. those required for computing maxSC-optimal solutions) will not be included.

**Set-based optimisation** Set-based optimal solutions correspond to the stable models of $\Pi_{(D, \Sigma)}$ that contain an optimal set of target facts, depending on the chosen criterion: (1) a maximal set of eqo/eqv facts for maxE; (2) a minimal set of (labeled) neqo/neqv facts for minV and minA; (3) a maximal set of weighted facts for maxS. Following (Xiang et al. 2024), we utilise the ASP-based preference framework asprin (Brewka et al. 2023) to encode preferences over the stable models of a program. For our uses, we prefer a model $M'$ over $M$ if its projection on the target facts is a strict superset or subset of that of $M$, under the selected criterion.

Alternatively, domain-specific heuristics can be used to simulate set preferences by prioritizing the truth assignments of target facts (Rosa, Giunchiglia, and Maratea 2010; Gebser et al. 2013). We encode such heuristics using the statement \#heuristic t. [1, p], where t is a non-ground atom with the same predicate as the target facts for the chosen criterion, and $p \in \{\text{True, False}\}$ enables maximization or minimization, respectively.

**Cardinality-based optimisation** To compute cardinality-optimal solutions, we use the standard ASP optimization statement (Gebser et al. 2012), which minimizes (or maximizes) over the full tuple of arguments in the target atoms, using a default weight and priority of 1. For instance, to compute minVC, we include the following statements: \#minimize $\{1@1, X, Y, R : \text{neqo}(X, Y, R)\}$
and `#minimize{1@1, T, I, T', J, R: neqv(T, I, T', J, R)}`. Alternatively, preferences over the cardinality of target facts can be expressed using asprin, allowing the selection of models with either maximal or minimal cardinality depending on the chosen criterion. It is worth noting that while heuristic-driven solving and multi-threaded solving (Gebser, Kaufmann, and Schaub 2012) can both improve efficiency for optimization tasks, they are not compatible and cannot be used simultaneously.

## 4.3 Implementation

The workflow of ASPEN$^+$ begins with an ASP encoding of an ER specification, a CSV/TSV dataset containing duplicate and potentially corrupted values (e.g., nulls), and a set of command-line options. A preprocessing component computes similarity scores between relevant constant pairs based on attributes referenced in similarity atoms. These scores, along with the dataset, are passed to a program transformer, which rewrites the encoding into the ASPEN$^+$ format and generates ASP facts for both database tuples and similarities. Finally, the ER controller, built on `clingo`, computes optimal solutions according to the specified input options. See Appendix C for a workflow illustration.

We implemented ASPEN$^+$ by extending the open-source system ASPEN. Specifically, we developed a new program transformer, based on the translation procedure from (Bienvenu et al. 2023), which enables users to write ASP rules in the style of ER specifications without dealing with the underlying complexities of ASP encoding. Additionally, we enhanced the ER controller to support computing solutions under various optimality criteria, leveraging ASP features such as heuristic-driven solving.

# 5 Experiments

Our experiments focus on the following questions: (1) How does ASPEN$^+$ perform compared to SOTA systems that rely exclusively on global semantics? (2) What are the most efficient configurations for each optimization criterion? How do the resulting solutions vary in terms of performance? Can these solutions be enumerated efficiently? We also present qualitative studies that highlight the value of integrating both global and local semantics to address complex ER scenarios.

**Datasets and Metrics** We evaluate ASPEN$^+$ on six multi-relational datasets: (i) *Imdb*, based on the IMDB database, which includes entities such as artists and movies, and contains real-world duplicates; (ii) *Mu*, which features synthetic duplicates derived from the MusicBrainz database; (iii) *MuC*, a noisier version of *Mu* that retains the same duplicates but includes more missing values and syntactic variations; (iv) *Poke*, a larger-scale dataset from the Pokémon database, characterized by a greater number of tuples and more complex inter-table relationships. We also consider two synthetic datasets, *ImdbC* and *MuCC*. These are derived from *Imdb* and *MuC*, respectively, and contain a higher proportion of syntactic variants. Both datasets follow the variant generation protocol described in (Xiang et al. 2024). We use the standard accuracy metrics (Köpcke, Thor, and Rahm 2010) of *Precision* (*P*), *Recall* (*R*), and *F1-Score*

($F_1$). Sources and statistics for all datasets, as well as details of the experimental environment and similarity measures, are provided in Appendix D.1.

## 5.1 Combining Global and Local Semantics

**Setup** We evaluate the performance of ASPEN$^+$ against three baselines: ASPEN and two pairwise rule-based ER systems, Magellan (Konda et al. 2016) and JedAI (Papadakis et al. 2020). Both ASPEN$^+$ and ASPEN use the same global rules from ASPEN, with ASPEN$^+$ additionally incorporating local rules. Functional dependencies (FD) from the dataset schema are included in both ASP-based systems, provided they yield satisfiable ER programs. For Magellan and JedAI, we apply the same preconditions and similarity measures as in the ASP-based systems to ensure comparability. Like in ASPEN, we consider a single maxES-solution as default output of ASPEN$^+$. We report accuracy metrics and total running time $t_o$ for all systems. For the ASP-based systems, we also report grounding time ($t_g$), solving time ($t_s$), and the number of DCs (`#DC`) added without violating constraints. Results are shown in Table 1.

**Accuracy** ASPEN$^+$ consistently achieved the highest $F_1$ scores across all datasets. Compared to the pairwise baselines, it outperformed Magellan and JedAI by wide margins, with $F_1$ gains ranging from 7.86% to 82% over Magellan, and 1.64% to 77% over JedAI. Similar trends were observed for ASPEN, highlighting the advantage of logic-based approaches that support collective ER and enforce constraints.

When compared to ASPEN, ASPEN$^+$ matched its performance on *Imdb* and *Mu*, but achieved $F_1$ improvements of 2.14%, 0.15%, 17.6%, and 3.2% on *ImdbC*, *MuC*, *MuCC*, and *Poke*, respectively. Except for *Imdb* and *ImdbC* (where inherent constraint violations exist) ASPEN$^+$ successfully incorporated all FDs from the schema. In contrast, ASPEN's reliance on global semantics alone often led to unsatisfiable programs when all FDs were included. Thus, ASPEN$^+$ produced solutions with better precision and recall, particularly on noisy datasets like *MuCC*. Interestingly, even in *Poke*, where both systems could include all FDs, ASPEN$^+$ achieved 4.72% higher recall than ASPEN, demonstrating that without handling alternative value representations, valid merges can still be blocked by DCs.

**Running time** The overall time $t_o$ consists of preprocessing (similarity computation) and ER time. For ASP-based systems, the ER time is further composed of grounding and solving time. ASPEN uses an optimized similarity algorithm for preprocessing, making similarity computation faster on more complex datasets. In contrast, ASPEN$^+$ uses a naive cross-product similarity computation, as ASPEN's optimized algorithm is incompatible with local semantics. Overall, both Magellan and JedAI significantly outperformed the ASP-based systems on $t_o$. Compared to ASPEN$^+$, Magellan was faster by factors of 22, 30, 10, 11, 15, and 45 on the *Imdb*, *ImdbC*, *Mu*, *ImdbC*, *MuCC*, and *Poke*, respectively. Similarly, JedAI achieved speed advantages of 4.5 to 506 times over the same datasets. Due to differences in the similarity computation, ASPEN$^+$ was 7 and 8 times faster than ASPEN on simpler datasets like *Imdb* and
<table><caption>Table 1: Results on Complex Multi-relational Datasets</caption><thead><tr><th>Method</th><th>Data</th><th>F<sub>1</sub></th><th>(P / R)</th><th>t<sub>o</sub></th><th>t<sub>g</sub></th><th>t<sub>s</sub></th><th>#DC</th><th>Data</th><th>F<sub>1</sub></th><th>(P / R)</th><th>t<sub>o</sub></th><th>t<sub>g</sub></th><th>t<sub>s</sub></th><th>#DC</th></tr></thead><tbody><tr><td>Magellan</td><td rowspan="4">Imdb</td><td>88.09</td><td><strong>99.80</strong></td><td>78.83</td><td><strong>3.89</strong></td><td>N/A</td><td>N/A</td><td>0/5</td><td rowspan="4">ImdbC</td><td>83.05</td><td><strong>99.77</strong></td><td>71.12</td><td><strong>3.11</strong></td><td>N/A</td><td>N/A</td><td>0/5</td></tr><tr><td>JedAI</td><td>97.49</td><td>99.40</td><td>95.67</td><td>18.78</td><td>N/A</td><td>N/A</td><td>0/5</td><td>97.49</td><td>99.40</td><td>95.67</td><td>18.67</td><td>N/A</td><td>N/A</td><td>0/5</td></tr><tr><td>ASPEN</td><td><strong>99.27</strong></td><td>99.39</td><td><strong>99.14</strong></td><td>610.49</td><td><strong>11.51</strong></td><td><strong>0.082</strong></td><td>1/5</td><td>96.99</td><td>99.36</td><td>94.73</td><td>757.17</td><td><strong>11.75</strong></td><td><strong>0.088</strong></td><td>1/5</td></tr><tr><td>ASPEN<sup>+</sup></td><td><strong>99.27</strong></td><td>99.39</td><td><strong>99.14</strong></td><td>86.24</td><td>13.02</td><td>0.096</td><td>3/5</td><td><strong>99.13</strong></td><td>99.39</td><td><strong>98.87</strong></td><td>94.85</td><td>18.71</td><td>0.69</td><td>3/5</td></tr><tr><td>Magellan</td><td rowspan="4">Mu</td><td><u>89.78</u></td><td><u>98.63</u></td><td>82.38</td><td><strong>64.83</strong></td><td>N/A</td><td>N/A</td><td>0/23</td><td rowspan="4">MuC</td><td>55.54</td><td><strong>97.51</strong></td><td><u>38.83</u></td><td><strong>66.87</strong></td><td>N/A</td><td>N/A</td><td>0/23</td></tr><tr><td>JedAI</td><td>70.67</td><td>87.46</td><td><u>59.30</u></td><td>105.06</td><td>N/A</td><td>N/A</td><td>0/23</td><td>32.75</td><td>73.95</td><td>21.02</td><td>101.02</td><td>N/A</td><td>N/A</td><td>0/23</td></tr><tr><td>ASPEN</td><td><strong>97.64</strong></td><td><strong>99.45</strong></td><td><strong>95.89</strong></td><td>666.01</td><td><strong>1.78</strong></td><td><strong>0.20</strong></td><td>21/23</td><td><u>90.31</u></td><td>91.86</td><td><strong>88.81</strong></td><td>695.76</td><td><strong>20.15</strong></td><td><strong>3.57</strong></td><td>17/23</td></tr><tr><td>ASPEN<sup>+</sup></td><td><strong>97.64</strong></td><td><strong>99.45</strong></td><td><strong>95.89</strong></td><td>665.65</td><td>1.82</td><td>0.21</td><td>23/23</td><td><strong>90.46</strong></td><td><u>92.17</u></td><td><strong>88.81</strong></td><td>770.44</td><td>72.81</td><td>12.16</td><td>23/23</td></tr><tr><td>Magellan</td><td rowspan="4">MuCC</td><td>55.48</td><td><strong>97.62</strong></td><td>38.75</td><td><strong>64.81</strong></td><td>N/A</td><td>N/A</td><td>0/23</td><td rowspan="4">Poke</td><td>7.01</td><td>3.97</td><td>29.74</td><td><u>260.96</u></td><td>N/A</td><td>N/A</td><td>0/10</td></tr><tr><td>JedAI</td><td>31.04</td><td>72.47</td><td>19.75</td><td><u>101.47</u></td><td>N/A</td><td>N/A</td><td>0/23</td><td>2.1</td><td>1.08</td><td>46.56</td><td><strong>23.46</strong></td><td>N/A</td><td>N/A</td><td>0/10</td></tr><tr><td>ASPEN</td><td><u>71.18</u></td><td>77.83</td><td><u>65.58</u></td><td>718.38</td><td><strong>21.01</strong></td><td><strong>10.47</strong></td><td>16/23</td><td><strong>81.78</strong></td><td><u>99.71</u></td><td><u>69.31</u></td><td>4,454</td><td><strong>311.37</strong></td><td><strong>0.91</strong></td><td>10/10</td></tr><tr><td>ASPEN<sup>+</sup></td><td><strong>88.85</strong></td><td><u>89.5</u></td><td><strong>88.21</strong></td><td>993.31</td><td>97.51</td><td>23.02</td><td>23/23</td><td><strong>84.98</strong></td><td><strong>99.73</strong></td><td><strong>74.03</strong></td><td>11,880</td><td>496.14</td><td>48.52</td><td>10/10</td></tr></tbody></table>

ImdbC. However, on more complex datasets, the optimised similarity algorithm used by ASPEN gave speed advantages of 1.1, 1.4, and 2.6 times compared to ASPEN<sup>+</sup> on MuC, MuCC, and Poke.

In terms of t<sub>g</sub> and t<sub>s</sub>, ASPEN consistently outperformed ASPEN<sup>+</sup>. On MuC, MuCC, and Poke, ASPEN's grounding was 3.6, 4.6, and 1.5 times faster, respectively. The differences in solving time were even more pronounced: ASPEN<sup>+</sup> was 2.1, 3.4, 7.8, and 53 times slower than ASPEN on MuCC, MuC, ImdbC, and Poke. These results show that while ASPEN<sup>+</sup> delivers higher ER quality, it often does so at the expense of computational efficiency.

## 5.2 Comparison on Optimization Criteria

**Setup** For each dataset, we fixed the corresponding ER program and used ASPEN<sup>+</sup> to compute one and up to 50 optimal solutions based on the set of optimization criteria defined in Section 3.3. For set-based criteria, heuristic-driven solving was enabled. For cardinality-based criteria, we used weighted constraints and enabled parallel solving with 36 threads. We recorded the average accuracy metrics over the number of enumerated solutions #e as $\bar{F}_1/\bar{P}/\bar{R}$. For efficiency, we measured the solving time to compute the first optimal model ($t_s^1$) and the average solving time per model $t_s^n$. For simplicity, we use the prefixes S- and C- to denote, in general, set-based and cardinality-based optimality criteria, respectively. Results are summarized in Table 2 and Table 3. Appendix D.2 presents results for various configurations under each optimality criterion (e.g., using aspirin vs. using heuristic). The results reported in this section correspond to the most efficient configuration.

**Accuracy** For the simpler datasets, Imdb, ImdbC, and Mu, we observed that all optimization criteria produced a single optimal solution identical to maxES, resulting in the same $\bar{F}_1$ (see Appendix D.3). This is consistent with findings from (Xiang et al. 2024), indicating that in the presence of data with less corrupted values and nulls, value-

<table><caption>Table 2: Result on optimal solutions under different set-optimisation criteria over the datasets</caption><thead><tr><th>Data</th><th>Method</th><th>F&#x0304;<sub>1</sub></th><th>(P&#x0304; / R&#x0304;)</th><th>t<sub>s</sub><sup>1</sup></th><th>#e</th><th>t<sub>s</sub><sup>n</sup></th></tr></thead><tbody><tr><td rowspan="3">MuC</td><td>maxES/SS</td><td>90.50</td><td>92.20</td><td><strong>88.86</strong></td><td><strong>12.16</strong></td><td>50</td><td>1.86</td></tr><tr><td>minAS</td><td><strong>91.88</strong></td><td><strong>95.11</strong></td><td><strong>88.86</strong></td><td>12.8</td><td>50</td><td><strong>1.7</strong></td></tr><tr><td>minVS</td><td><u>91.7</u></td><td><u>94.73</u></td><td><u>88.85</u></td><td>12.44</td><td>50</td><td><u>1.78</u></td></tr><tr><td rowspan="3">MuCC</td><td>maxES/SS</td><td>88.85</td><td>89.5</td><td><strong>88.21</strong></td><td>23.02</td><td>50</td><td><u>1.67</u></td></tr><tr><td>minAS</td><td><u>89.62</u></td><td><u>91.11</u></td><td>88.18</td><td>23.01</td><td>50</td><td><strong>1.54</strong></td></tr><tr><td>minVS</td><td><strong>90.13</strong></td><td><strong>92.2</strong></td><td>88.15</td><td>21.61</td><td>50</td><td>2.48</td></tr><tr><td rowspan="3">Poke</td><td>maxES/SS</td><td><strong>84.98</strong></td><td><strong>99.73</strong></td><td><strong>74.03</strong></td><td><strong>48.52</strong></td><td>1</td><td>N/A</td></tr><tr><td>minAS</td><td>83.83</td><td><strong>99.73</strong></td><td>72.3</td><td>51.58</td><td>50</td><td><u>0.06</u></td></tr><tr><td>minVS</td><td><strong>84.62</strong></td><td><strong>99.73</strong></td><td>73.48</td><td>56.87</td><td>50</td><td><strong>0.01</strong></td></tr></tbody></table>

<table><caption>Table 3: Result on optimal solutions under different cardinality-optimisation criteria over the datasets</caption><thead><tr><th>Data</th><th>Method</th><th>F&#x0304;<sub>1</sub></th><th>(P&#x0304; / R&#x0304;)</th><th>t<sub>s</sub><sup>1</sup></th><th>#e</th><th>t<sub>s</sub><sup>n</sup></th></tr></thead><tbody><tr><td rowspan="4">MuC</td><td>maxEC</td><td>90.51</td><td>92.20</td><td><strong>88.9</strong></td><td><u>35.09</u></td><td>50</td><td><strong>2.53</strong></td></tr><tr><td>maxSC</td><td>90.52</td><td>92.21</td><td><strong>88.9</strong></td><td><strong>30.1</strong></td><td>16</td><td>12.09</td></tr><tr><td>minAC</td><td><u>91.4</u></td><td><u>94.05</u></td><td><strong>88.9</strong></td><td>84.69</td><td>50</td><td><u>2.61</u></td></tr><tr><td>minVC</td><td><strong>92.01</strong></td><td><strong>95.35</strong></td><td>88.89</td><td>48.97</td><td>50</td><td>5.66</td></tr><tr><td rowspan="3">MuCC</td><td>maxEC</td><td>88.83</td><td>89.45</td><td><strong>88.21</strong></td><td>66.71</td><td>1</td><td>N/A</td></tr><tr><td>maxSC</td><td>88.85</td><td>89.50</td><td><strong>88.21</strong></td><td><strong>52.8</strong></td><td>2</td><td>629.56</td></tr><tr><td>minAC</td><td><u>89.51</u></td><td><u>90.93</u></td><td>88.14</td><td>92.97</td><td>50</td><td><strong>2.12</strong></td></tr><tr><td rowspan="3">Poke</td><td>minVC</td><td><strong>89.74</strong></td><td><strong>91.36</strong></td><td>88.18</td><td><u>67.82</u></td><td>50</td><td><u>8.42</u></td></tr><tr><td>maxEC</td><td><strong>84.98</strong></td><td><strong>99.73</strong></td><td><strong>74.03</strong></td><td><strong>48.52</strong></td><td>1</td><td>N/A</td></tr><tr><td>maxSC</td><td><strong>84.98</strong></td><td><strong>99.73</strong></td><td><strong>74.03</strong></td><td><strong>49.1</strong></td><td>1</td><td>N/A</td></tr><tr><td></td><td>minAC</td><td>84.80</td><td><strong>99.73</strong></td><td>73.75</td><td>49.23</td><td>50</td><td><strong>0.037</strong></td></tr><tr><td></td><td>minVC</td><td><strong>84.91</strong></td><td><strong>99.73</strong></td><td><u>73.91</u></td><td>49.11</td><td>2</td><td><u>1.15</u></td></tr></tbody></table>
based comparisons (e.g., similarity or equality) are sufficient for merging, leaving little room for variation. In contrast, for more complex datasets, minVS and minVC achieved the highest accuracy on *MuC* and *MuCC*, outperforming the default maxES by 1.5% and 1.28%, respectively. However, on *Poke*, the opposite trend was observed: maxES slightly outperformed minVS and minVC by 0.36% and 0.07%, resp. We also observed that solutions based on different optimization criteria differ in the following:

*minA & minV vs maxS & maxE*. Except for a tie on *Poke*, minA and minV consistently outperformed maxS and maxE in terms of precision. The largest improvements were observed on *MuC* and *MuCC*, with leads of 2.93% and 2.7% for the S-criteria, and 1.5% and 1.9% for the C-optimal solutions, respectively. In contrast, maxS/maxE obtained better recall, with the largest leads of 1.73% seen when comparing maxES/SS to minAS on *Poke*. This highlights the different characteristics between minA/minV and maxS/maxE, while the former prioritizes precision, the latter is more inclusive and has better coverage. As a result, on datasets with more corrupted values like *MuC* and *MuCC*, minA/minV obtained higher $\bar{F}_1$.

*maxE vs maxS & minA vs minV*. $\bar{F}_1$ scores for maxE and maxS are very close, with only marginal differences on *MuC* and *MuCC*, and identical results on *Poke*. Although maxS typically achieves higher precision, maxE consistently yields the best recall. This suggests that although both criteria are similar in nature, prioritizing rule applications may lead to more cautious merging decisions while maintaining good coverage. Similar trends were observed between minA and minV, where minV achieved higher precision and better $\bar{F}_1$ scores on all datasets except *MuC*.

*Set vs Cardinality*. Accuracy metrics between S-optimal and C-optimal solutions differ only slightly, with the former generally achieving higher precision and the latter showing better recall. Although S optimization often produces many solutions, C optimization solutions may be preferable when a single representative model is desired.

**Efficiency** For S-optimization, first-model solving time $t_s^1$ is generally at the same level across criteria, with the largest difference being 1.1 times between minVS and maxES on *Poke*. Enumeration speed $t_s^n$ is also similar, except on *Poke*, where minVS was 6 times faster than minAS. In contrast, C-optimization methods show greater variability. minAC was consistently the slowest for first-model computation, taking up to 2.8, 1.76, and 1.01 times longer than the fastest criteria (maxEC and maxSC) on *MuC*, *MuCC*, and *Poke*, resp.

Comparing the solving times of each S-optimal criterion with its C-optimal counterpart, we observed substantial increases in both $t_s^1$ and $t_s^n$—despite executing C-optimal computations on 36 threads. Without multi-threaded solving, both minAC and minV hit the 24-hour timeout, even with heuristic-driven solving enabled (see Appendix D). These results suggest that in resource-constrained environments, S-optimal solutions are more practical, as the marginal quality gains from C-optimal solutions often come at a significant computational cost.

## 5.3 Qualitative Studies

We present qualitative examples from the *MuCC* dataset, illustrating the efficacy and necessity of local semantics. In the *MuCC* dataset, the schema includes:

* *Place pid,name,type,address,area,coordinate)*: stores information of building or outdoor area used for performing or producing music, where the *area* attribute is a reference to *id* of the *Area* table.

* *Release (rid, artist, name, barcode, language)*: records information of release of music albums.

The ER program for *MuCC* contains: i) a hard rule $hr_1$: the *rid* of two releases are the same if they are from the same *artist* and in the same *language* and similar *names*. ii) a soft rule $sr_1$: the *pid* of two places are possibly the same if they have the same *type* and similar *names*. iii) two denial constraints $d_1$ and $d_2$: FDs requiring that *pid*/*rid* must associate to the same *coordinate*/*barcode*, respectively.

**Block of merges** The two *Place* tuples

* *Place*($t_1$, $p_1$, *Kunsthalle*, *Kindikty*, $a_1$, 48.20 81.63)

* *Place*($t_2$, $p_2$, *Kunsthalle*, *Kindikty* dist., $a_2$, 48.20-81.63)

satisfy $sr_1$, but will be blocked by $d_1$ if the two *value constants* 48.20 81.63 and 48.20-81.63 are not merged. Thus, the pair is absent in the stable models of ASPEN, but might be present in those of ASPEN$^+$.

**Violation of DCs** The two *Release* tuples

* *Release*($t_3$, $r_1$, $a_1$, *chante les poètes*, 48.20 81.63, FR)

* *Release*($t_4$, $r_2$, $a_2$, *chanteLes poètes*, 48.20-81.63, Fr)

satisfy the hard rule $hr_1$, requiring that $eqo(r1, r2)$ be included in any stable model. However, without merging the value constants 48.20 81.63 and 48.20-81.63, the program violates the DC $d_2$, resulting in no solution for *MuCC*. As a result, $d_2$ must be excluded from ASPEN's ER program. In contrast, ASPEN$^+$ can safely incorporate $d_2$ by handling alternative representations of values.

**Local merges are necessary** To satisfy $d_2$, the barcodes in the two *Release* tuples must be merged. However, these same values also appear as *coordinates* in the *Place* table, where they refer to distinct locations—one in Germany, the other in Kazakhstan. As a result, the merge must be handled locally using ASPEN$^+$; a global merge would incorrectly unify distinct places and propagate errors to related tables such as *Area*, due to referential dependencies.

## 6 Conclusions

We have introduced ASPEN$^+$, a logic-based system for collective ER that supports both global and local merges, along with a suite of seven optimality criteria for preferred solutions. Our formalization and complexity analysis of these criteria offer new insights into optimal ER solution selection. Through extensive experiments, we demonstrate the practical benefits of local semantics and flexible optimization, achieving superior accuracy on complex, real-world datasets. ASPEN$^+$ thus marks a significant step toward principled ER in noisy and multi-relational environments.
Acknowledgements

The authors were partially supported by the ANR AI Chair
INTENDED (ANR-19-CHIA-0014) and by MUR under the
PNRR project FAIR (PE0000013). The authors thank the
Potassco community for their support in resolving the issues
encountered while using clingo.

References

Arasu, A.; Ré, C.; and Suciu, D. 2009. Large-scale dedupli-
cation with constraints using dedupalog. In Ioannidis, Y. E.;
Lee, D. L.; and Ng, R. T., eds., *Proceedings of the 25th In-
ternational Conference on Data Engineering, ICDE 2009*,
*March 29 2009 - April 2 2009*, Shanghai, China, 952–963.
IEEE Computer Society.

Bahmani, Z.; Bertossi, L. E.; and Vasiloglou, N. 2017.
Erblox: Combining matching dependencies with machine
learning for entity resolution. *Int. J. Approx. Reason.*
83:118–141.

Bertossi, L. E.; Kolahi, S.; and Lakshmanan, L. V. S. 2013. Data cleaning and query answering with matching dependencies and matching functions. *Theory of Computing Systems* 52(3):441–482.

Bhattacharya, I., and Getoor, L. 2007. Collective entity
resolution in relational data. *ACM Trans. Knowl. Discov.
Data* 1(1):5.

Bienvenu, M.; Cima, G.; Gutiérrez-Basulto, V.; and Ibáñez-García, Y. 2023. Combining global and local merges in logic-based entity resolution. In Marquis, P.; Son, T. C.; and Kern-Isberner, G., eds., *Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning*, KR 2023, Rhodes, Greece, September 2-8, 2023, 742–746.

Bienvenu, M.; Cima, G.; and Gutiérrez-Basulto, V. 2022.
LACE: A logical approach to collective entity resolution.
In Libkin, L., and Barceló, P., eds., *PODS '22: International Conference on Management of Data*, Philadelphia,
PA, USA, June 12 - 17, 2022, 379–391. ACM.

Börger, E.; Grädel, E.; and Gurevich, Y. 1997. *The Classical Decision Problem*. Perspectives in Mathematical Logic. Springer.

Brewka, G.; Delgrande, J. P.; Romero, J.; and Schaub, T. 2023. A general framework for preferences in answer set programming. *Artif. Intell.* 325:104023.

Brewka, G.; Eiter, T.; and Truszczynski, M. 2011. Answer set programming at a glance. *Commun. ACM* 54(12):92–103.

Burdick, D.; Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W. 2016. A declarative framework for linking entities. *ACM Trans. Database Syst.* 41(3):17:1–17:38.

Cabalar, P., and Muñiz, B. 2023. Explanation graphs for sta-
ble models of labelled logic programs. In *ICLP Workshops*,
volume 3437 of *CEUR Workshop Proceedings*. CEUR-
WS.org.

Calimeri, F.; Faber, W.; Gebser, M.; Ianni, G.; Kaminski,
R.; Krennwallner, T.; Leone, N.; Maratea, M.; Ricca, F.; and

Schaub, T. 2020. Asp-core-2 input language format. *Theory Pract. Log. Program.* 20(2):294–309.

Christophides, V.; Efthymiou, V.; Palpanas, T.; Papadakis, G.; and Stefanidis, K. 2021. An overview of end-to-end entity resolution for big data. *ACM Comput. Surv.* 53(6):127:1–127:42.

Deng, T.; Fan, W.; Lu, P.; Luo, X.; Zhu, X.; and An, W. 2022. Deep and collective entity resolution in parallel. In *38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022*, 2060–2072. IEEE.

Fagin, R.; Kolaitis, P. G.; Lembo, D.; Popa, L.; and Scafoglieri, F. 2023. A framework for combining entity resolution and query answering in knowledge bases. In *KR*, 229–239.

Fan, W.; Jia, X.; Li, J.; and Ma, S. 2009. Reasoning about record matching rules. *Proceedings of the VLDB Endowment* 2(1):407–418.

Fan, W. 2008. Dependencies revisited for improv-
ing data quality. In *Proceedings of the Twenty-Seventh
ACM SIGMOD-SIGACT-SIGART Symposium on Principles
of Database Systems (PODS 2008)*, 159–170. ACM.

Gebser, M.; Kaminski, R.; Kaufmann, B.; and Schaub, T. 2012. *Answer Set Solving in Practice*. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers.

Gebser, M.; Kaufmann, B.; Romero, J.; Otero, R.; Schaub, T.; and Wanko, P. 2013. Domain-specific heuristics in answer set programming. In desJardins, M., and Littman, M. L., eds., *Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA*, 350–356. AAAI Press.

Gebser, M.; Leone, N.; Maratea, M.; Perri, S.; Ricca, F.; and Schaub, T. 2018. Evaluation techniques and systems for answer set programming: a survey. In Lang, J., ed., *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden*, 5450–5456. ijcai.org.

Gebser, M.; Kaufmann, B.; and Schaub, T. 2012. Multi-threaded ASP solving with clasp. *Theory Pract. Log. Program.* 12(4-5):525–545.

Konda, P.; Das, S.; C., P. S. G.; Doan, A.; Ardalan, A.; Bal-
lard, J. R.; Li, H.; Panahi, F.; Zhang, H.; Naughton, J. F.;
Prasad, S.; Krishnan, G.; Deep, R.; and Raghavendra, V.
2016. Magellan: Toward building entity matching manage-
ment systems. *Proc. VLDB Endow.* 9(12):1197–1208.

Köpcke, H.; Thor, A.; and Rahm, E. 2010. Evaluation of
entity resolution approaches on real-world match problems.
*Proc. VLDB Endow.* 3(1):484–493.

Lifschitz, V. 2019. *Answer Set Programming*. Springer.

Papadakis, G.; Mandilaras, G. M.; Gagliardelli, L.; Simonini, G.; Thanos, E.; Giannakopoulos, G.; Bergamaschi, S.; Palpanas, T.; and Koubarakis, M. 2020. Three-dimensional entity resolution with jedai. *Inf. Syst.* 93:101565.
Rosa, E. D.; Giunchiglia, E.; and Maratea, M. 2010. Solving satisfiability problems with preferences. *Constraints An Int. J.* 15(4):485–515.

Singla, P., and Domingos, P. M. 2006. Entity resolution with markov logic. In *Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006), 18-22 December 2006, Hong Kong, China*, 572–582. IEEE Computer Society.

Xiang, Z.; Bienvenu, M.; Cima, G.; Gutiérrez-Basulto, V.; and Ibáñez-García, Y. 2024. ASPEN: asp-based system for collective entity resolution. In Marquis, P.; Ortiz, M.; and Pagnucco, M., eds., *Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi, Vietnam. November 2-8, 2024.*

Xiang, Z. 2025. ASPEN$^+$ Git Repository. https://github.com/zl-xiang/ASPEnP.
A Intuitions of Optimality Criteria

maxES/maxEC. Under these criteria, solutions that merge more objects or values are preferred, as they tend to reduce duplication in data records. Set containment offers an intuitive basis for comparing solutions obtained through incremental applications of merging rules. In contrast, the maxEC criterion can be useful in scenarios where two solutions overlap only partially, as it favors the one that achieves a greater total number of merges.

maxSC. Under this cardinality-based criterion, solutions that include the same number of merges can still be distinguished by taking into account the supporting rules. We use the SUPP(E, V), which annotates merges with the rules that support them, to give greater weight to merges supported by multiple rules. Intuitively, duplicate entities or values can often be identified through different reasoning paths, so merges justified by several rules are considered more likely to correspond to true duplicates. Note that while we can also define a set-based criterion, maxSS, which takes into account the rules supporting merges, we have proven in Proposition 1 that maxES and maxSS actually coincide.

minAS/minAC. Under these criteria, solutions are compared based on the triggered merges that fail to perform — captured by the set ABS(E, V). Intuitively, we prefer solutions that minimize such 'missed' merges, as these indicate pairs that were active according to some rule but were not included in the final merge set.

minVS/minVC. These criteria select solutions that minimize the number of violated soft rules, formalized by VIOL(E, V). Intuitively, we prefer solutions that respect more soft rules, as these represent likely but non-mandatory matches. Minimizing violations promotes solutions that adhere more closely to the intended matching heuristics, possibly improving the overall quality and consistency of the resolved data.

B Proofs of Section 3

To simplify the presentation of the proofs, we introduce some additional notation and preliminary results:

* We denote by $\text{Dom}(D)$ the set of constants occurring in a database $D$.

* Given an *n*-ary query $q(x_1, \dots, x_n)$ and *n*-tuple of constants $\vec{c} = (c_1, \dots, c_n)$, we denote by $q[\vec{c}]$ the Boolean query obtained by replacing each $x_i$ by $c_i$.

* We use $\text{qvars}(q)$ (resp. $\text{cons}(q)$) for the set of variables (resp. constants) occurring in a query $q$. With a slight abuse of notation, we sometimes denote by $\pi \in q$ the fact that a relational atom $\pi$ occurs in $q$.

* Given an ER specification $\Sigma$ and a database $D$, for any $X \in \{\text{maxES}, \text{maxEC}, \text{maxSS}, \text{maxSC}, \text{minAS}, \text{minAC}, \text{minVS}, \text{minVC}\}$, we denote by $\text{OptSol}_X(D, \Sigma)$ the set of $X$-optimal solutions for $(D, \Sigma)$.

The following definition, taken from (Bienvenu et al. 2023, Definition 2), specifies how queries in rule bodies and constraints are to be evaluated over extended databases.

**Definition 3.** A Boolean query $q$ (possibly containing similarity and inequality atoms) is satisfied in $D_{E,V}$, denoted $D_{E,V} \models q$, if there exists a function $h : \text{qvars}(q) \cup \text{cons}(q) \to 2^{\text{Dom}(D)} \setminus \{\emptyset\}$ and functions $g_\pi : \{0, \dots, k\} \to 2^{\text{Dom}(D)}$ for each $k$-ary relational atom $\pi \in q$, such that:

1. $h$ is determined by the $g_\pi$: for every $a \in \text{cons}(q)$, $h(a) = \{a\}$, and for every $z \in \text{qvars}(q)$, $h(z)$ is the intersection of all sets $g_\pi(i)$ such that $z$ is the $i$th argument of $\pi$;

2. for every relational atom $\pi = R(u_0, u_1, \dots, u_k) \in q$, $R(g_\pi(0), g_\pi(1), \dots, g_\pi(k)) \in D_{E,V}$, and for every $1 \le i \le k$, if $u_i \in \text{cons}(q)$, then $u_i \in g_\pi(i)$;

3. for every inequality atom $z \neq z' \in q$: $h(z) \cap h(z') = \emptyset$;

4. for every similarity atom $u \approx u' \in q$: there exist $c \in h(u)$ and $c' \in h(u')$ such that $c \approx c'$.

For non-Boolean queries, the set $q(D_{E,V})$ of answers to $q(\vec{x})$ contains those tuples $\vec{c}$ such that $D_{E,V} \models q[\vec{c}]$.

**Lemma 1.** Let $q$ be a Boolean query (possibly involving similarity and inequality atoms), $D$ be a database, $E$ be an equivalence relation on $\text{Obj}(D)$, and $V$ be an equivalence relation on $\text{Cells}(D)$. Checking whether $D_{E,V} \models q$ can be done in polynomial time in the size of $D$, $E$, and $V$.

*Proof.* First, it is immediate to see that computing $D_{E,V}$, i.e. the extended database induced by $D$, $E$, and $V$, can be done in polynomial time in the size of $D$, $E$, and $V$. With a slight abuse of notation, let $\text{dom}(D_{E,V})$ be the set of sets of constants occurring in the extended database $D_{E,V}$. Assuming that $q$ is fixed, we now show that checking whether $D_{E,V} \models q$ can be done in polynomial time.

Observe that, due to Point 2 of Definition 3, if there exists functions $h$ and $g_\pi$ for each relational atom $\pi \in q$ witnessing that $D_{E,V} \models q$, i.e. satisfying Points 2, 1, 3, and 4, then the image of each $g_\pi$ must necessarily be a subset of $\text{dom}(D_{E,V})$. It follows that, when seeking for functions $g_\pi$ for each relational atom $\pi \in q$ witnessing that $D_{E,V} \models q$, we can actually restrict the codomain of each $g_\pi$ to $\text{dom}(D_{E,V})$ rather than considering $2^{\text{Dom}(D)}$.

Now, for each $k$-ary relational atom $\pi \in q$, let $G_\pi$ be the set of all possible functions $g_\pi$ from $\{0, \dots, k\}$ to $\text{dom}(D_{E,V})$. Since $q$ is assumed to be fixed, and therefore $k$ is fixed, the total number of such functions is only polynomial in the size of $D$, $E$, and $V$. Let $\pi_1, \dots, \pi_n$ be the relational atoms occurring in $q$. From what said above, we have that $D_{E,V} \models q$ if and only if there exists functions $(g_{\pi_1}, \dots, g_{\pi_n})$ in the Cartesian product $G_{\pi_1} \times \dots \times G_{\pi_n}$ such that, once computed the function $h$ as specified by Point 1 of Definition 3, requirements 2, 3, and 4 are all satisfied. It is not hard to verify that (i) computing the function $h$ from $(g_{\pi_1}, \dots, g_{\pi_n})$ as specified by Point 1 and (ii) checking whether requirements 2, 3, and 4 are satisfied by $h$ and $(g_{\pi_1}, \dots, g_{\pi_n})$ can be both done in polynomial time. Since $q$ is assumed to be fixed, and therefore the cardinality of the Cartesian product $G_{\pi_1} \times \dots \times G_{\pi_n}$ is only polynomial in the size of $D$, $E$, and $V$, we can immediately derive a polynomial time algorithm for checking whether $D_{E,V} \models q$ which just consider all the possible functions $(g_{\pi_1}, \dots, g_{\pi_n})$ in the Cartesian product $G_{\pi_1} \times \dots \times G_{\pi_n}$.
If for some $(g_{\pi_1}, \dots, g_{\pi_n}) \in G_{\pi_1} \times \dots \times G_{\pi_n}$ requires 2, 3, and 4 are all satisfied after computing $h$ as specified by Point 1, then we return true (because $D_{E,V} \models q$); otherwise, we return false (because $D_{E,V} \not\models q$). $\square$

Since rule bodies do not involve any kind of negation, a pair $\alpha$ that is active in $D_{E,V}$ w.r.t. some rule $r$ remains active in $D_{E',V'}$ for any possible pair $\langle E', V' \rangle$ such that $E \cup V \subseteq E' \cup V'$. In particular, this means that if $\alpha$ is used to construct a (candidate) solution $\langle E, V \rangle$ for $(D, \Sigma)$, then $\alpha$ remains active w.r.t. $\langle E', V' \rangle$. In informal terms: later merges cannot invalidate the reasons for performing an earlier merge. What said above is an immediate consequence of the next lemma.

**Lemma 2.** Let $q(\vec{x})$ be an $n$-ary query (possibly involving similarity atoms), $D$ be a database, $\vec{c}$ be an $n$-tuple of constants, $E$ and $E'$ be two equivalence relations on $\text{Obj}(D)$, and $V$ and $V'$ be two equivalence relations on $\text{Cells}(D)$. If $\vec{c} \in q(D_{E,V})$ and $E \cup V \subseteq E' \cup V'$, then $\vec{c} \in q(D_{E',V'})$.

*Proof.* Suppose that $E \cup V \subseteq E' \cup V'$ and $\vec{c} \in q(D_{E,V})$, i.e. $D_{E,V} \models q[\vec{c}]$. Since $E \cup V \subseteq E' \cup V'$, we can immediately derive the following: for each (extended) fact of the form $R(\{t\}, C_1, \dots, C_k)$ occurring in the extended database $D_{E,V}$, we have a corresponding (extended) fact of the form $R(\{t\}, C'_1, \dots, C'_k)$ occurring in the extended database $D_{E',V'}$ such that $C_i \subseteq C'_i$ holds for every $1 \le i \le k$. Thus, since $q$ does not contain inequality atoms and since $D_{E,V} \models q[\vec{c}]$ holds by assumption, due to the previous observation and the notion of evaluation of Boolean queries over extended databases (Definition 3), it is not hard to see that $D_{E',V'} \models q[\vec{c}]$ as well, i.e. $\vec{c} \in q(D_{E',V'})$. $\square$

**Lemma 3.** Let $\delta$ be a denial constraint over a schema that do not use inequality atoms, $D$ be a database, $E$ and $E'$ be two equivalence relations over $\text{Obj}(D)$, and $V$ and $V'$ be two equivalence relations over $\text{Cells}(D)$. If $D_{E,V} \not\models \delta$ and $E \cup V \subseteq E' \cup V'$, then $D_{E',V'} \not\models \delta$.

*Proof.* Let $\delta = \forall \vec{y}.\varphi(\vec{y}) \rightarrow \bot$. By definition, we have that $D_{E,V} \not\models \delta$ iff $D_{E,V} \models \exists \vec{y}.\varphi(\vec{y})$. So, suppose that $E \cup V \subseteq E' \cup V'$ and $D_{E,V} \not\models \delta$, i.e. $D_{E,V} \models \exists \vec{y}.\varphi(\vec{y})$. Since by assumption $\delta$ is a denial constraint without inequality atoms, and therefore $\exists \vec{y}.\varphi(\vec{y})$ is a CQ (without inequality atoms), and since $D_{E,V} \models \exists \vec{y}.\varphi(\vec{y})$ and $E \cup V \subseteq E' \cup V'$, by Lemma 2 we derive that $D_{E',V'} \models \exists \vec{y}.\varphi(\vec{y})$ as well, and therefore $D_{E',V'} \not\models \delta$, as required. $\square$

We are now ready to provide the proof of Proposition 1 and the proofs of Theorem 1 and Theorem 2. We point out that the lower bounds claimed in Theorem 1 and Theorem 2 are provided using schemas whose relation symbols contain only object positions. This allows us to make three simplifying assumptions: (i) for such schemas, we can consider databases without occurrences of **TID** constants, i.e. databases are not **TID**-annotated; (ii) we can write ER specifications over such schemas as pairs $\Sigma = (\Gamma_O, \Delta)$ rather than as triples $\Sigma = (\Gamma_O, \emptyset, \Delta)$; and (iii) we can write solutions to ER specifications $\Sigma$ over such schemas simply as equivalence relations $E$ over $\text{Dom}(D) = \text{Obj}(D)$ rather

than as pairs $\langle E, \emptyset \rangle$ (i.e. the setting is exactly as in (Bienvenu, Cima, and Gutiérrez-Basulto 2022)).

**Proposition 1.** All pairs of the defined criteria yield different sets of optimal solutions, except for maxES and maxSS.

*Proof.* Claim 1: maxES and maxSS yield the same set of optimal solutions, i.e. we have that $\text{OptSol}_{\text{maxES}}(D, \Sigma) = \text{OptSol}_{\text{maxSS}}(D, \Sigma)$ holds for any ER specification $\Sigma$ and database $D$.

Let $\Sigma$ be an ER specification, $D$ be a database, $E$ be an equivalence relation over $\text{Obj}(D)$, and $V$ be an equivalence relation over $\text{Cells}(D)$. We now show that $\langle E, V \rangle \in \text{OptSol}_{\text{maxES}}(D, \Sigma)$ if and only if $\langle E, V \rangle \in \text{OptSol}_{\text{maxSS}}$, thus proving $\text{OptSol}_{\text{maxES}}(D, \Sigma) = \text{OptSol}_{\text{maxSS}}(D, \Sigma)$.

Only-if part Suppose $\langle E, V \rangle \notin \text{OptSol}_{\text{maxSS}}$, i.e. there is $\langle E', V' \rangle$ such that $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$ and $\text{SUPP}(E, V) \subseteq \text{SUPP}(E', V')$. By combining Lemma 2 and the notion of solution (Definition 2), it is easy to see that any $\langle E'', V'' \rangle$ such that $\langle E'', V'' \rangle \in \text{Sol}(D, \Sigma)$ satisfies the following: if $p \in E'' \cup V''$, then $(p, r) \in \text{actP}(D, E'', V'', \Sigma)$ for some rule $r$ in $\Sigma$. Thus, from this observation, the definition of $\text{SUPP}(\cdot, \cdot)$, and the fact that $\text{SUPP}(E, V) \subseteq \text{SUPP}(E', V')$, we immediately derive that $E \cup V \subseteq E' \cup V'$. Since $\langle E', V' \rangle$ is such that $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$, we can conclude that $\langle E, V \rangle \notin \text{OptSol}_{\text{maxES}}$ as well.

If part Suppose $\langle E, V \rangle \notin \text{OptSol}_{\text{maxES}}$, i.e. there is $\langle E', V' \rangle$ such that $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$ and $E \cup V \subseteq E' \cup V'$. By combining Lemma 2 and the fact that $E \cup V \subseteq E' \cup V'$, we immediately derive that $\text{actP}(D, E, V, \Sigma) \subseteq \text{actP}(D, E', V', \Sigma)$, and therefore $\text{SUPP}(E, V) \subseteq \text{SUPP}(E', V')$. Since $\langle E', V' \rangle$ is such that $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$, we can conclude that $\langle E, V \rangle \notin \text{OptSol}_{\text{maxSS}}$ as well.

**Claim 2:** Let $X$ be any criteria based on set inclusion (i.e. $X \in \{\text{maxES}, \minAS, \minVS\}$), and let $Y$ be any criteria based on cardinality (i.e. $Y \in \{\text{maxEC}, \text{maxSS}, \minAC, \minVC\}$). Then, there exists a specification $\Sigma$ and a database $D$ such that $\text{OptSol}_X(D, \Sigma) \not= \text{OptSol}_Y(D, \Sigma)$.

Consider $\Sigma = (\Gamma_O, \emptyset, \Delta)$, where $\Gamma_O = \{\sigma, \sigma'\}$ and $\Delta = \{\delta\}$ are defined as follows:

* $\sigma = R(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma' = R'(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\delta = \forall y, z. \neg(R(y, y) \wedge R'(z, z))$

Let $D = \{R(a_1, a_2), R'(b_1, b_2), R'(c_1, c_2)\}$. Observe that, due to $\delta$, no $\langle E, \emptyset \rangle \in \text{Sol}(D, \Sigma)$ can be such that $(a_1, a_2) \in E$ and either $(b_1, b_2) \in E$ or $(c_1, c_2) \in E$. Now, consider $E_\alpha = \{(a_1, a_2)\}$ and $E_{b,c} = \{(b_1, b_2), (c_1, c_2)\}$, and let $E' = \text{EqRel}(E_\alpha, \text{Obj}(D))$ and $E'' = \text{EqRel}(E_{b,c}, \text{Obj}(D))$. It is straightforward to verify that $\text{OptSol}_{\text{maxES}}(D, \Sigma) = \text{OptSol}_{\text{minAS}}(D, \Sigma) = \text{OptSol}_{\text{minVS}}(D, \Sigma) = \{\langle E', \emptyset \rangle, \langle E'', \emptyset \rangle\}$ while $\text{OptSol}_{\text{maxEC}}(D, \Sigma) = \text{OptSol}_{\text{maxSC}}(D, \Sigma) = \text{OptSol}_{\text{minAC}}(D, \Sigma) = \text{OptSol}_{\text{minVC}}(D, \Sigma) = \{\langle E'', \emptyset \rangle\}$.

**Claim 3:** There exists a specification $\Sigma$ and a database $D$ such that $\text{OptSol}_{\text{maxES}}(D, \Sigma) \not= \text{OptSol}_{\text{minAS}}(D, \Sigma) = \text{OptSol}_{\text{minVS}}(D, \Sigma)$.
Consider $\Sigma = \langle \Gamma_O, \emptyset, \Delta \rangle$, where $\Gamma_O = \{\sigma, \sigma'\}$ and $\Delta = \{\delta\}$ are defined as follows:

* $\sigma = R(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma' = \exists z. R(z, z) \wedge R'(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\delta = \forall y, z. \neg(R(y, y) \wedge R'(z, z))$

Let $D = \{R(a_1, a_2), R'(b_1, b_2)\}$. Observe that no $\langle E, \emptyset \rangle \in \text{Sol}(D, \Sigma)$ can be such that $(a_1, a_2) \in E$ and $(b_1, b_2) \in E$ as well as no $\langle E, \emptyset \rangle \in \text{Sol}(D, \Sigma)$ can be such that $(b_1, b_2) \in E$ but $(a_1, a_2) \notin E$. Now, consider $E_\emptyset = \emptyset$ and $E_a = \{(a_1, a_2)\}$, and let $E' = \text{EqRel}(E_\emptyset, \text{Obj}(D))$ and $E'' = \text{EqRel}(E_a, \text{Obj}(D))$. It is straightforward to verify that $\text{OptSol}_{\text{maxES}}(D, \Sigma) = \{\langle E'', \emptyset \rangle\}$ while $\text{OptSol}_{\text{minAS}}(D, \Sigma) = \text{OptSol}_{\text{minVS}}(D, \Sigma) = \{\langle E', \emptyset \rangle, \langle E'', \emptyset \rangle\}$.

**Claim 4:** There exists a specification $\Sigma$ and a database $D$ such that $\text{OptSol}_{\text{minAS}}(D, \Sigma) \neq \text{OptSol}_{\text{minVS}}(D, \Sigma)$.

Consider $\Sigma = \langle \Gamma_O, \emptyset, \Delta \rangle$, where $\Gamma_O = \{\sigma_a, \sigma_b, \sigma_c, \sigma_{c'}\}$ and $\Delta = \{\delta\}$ are defined as follows:

* $\sigma_a = R_a(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma_b = R_b(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma_c = R_c(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma_{c'} = \exists z. R_b(z, z) \wedge R_c(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\delta = \forall y, z. \neg(R_a(y, y) \wedge R_c(z, z))$

Let $D = \{R_a(a_1, a_2), R_b(b_1, b_2), R_c(c_1, c_2)\}$. Observe that, due to $\delta$, no $\langle E, \emptyset \rangle \in \text{Sol}(D, \Sigma)$ can be such that $(a_1, a_2) \in E$ and $(c_1, c_2) \in E$. Now, consider $E_a = \{(a_1, a_2)\}$ and $E_{a,b} = \{(a_1, a_2), (b_1, b_2)\}$, and let $E' = \text{EqRel}(E_a, \text{Obj}(D))$ and $E'' = \text{EqRel}(E_{a,b}, \text{Obj}(D))$. Observe that $\text{ABS}(E', \emptyset) = \{(b_1, b_2), (c_1, c_2)\}$ while $\text{ABS}(E'', \emptyset) = \{(c_1, c_2)\}$. Thus, since $E'' \in \text{Sol}(D, \Sigma)$, we derive that $E' \notin \text{OptSol}_{\text{minAS}}(D, \Sigma)$ because $\text{ABS}(E'', \emptyset) \subseteq \text{ABS}(E', \emptyset)$. Notice, however, that $\text{VIOL}(E', \emptyset) = \{( (b_1, b_2), \sigma_b), ((c_1, c_2), \sigma_c) \}$ while $\text{VIOL}(E'', \emptyset) = \{( (c_1, c_2), \sigma_c), ((c_1, c_2), \sigma_{c'}) \}$. So, $((c_1, c_2), \sigma_{c'}) \in \text{VIOL}(E'', \emptyset)$ but $((c_1, c_2), \sigma_{c'}) \notin \text{VIOL}(E', \emptyset)$. Thus, it is easy to see that $E' \in \text{OptSol}_{\text{minVS}}(D, \Sigma)$. We conclude that $\text{OptSol}_{\text{minAS}}(D, \Sigma) \neq \text{OptSol}_{\text{minVS}}(D, \Sigma)$.

**Claim 5:** There exists a specification $\Sigma$ and a database $D$ such that $\text{OptSol}_{\text{maxEC}}(D, \Sigma) = \text{OptSol}_{\text{maxSC}}(D, \Sigma) \neq \text{OptSol}_{\text{minAC}}(D, \Sigma) = \text{OptSol}_{\text{minVC}}(D, \Sigma)$.

Recall $\Sigma$, $D$, $E'$, and $E''$ as defined in the proof of Claim 3. It is straightforward to verify that $\text{OptSol}_{\text{maxEC}}(D, \Sigma) = \text{OptSol}_{\text{maxSC}}(D, \Sigma) = \{\langle E'', \emptyset \rangle\}$ while $\text{OptSol}_{\text{minAC}}(D, \Sigma) = \text{OptSol}_{\text{minVC}}(D, \Sigma) = \{\langle E', \emptyset \rangle, \langle E'', \emptyset \rangle\}$.

**Claim 6:** There exists a specification $\Sigma$ and a database $D$ such that $\text{OptSol}_{\text{maxEC}}(D, \Sigma) \neq \text{OptSol}_{\text{maxSC}}(D, \Sigma)$.

Consider $\Sigma = \langle \Gamma_O, \emptyset, \Delta \rangle$, where $\Gamma_O = \{\sigma, \sigma', \sigma''\}$ and $\Delta = \{\delta\}$ are defined as follows:

* $\sigma = R(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma' = R'(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma'' = R''(x, y) \dashrightarrow \text{EqO}(x, y)$

* $\delta = \forall y, z. \neg(R(y, y) \wedge R'(z, z))$

Let $D = \{R(a_1, a_2), R'(b_1, b_2), R''(b_1, b_2)\}$. Now, consider $E_a = \{(a_1, a_2)\}$ and $E_b = \{(b_1, b_2)\}$, and let $E' = \text{EqRel}(E_a, \text{Obj}(D))$ and $E'' = \text{EqRel}(E_b, \text{Obj}(D))$. It is straightforward to verify that $\text{OptSol}_{\text{maxEC}}(D, \Sigma) = \{\langle E', \emptyset \rangle, \langle E'', \emptyset \rangle\}$ while $\text{OptSol}_{\text{maxSC}}(D, \Sigma) = \{\langle E'', \emptyset \rangle\}$. This is so because $\text{SUPP}(E'', \emptyset) = \{( (b_1, b_2), \sigma'), ((b_1, b_2), \sigma'') \} = 2$ while $\text{SUPP}(E', \emptyset) = \{((a_1, a_2), \sigma)\} = 1$.

**Claim 7:** There exists a specification $\Sigma$ and a database $D$ such that $\text{OptSol}_{\text{minAC}}(D, \Sigma) \neq \text{OptSol}_{\text{minVC}}(D, \Sigma)$.

Recall $\Sigma$, $D$, $E'$, and $E''$ as defined in the proof of Claim 4. Consider, moreover, $E_{b,c} = \{(b_1, b_2), (c_1, c_2)\}$, and let $E = \text{EqRel}(E_{b,c}, \text{Obj}(D))$. Observe that $\text{ABS}(E, \emptyset) = \{(a_1, a_2)\}$, and recall that $\text{ABS}(E'', \emptyset) = \{(c_1, c_2)\}$. Thus, $|\text{ABS}(E, \emptyset)| = |\text{ABS}(E'', \emptyset)| = 1$, and therefore it is easy to see that $\text{OptSol}_{\text{minAC}}(D, \Sigma) = \{\langle E, \emptyset \rangle, \langle E'', \emptyset \rangle\}$. However, note that $\text{VIOL}(E, \emptyset) = \{((a_1, a_2), \sigma_a)\}$ while $\text{VIOL}(E'', \emptyset) = \{((c_1, c_2), \sigma_c), ((c_1, c_2), \sigma_{c'})\}$, and therefore $|\text{VIOL}(E, \emptyset)| < |\text{VIOL}(E'', \emptyset)|$, which implies that $\langle E'', \emptyset \rangle \notin \text{OptSol}_{\text{minVC}}(D, \Sigma)$. We conclude that $\text{OptSol}_{\text{minAC}}(D, \Sigma) \neq \text{OptSol}_{\text{minVC}}(D, \Sigma)$. $\square$

**Theorem 1.** For all seven optimality criteria, recognition of optimal solutions is coNP-complete in data complexity.

**Proof. Upper bound.** First, given an ER specification $\Sigma$, a database $D$, an equivalence relation $E$ over $\text{Obj}(D)$, and an equivalence relation $V$ over $\text{Cells}(D)$, computing $D_{E,V}$ as well as the set $\text{actP}(D, E, V, \Sigma)$ can be clearly done in polynomial time in the size of $D$, $E$, and $V$ (i.e. assuming that $\Sigma$ is fixed). Based on this observation, given an ER specification $\Sigma$, a database $D$, a binary relation $E$ on $\text{Obj}(D)$, and a binary relation $V$ on $\text{Cells}(D)$, for any $X \in \{\text{maxES}, \text{maxEC}, \text{maxSC}, \text{minAS}, \text{minAC}, \text{minVS}, \text{minVC}\}$, we now show how to check whether $\langle E, V \rangle \notin \text{OptSol}_X(D, \Sigma)$ in NP in the size of $D$, $E$, and $V$.

First, note that, by definition, $\langle E, V \rangle \notin \text{OptSol}_X(D, \Sigma)$ if and only if either $\langle E, V \rangle \notin \text{Sol}(D, \Sigma)$ or there exists $\langle E'', V'' \rangle$ such that $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$ and $\langle E', V' \rangle$ is strictly better than $\langle E, V \rangle$ according to the optimality criteria $X$. So, we first guess a pair $\langle E', V' \rangle$, where $E'$ is a set of pairs of object constants from $\text{Obj}(D)$ and $V'$ is a set of pairs of cells from $\text{Cells}(D)$. Then, we check whether $(i) \langle E, V \rangle \notin \text{Sol}(D, \Sigma)$ or $(ii) \langle E', V' \rangle \in \text{Sol}(D, \Sigma)$ and $\langle E', V' \rangle$ is strictly better than $\langle E, V \rangle$ according to the optimality criteria $X$. If either condition (i) or condition (ii) is satisfied, then we return true; otherwise, we return false. Correctness of the above procedure for deciding $\langle E, V \rangle \notin \text{OptSol}_X(D, \Sigma)$ is trivial.

Due to (Bienvenu et al. 2023, Theorem 2), note that checking whether $\langle E, V \rangle \in \text{Sol}(D, \Sigma)$ can be done in polynomial time in the size of $D$, $E$, and $V$ (and therefore, also checking whether $\langle E', V' \rangle \in \text{Sol}(D, \Sigma)$ can be done in polynomial time in the size of $D$, $E$, and $V$ because both the guessed $E'$ and $V'$ are polynomially related to $D$). Furthermore, since checking whether $\langle E', V' \rangle$ is strictly better than $\langle E, V \rangle$ according to the optimality criteria $X$ is clearly feasible in polynomial time in the size of $D$, $E$, and $V$ due to the fact that computing $\text{actP}(D, E, V, \Sigma)$
(resp. $\text{actP}(D, E', V', \Sigma)$) can be done in polynomial time in the size of $D$, $E$, and $V$ (resp. $D, E'$, and $V'$), we conclude that checking whether $\langle E, V \rangle \notin \text{OptSol}_X(D, \Sigma)$ can be done in NP in the size of $D$, $E$, and $V$.

**Lower bound.** We now give a reduction from the complement of 3SAT. We use the following fixed schema:

$$S = \{R_{\text{fff}}/3, R_{\text{ftf}}/3, R_{\text{ftf}}/3, R_{\text{ttf}}/3, R_{\text{ttf}}/3, R_{\text{ttt}}/3, V/1, F/1, T/1, B/1\}$$

Given an input $\varphi = c_1 \wedge \dots \wedge c_m$ to 3SAT over variables $x_1, \dots, x_n$, where $c_i = \ell_{i,1} \vee \ell_{i,2} \vee \ell_{i,3}$, we construct a database $D^\varphi$ that contains:

* the fact $V(x_i)$ for each $i \in [1, n]$,

* the facts $T(1), F(0), B(0)$, and $B(1)$;

* for each clause $c$ occurring in $\varphi$ of the form $(\overline{x_k} \vee \overline{x_z} \vee \overline{x_w})$ (resp. $(\overline{x_k} \vee \overline{x_z} \vee x_w), (\overline{x_k} \vee x_z \vee \overline{x_w}), (\overline{x_k} \vee x_z \vee x_w), (x_k \vee \overline{x_z} \vee \overline{x_w}), (x_k \vee \overline{x_z} \vee x_w), (x_k \vee x_z \vee \overline{x_w}), (x_k \vee x_z \vee x_w)$), the fact $R_{\text{fff}}(x_k, x_z, x_w)$ (resp. $R_{\text{ftf}}(x_k, x_z, x_w)$, $R_{\text{ftf}}(x_k, x_z, x_w)$, $R_{\text{ttf}}(x_k, x_z, x_w)$, $R_{\text{ttf}}(x_k, x_z, x_w)$, $R_{\text{ttt}}(x_k, x_z, x_w)$).

We also let $E_{\text{triv}}$ be the following equivalence relation over $\text{Obj}(D^\varphi): E_{\text{triv}} = \text{EqRel}(\emptyset, \text{Obj}(D^\varphi))$.

We now define the fixed ER specification $\Sigma_{3\text{SAT}} = (\Gamma_O, \Delta)$, where $\Gamma_O$ contains a single soft rule for objects:

* $\sigma = V(x) \wedge B(y) \dashrightarrow \text{EqO}(x, y)$

and $\Delta$ contains the following denial constraints (all the variables are implicitly universally quantified):

* $\delta_0 = \neg(F(y) \wedge T(y))$

* $\delta_1 = \neg(R_{\text{fff}}(y_1, y_2, y_3) \wedge T(y_1) \wedge T(y_2) \wedge T(y_3))$

* $\delta_2 = \neg(R_{\text{ftf}}(y_1, y_2, y_3) \wedge T(y_1) \wedge T(y_2) \wedge F(y_3))$

* $\delta_3 = \neg(R_{\text{ftf}}(y_1, y_2, y_3) \wedge T(y_1) \wedge F(y_2) \wedge T(y_3))$

* $\delta_4 = \neg(R_{\text{ftt}}(y_1, y_2, y_3) \wedge T(y_1) \wedge F(y_2) \wedge F(y_3))$

* $\delta_5 = \neg(R_{\text{ttf}}(y_1, y_2, y_3) \wedge F(y_1) \wedge T(y_2) \wedge T(y_3))$

* $\delta_6 = \neg(R_{\text{ttf}}(y_1, y_2, y_3) \wedge F(y_1) \wedge T(y_2) \wedge F(y_3))$

* $\delta_7 = \neg(R_{\text{ttf}}(y_1, y_2, y_3) \wedge F(y_1) \wedge F(y_2) \wedge T(y_3))$

* $\delta_8 = \neg(R_{\text{ttt}}(y_1, y_2, y_3) \wedge F(y_1) \wedge F(y_2) \wedge F(y_3))$

* $\delta_9 = \neg(V(v) \wedge B(v) \wedge V(x) \wedge T(y) \wedge F(z) \wedge x \neq y \wedge x \neq z)$

It is straightforward to verify that both $D^\varphi$ and $E_{\text{triv}}$ can be constructed in LOGSPACE from $\varphi$. To conclude the proof, we show that, for any $X \in \{\text{maxES}, \text{maxEC}, \text{maxSC}, \text{minAS}, \text{minAC}, \text{minVS}, \text{minVC}\}$, we have that $E_{\text{triv}} \in \text{OptSol}_X(D^\varphi, \Sigma_{3\text{SAT}})$ if and only if $\varphi$ is unsatisfiable.

If part Suppose that $E_{\text{triv}} \notin \text{OptSol}_X(D^\varphi, \Sigma_{3\text{SAT}})$, i.e. there exists $E'$ such that $E' \in \text{Sol}(D^\varphi, \Sigma_{3\text{SAT}})$ and $E'$ is strictly better than $E_{\text{triv}}$ according to the optimality criteria $X$. By construction of $\Sigma_{3\text{SAT}}$ and $D^\varphi$, and in particular the fact that $\sigma$ is the only rule in $\Gamma_O$, we have that $E'$ must contain at least either a pair of the form $(x_i, 0)$ or a pair of the form $(x_i, 1)$, for some $x_i \in \text{Dom}(D^\varphi)$. Due to the presence of $\delta_9$ in $\Sigma_{3\text{SAT}}$, from the assumption that

$E' \in \text{Sol}(D^\varphi, \Sigma_{3\text{SAT}})$, the presence of this pair in $E'$ actually implies that either $(x_j, 0) \in E'$ or $(x_j, 1) \in E'$, for every $j \in [n]$. Furthermore, due to the presence of $\delta_0$ in $\Sigma_{3\text{SAT}}$, we cannot have both $(x_j, 0) \in E$ and $(x_j, 1) \in E$ for some $j \in [n]$.

We can thus define a valuation $\mu$ by setting $\mu(x_j) = 0$ if $(x_j, 0) \in E'$ and $\mu(x_j) = 1$ if $(x_j, 1) \in E'$, for every $j \in [n]$. Since $E' \in \text{Sol}(D^\varphi, \Sigma_{3\text{SAT}})$, this means that also the denial constraints $\delta_1, \dots, \delta_8$ are satisfied in $D_{E'}^\varphi$. Thus, we can conclude that $\mu$ is a valuation to the variables of $\varphi$ witnessing the satisfiability of $\varphi$.

**Only-if part** Suppose that $\varphi$ is satisfiable, and let $\mu: \{x_0, \dots, x_n\} \to \{0, 1\}$ be a satisfying valuation. Let $E_\mu = \{(x_i, \mu(x_i)) \mid 1 \le i \le n\}$, and let $E' = \text{EqRel}(E_\mu, \text{Obj}(D^\varphi))$. Obviously, $E'$ is strictly better than $E_{\text{triv}}$ according to the optimality criteria $X$. We now conclude the proof by showing that $E' \in \text{Sol}(D^\varphi, \Sigma_{3\text{SAT}})$, which implies that $E_{\text{triv}} \notin \text{OptSol}_X(D^\varphi, \Sigma_{3\text{SAT}})$.

By construction, $(0, 1) \notin E'$, and therefore $D_{E'}^\varphi \models \delta_0$. Furthermore, since by assumption the valuation $\mu$ satisfies all the clauses of $\varphi$, there cannot be any violations of the denial constraints $\delta_1$ to $\delta_8$, i.e. $D_{E'}^\varphi \models \delta_k$, for every $k = 1, \dots, 8$. The last denial constraint $\delta_9$ is also satisfied in $D_{E'}^\varphi$ because $y$ and $z$ must map to 1 and 0 respectively, and for every $x_i$, either $x_i = 1$ or $x_i = 0$ holds in $D_{E'}^\varphi$. $\square$

**Theorem 2.** In the restricted setting, recognition of optimal solutions becomes PTIME-complete in data complexity for the optimality criteria maxES, minAS, and minVS, while it remains coNP-complete in data complexity for the optimality criteria maxEC, maxSC, minAC, and minVC.

**Proof. Upper bound PTIME cases.** For maxES the claim follows from (Bienvenu et al. 2023, Theorem 2). We now provide the proof for the remaining two cases, namely minAS and minVS. We start with minAS.

Given an ER specification $\Sigma = (\Gamma_O, \Gamma_V, \Delta)$ such that the denial constraints in $\Delta$ do not make use of inequality atoms, a database $D$, a binary relation $E$ on $\text{Obj}(D)$, and a binary relation $V$ on $\text{Cells}(D)$, we first check whether $\langle E, V \rangle \in \text{Sol}(D, \Sigma)$. If this is not the case, then we return false and we are done. This can be done in polynomial time in the size of $D$, $E$, and $V$ due to (Bienvenu et al. 2023, Theorem 2). If $\langle E, V \rangle \in \text{Sol}(D, \Sigma)$, we continue as follows. We compute $D_{E,V}$, the set $\text{actP}(D, E, V, \Sigma)$, and the set $\text{ABS}(E, V)$, which can be clearly done in polynomial time in the size of $D$, $E$, and $V$ (i.e. assuming that $\Sigma$ is fixed).

For each $p \in \text{ABS}(E, V)$, we do the following. If $p$ is a pair of object constants, then we start with $E' := \text{EqRel}(E \cup \{p\}, \text{Obj}(D))$ and $V' := V$; otherwise (i.e. $p$ is a pairs of cells), we start with $E' := E$ and $V' := \text{EqRel}(V \cup \{p\}, \text{Cells}(D))$. In both cases, we repeat the following step until a fixpoint is reached: if there is some pair $(o, o')$ such that either $(o, o') \notin \text{ABS}(E, V)$ and $(o, o') \in \text{ABS}(E', V')$ or $(o, o') \in q(D_{E,V})$ for some hard rule for objects $q(x, y) \Rightarrow \text{EqO}(x, y) \in \Gamma_h^o$, then we set $E' := \text{EqRel}(E' \cup \{(o, o')\}, \text{Obj}(D))$. Similarly, if there is some pair $(\langle t, i \rangle, \langle t', i' \rangle)$ such that either $(\langle t, i \rangle, \langle t', i' \rangle) \notin \text{ABS}(E, V)$ and $(\langle t, i \rangle, \langle t', i' \rangle) \in \text{ABS}(E', V')$
ABS(E', V') or (t, t') ∈ q(D<sub>E,V</sub>) for some hard rule
for values q(x<sub>t</sub>, y<sub>t</sub>) ⇒ EqV(⟨x<sub>t</sub>, i⟩, ⟨y<sub>t</sub>, i'⟩) ∈ Γ<sub>h</sub><sup>v</sup>, then
we set V' := EqRel(V' ∪ {⟨⟨t, i⟩, ⟨t', i'⟩⟩}, Cells(D)).
Once the fixpoint is reached, by construction we have that
ABS(E', V') ⊊ ABS(E, V). Then, we just check whether
the resulting ⟨E', V'⟩ is such that ⟨E', V'⟩ ∈ Sol(D, Σ). If
this is the case for some p ∈ ABS(E, V), then we return
false; otherwise, we return true.

Clearly, the overall procedure runs in polynomial time
in the size of D, E, and V. Furthermore, Lemma 2 and
Lemma 3 guarantee its correctness. Notice, indeed, that the
procedure considers pairs ⟨E', V'⟩ such that ABS(E', V') ⊊
ABS(E, V) and that are obtained by ‘minimally’ extending
⟨E, V⟩ while ensuring that all the hard rules are satisfied.
Consider now one ⟨E', V'⟩ obtained as detailed in the fix-
point step of the procedure. If it is the case that D<sub>E',V'</sub> ⊢
Δ, then Lemma 3 guarantees that it is not possible to re-
solve the constraint violation by further extending ⟨E', V'⟩.
Similarly, it is not possible to resolve the constraint violation
by deleting some pair (or a set of pairs) that was originally
in E ∪ V, as Lemma 2 and the notion of candidate solution
(Definition 2) guarantee that the resulting ⟨E', V'⟩ after such
deletion would be such that ABS(E', V') ⊈ ABS(E, V).

Finally, the case for minVS is very similar, as it is suf-
ficient to replace *p* ∈ *ABS(E,V)* with {*p* | (*p*,*r*) ∈
*VIOL(E,V)*} in the steps of the above procedure.

Lower bound PTIME cases. For maxES the claim fol-
lows from (Bienvenu et al. 2023, Theorem 2). We now pro-
vide the proof for the remaining two cases, namely minAS
and minVS. We start with minAS. The proof can be ob-
tained by slightly extending the proof sketch of (Bienvenu,
Cima, and Gutiérrez-Basulto 2022, Theorem 1), presented
in the appendix of that paper. Specifically, we give a reduc-
tion from Horn3SAT, a well-known PTIME-complete prob-
lem (Börger, Grädel, and Gurevich 1997). We recall that an
input to Horn3SAT is a pair (*F*, *x*<sub>w</sub>), where *F* = ⋀<sub>*i*=1</sub><sup>*m*</sup> *λ*<sub>*i*</sub> is
a formula over variables *X* = {*x*<sub>1</sub>, ..., *x*<sub>*n*</sub>} and *x*<sub>w</sub> ∈ *X*.
Each *λ*<sub>*i*</sub> is either a single propositional variable *x*<sub>*h*</sub> ∈ *X* or a
clause of the form (¬*x*<sub>*j*</sub> ∨ ¬*x*<sub>*k*</sub> ∨ *x*<sub>*h*</sub>), where *x*<sub>*j*</sub>, *x*<sub>*k*</sub>, *x*<sub>*h*</sub> ∈ *X*.
The problem is to decide whether *F* |= *x*<sub>w</sub>.

We use the fixed schema $S = \{R/4, C/2, W/2\}$.
Given an input $\phi = (F, x_w)$ to Horn3SAT over variables
$x_1, \dots, x_n$, we construct a database $D^\phi$ that contains:

• the fact C(c₁, c₂);

• the fact W(x<sub>w</sub>, x'<sub>w</sub>);

* for each *i* ∈ [n], if *λ*<sub>*i*</sub> is of the form *λ*<sub>*i*</sub> = *x*<sub>*h*</sub>, then we
include in *D*<sup>*φ*</sup> the facts *R*(*l*<sub>*i*</sub>, *t*, *t*, *x*<sub>*h*</sub>) and *R*(*l*<sub>*i*</sub>, *t*, *t*, *x*'<sub>*h*</sub>);
otherwise, i.e. *λ*<sub>*i*</sub> of the form (¬*x*<sub>*j*</sub> ∨ ¬*x*<sub>*k*</sub> ∨ *x*<sub>*h*</sub>), we include
in *D*<sup>*φ*</sup> the facts *R*(*l*<sub>*i*</sub>, *x*<sub>*j*</sub>, *x*<sub>*k*</sub>, *x*<sub>*h*</sub>) and *R*(*l*<sub>*i*</sub>, *x*'<sub>*j*</sub>, *x*'<sub>*k*</sub>, *x*'<sub>*h*</sub>).

We also let $E_{\text{triv}}$ be the following equivalence relation over $\text{Obj}(D^\phi)$: $E_{\text{triv}} = \text{EqRel}(\emptyset, \text{Obj}(D^\phi))$. It is straightforward to verify that both $D^\phi$ and $E_{\text{triv}}$ can be constructed in $\text{LOGSPACE}$ from $(F, x_w)$.

We now define the fixed ER specification $\Sigma_{\text{Horn3SAT}} = \langle \Gamma_O, \Delta \rangle$, where $\Gamma_O$ contains a single soft rule for objects $\sigma$ and a single hard rule for objects $\rho$:

• $\sigma = C(x, y) \dashrightarrow \text{EqO}(x, y)$

• $\rho = \exists z_l, z_1, z_2, z. R(z_l, z_1, z_2, x) \wedge R(z_l, z_1, z_2, y) \wedge C(z, z) \Rightarrow \text{EqO}(x, y)$

and $\Delta$ contains the following denial constraint $\delta$:

• $\delta = \forall y. \neg(W(y, y))$

The soft rule $\sigma$ allows to merge $c_1$ and $c_2$. If such a merge
is performed, then, for each variable $x_h$ such that there is a
$\lambda_i$ in $F$ of the form $\lambda_i = x_h$, the hard rule $\rho$ forces the merge
of $x_h$ with its copy $x'_h$, due to the presence of $R(l_i, t, t, x_h)$
and $R(l_i, t, t, x'_h)$. Subsequently, assuming that $c_1$ and $c_2$
have been merged, by a trivial induction argument on the
derivation length of the variables in $F$, it can be easily shown
that $F \models x_h$ if and only if the merge of $x_h$ with its copy $x'_h$
is forced by the hard rule $\rho$. Finally, the denial constraint $\delta$
forbids the merge of $x_w$ with its copy $x'_w$.

With the above intuition in mind, we now conclude the
proof by showing that $E_{\text{triv}} \in \text{OptSol}_{\text{minAS}}(D^{\phi}, \Sigma_{\text{Horn3SAT}})$
if and only if $F \models x_w$.

If part Suppose that $E_{\text{triv}} \notin \text{OptSol}_{\text{minAS}}(D^{\phi}, \Sigma_{\text{Horn3SAT}})$, i.e. there exists $E'$ such that $E' \in \text{Sol}(D^{\phi}, \Sigma_{\text{Horn3SAT}})$ and $\text{ABS}(E', \emptyset) \subsetneq \text{ABS}(E_{\text{triv}}, \emptyset)$. By construction, this implies that $(c_1, c_2) \in E'$, as $\text{ABS}(E_{\text{triv}}, \emptyset) = \{(c_1, c_2)\}$. Notice that, since $(c_1, c_2) \in E'$ and $E' \in \text{Sol}(D^{\phi}, \Sigma_{\text{Horn3SAT}})$, the following holds: for every variable $x_h$ for which $F \models x_h$, we have that the hard rule $\rho$ has forced the merge of $x_h$ with its copy $x'_h$, i.e. for every variable $x_h \in X$, we have $(x_h, x'_h) \in E'$ if and only if $F \models x_h$. Now, from the fact that $D^{\phi}_{E'} \models \delta$ because $E' \in \text{Sol}(D^{\phi}, \Sigma_{\text{Horn3SAT}})$, we must necessarily have that $(x_w, x'_w) \notin E'$. Thus, we can conclude that $F \not\models x_w$.

Only-if part Suppose that $F \nvDash x_w$. Let $E_F = \{(c_1, c_2)\} \cup \{(x_h, x'_h) \mid F \models x_h\}$, and let $E' = \text{EqRel}(E_F, \text{Obj}(D^\phi))$. Notice that, since by assumption $F \nvDash x_w$, we have that $(x_w, x'_w) \notin E'$, and therefore $D^\phi_{E'} \models \delta$. Furthermore, by construction we have that $D^\phi_{E'} \models \Gamma^o = \{\rho\}$, as we included in $E'$ all the pairs $(x_h, x'_h)$ such that $F \models x_h$. It follows that $E' \in \text{Sol}(D^\phi, \Sigma_{\text{Horn3SAT}})$. Finally, observe that $\text{ABS}(E', \emptyset) = \emptyset \subsetneq \text{ABS}(E_{\text{triv}}, \emptyset) = \{(c_1, c_2)\}$. Since $E' \in \text{Sol}(D^\phi, \Sigma_{\text{Horn3SAT}})$ and $\text{ABS}(E', \emptyset) \subsetneq \text{ABS}(E_{\text{triv}}, \emptyset)$, we derive that $E_{\text{triv}} \notin \text{OptSol}_{\text{minAS}}(D^\phi, \Sigma_{\text{Horn3SAT}})$.

We observe that the above proof works for the op-
timality criteria minVC as well (and actually, for
all the seven optimality criteria). To see this, note
that, for every input (F, x<sub>w</sub>) to Horn3SAT, one
can easily see that OptSol<sub>minAS</sub>(D<sup>φ</sup>, Σ<sub>Horn3SAT</sub>) =
OptSol<sub>minVC</sub>(D<sup>φ</sup>, Σ<sub>Horn3SAT</sub>).

Upper bound coNP cases. The claimed upper bound for
all the coNP cases follows from Theorem 1.

Lower bound for minAC and minVC. We give a re-
duction from the complement of 3SAT. We use the fixed
schema $S' = S \cup \{H/2\}$, where $S$ is as in the proof of Theo-
rem 1. Given an input $\varphi$ to 3SAT over variables $x_1, \dots, x_n$,
we construct a database $D^\varphi = D^\varphi \cup \{H(c_1, c_2)\}$, where
$D^\varphi$ is as in the proof of Theorem 1 while $c_1$ and $c_2$ are two
fresh constants. We also let $E^0 = \{(x_i, 0) \mid 1 \le i \le n\}$ and
$E = \text{EqRel}(E^0, \text{Obj}(D^\varphi))$.
We now define the fixed ER specification $\Sigma'_{3SAT} = \langle \Gamma_O, \Delta \rangle$, where $\Gamma_O$ contains two soft rules for objects:

* $\sigma = V(x) \wedge B(y) \dashrightarrow \text{EqO}(x, y)$

* $\sigma' = H(x, y) \dashrightarrow \text{EqO}(x, y)$

and $\Delta$ contains the following denial constraints (all the variables are implicitly universally quantified):

* $\delta_0 = \neg(F(y) \wedge T(y))$

* $\delta_1 = \neg(R_{ff}(y_1, y_2, y_3) \wedge T(y_1) \wedge T(y_2) \wedge T(y_3) \wedge H(z, z))$

* $\delta_2 = \neg(R_{fft}(y_1, y_2, y_3) \wedge T(y_1) \wedge T(y_2) \wedge F(y_3) \wedge H(z, z))$

* $\delta_3 = \neg(R_{ftf}(y_1, y_2, y_3) \wedge T(y_1) \wedge F(y_2) \wedge T(y_3) \wedge H(z, z))$

* $\delta_4 = \neg(R_{ftt}(y_1, y_2, y_3) \wedge T(y_1) \wedge F(y_2) \wedge F(y_3) \wedge H(z, z))$

* $\delta_5 = \neg(R_{tff}(y_1, y_2, y_3) \wedge F(y_1) \wedge T(y_2) \wedge T(y_3) \wedge H(z, z))$

* $\delta_6 = \neg(R_{tft}(y_1, y_2, y_3) \wedge F(y_1) \wedge T(y_2) \wedge F(y_3) \wedge H(z, z))$

* $\delta_7 = \neg(R_{ttf}(y_1, y_2, y_3) \wedge F(y_1) \wedge F(y_2) \wedge T(y_3) \wedge H(z, z))$

* $\delta_8 = \neg(R_{ttt}(y_1, y_2, y_3) \wedge F(y_1) \wedge F(y_2) \wedge F(y_3) \wedge H(z, z))$

It is straightforward to verify that both $\mathcal{D}^\varphi$ and $E$ can be constructed in LOGSPACE from $\varphi$. We start with the optimality criteria minAC, and show that $E \in \text{OptSol}_{\text{minAC}}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$ if and only if $\varphi$ is unsatisfiable. First, note that $|\text{ABS}(E, \emptyset)| = n+1$, i.e. there are $n+1$ active pairs in $\mathcal{D}^\varphi_E$ w.r.t. rules in $\Gamma_O$ that are not included in $E$, namely: $(c_1, c_2)$ and $(x_i, 1)$, for each $i \in [1, n]$. Furthermore, since $(c_1, c_2) \notin E$, we trivially derive that $\mathcal{D}^\varphi_E \models \Delta$, and therefore $E \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$.

If part Suppose that $E \notin \text{OptSol}_{\text{minAC}}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$, i.e. there exists $E'$ such that $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$ and $|\text{ABS}(E', \emptyset)| < |\text{ABS}(E, \emptyset)|$. Due to the simultaneous presence of $\sigma$ and $\delta_0$, it is easy to see that any $E'' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$ must be such that $|\text{ABS}(E'', \emptyset)| \ge n$. In other words, since by assumption $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$ and $|\text{ABS}(E', \emptyset)| < |\text{ABS}(E, \emptyset)|$, we have that $E'$ must contain the pair $(c_1, c_2)$ (which can be merged due to $\sigma'$) as well as either $(x_i, 0)$ or $(x_i, 1)$, for each $i \in [1, n]$ (but not both due to $\delta_0$).

We can thus define a valuation $\mu$ by setting $\mu(x_j) = 0$ if $(x_j, 0) \in E'$ and $\mu(x_j) = 1$ if $(x_j, 1) \in E'$, for every $j \in [n]$. Since $(c_1, c_2) \in E'$, from the assumption that $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$, and in particular the fact that the denial constraints $\delta_1, \dots, \delta_8$ are satisfied in $\mathcal{D}^\varphi_E'$, we conclude that $\mu$ is a valuation to the variables of $\varphi$ witnessing the satisfiability of $\varphi$.

Only-if part Suppose that $\varphi$ is satisfiable, and let $\mu: \{x_0, \dots, x_n\} \to \{0, 1\}$ be a satisfying valuation. Let $E_\mu = \{(x_i, \mu(x_i)) \mid 1 \le i \le n\} \cup \{(c_1, c_2)\}$, and let $E' = \text{EqRel}(E_\mu, \text{Obj}(\mathcal{D}^\varphi))$. Obviously, $|\text{ABS}(E', \emptyset)| = n < |\text{ABS}(E, \emptyset)| = n+1$. We now conclude the proof

by showing that $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$, which implies that $E \notin \text{OptSol}_{\text{minAC}}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$.

By construction, $(0, 1) \notin E'$, and therefore $\mathcal{D}^\varphi_{E'} \models \delta_0$. Furthermore, since by assumption the valuation $\mu$ satisfies all the clauses of $\varphi$, there cannot be any violations of the denial constraints $\delta_1$ to $\delta_8$, i.e. $\mathcal{D}^\varphi_{E'} \models \delta_k$, for every $k = 1, \dots, 8$. Thus, we conclude that $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$.

We observe that the above proof works for the optimality criteria minVC as well. To see this, note that, for every input $\varphi$ to 3SAT, one can easily see that $\text{OptSol}_{\text{minAC}}(\mathcal{D}^\varphi, \Sigma'_{3SAT}) = \text{OptSol}_{\text{minVC}}(\mathcal{D}^\varphi, \Sigma'_{3SAT})$. Lower bound for maxEC and maxSC.

It only remains to address the cases of the optimality criteria maxEC and maxSC. We do so by extending the reduction previously illustrated for minAC and minVC. Specifically, recall the schema $S'$, the ER specification $\Sigma'_{3SAT}$, and the database $\mathcal{D}^\varphi$. We define the following fixed schema $S''$, database $\mathcal{D}^\varphi$, and fixed ER specification $\Sigma''_{3SAT} = \langle \Gamma_O'', \Delta'' \rangle$:

* $S'' = S' \cup \{V'/1, P/2\}$;

* Given an input $\varphi$ to 3SAT over variables $x_1, \dots, x_n$, we construct a database $\mathcal{D}^\varphi = \mathcal{D}^\varphi \cup \{V'(x'_i) \mid 1 \le i \le n\} \cup \{P(x_i, x'_i) \mid 1 \le i \le n\}$;

* We also let $E^0 = \{(x_i, 0) \mid 1 \le i \le n\} \cup \{(x'_i, 1) \mid 1 \le i \le n\}$ and $E = \text{EqRel}(E^0, \text{Obj}(\mathcal{D}^\varphi))$;

* $\Gamma_O'' = \{\sigma, \sigma', \sigma''\}$ and $\Delta'' = \{\delta_0, \delta_1, \delta_2, \delta_3, \delta_4, \delta_5, \delta_6, \delta_7, \delta_8, \delta_9''\}$, where $\sigma, \sigma'$, $\delta_0, \delta_1, \delta_2, \delta_3, \delta_4, \delta_5, \delta_6, \delta_7$, and $\delta_8$ are as illustrated above in the ER specification $\Sigma'_{3SAT}$, while $\sigma'' = V'(x) \wedge Q(y) \dashrightarrow \text{EqO}(x, y)$ and $\delta_9'' = \forall y. \neg(P(y, y))$.

Intuitively, $\sigma''$ allows the copy $x'$ of each variable $x \in \bar{x}$ to merge with 0 or 1 (but not both due to $\delta_0$), while $\delta_9''$ says that a variable and its copy cannot merge with the same truth value. This guarantees that in each $E \in \text{OptSol}_{\text{maxEC}}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$ the equivalence class containing the constant 0 has the same cardinality as the equivalence class containing the constant 1.

It is straightforward to verify that both $\mathcal{D}^\varphi$ and $E$ can be constructed in LOGSPACE from $\varphi$. We start with the optimality criteria maxEC, and show that $E \in \text{OptSol}_{\text{maxEC}}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$ if and only if $\varphi$ is unsatisfiable. First, note that there are overall four equivalence classes in $E$, namely: $[0] = \{0\} \cup \{x_i \mid 1 \le i \le n\}$, $[1] = \{1\} \cup \{x'_i \mid 1 \le i \le n\}$, $[c_1] = \{c_1\}$, and $[c_2] = \{c_2\}$, and therefore $|E| = 2 \cdot (n+1)^2 + 2$. Furthermore, since $(c_1, c_2) \notin E$, we trivially derive that $\mathcal{D}^\varphi_E \models \Delta''$, and therefore $E \in \text{Sol}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$.

If part Suppose that $E \notin \text{OptSol}_{\text{maxEC}}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$, i.e. there exists $E'$ such that $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$ and $|E| < |E'|$. By construction, due to the presence of $\delta_9''$, it is easy to see that any $E'' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$ must be such that the equivalence classes $[0]$ and $[1]$ in $E''$ contain at most $n+1$ constants. In other words, since by assumption $E' \in \text{Sol}(\mathcal{D}^\varphi, \Sigma''_{3SAT})$ and $|E| < |E'|$, we have that $E'$ must contain the pair $(c_1, c_2)$ (which can be merged due to $\sigma'$) as well as either $(x_i, 0)$ and $(x'_i, 1)$ or $(x_i, 1)$ and $(x'_i, 0)$, for each $i \in [1, n]$.
We can thus define a valuation $\mu$ by setting $\mu(x_j) = 0$ if $(x_j, 0) \in E'$ and $\mu(x_j) = 1$ if $(x_j, 1) \in E'$, for every $j \in [n]$. Since $(c_1, c_2) \in E'$, from the assumption that $E' \in \text{Sol}(\mathbb{D}^{\varphi}, \Sigma''_{3\text{SAT}})$, and in particular the fact that the denial constraints $\delta_1, \dots, \delta_8$ are satisfied in $\mathbb{D}^{\varphi}_{E'}$, we can conclude that $\mu$ is a valuation to the variables of $\varphi$ witnessing the satisfiability of $\varphi$.

**Only-if part** Suppose that $\varphi$ is satisfiable, and let $\mu: \{x_0, \dots, x_n\} \to \{0, 1\}$ be a satisfying valuation. Let $E_\mu = \{(x_i, \mu(x_i)) \mid 1 \le i \le n\} \cup \{(c_1, c_2)\} \cup \{(x'_i, \neg(\mu(x_i))) \mid 1 \le i \le n\}$, where $\neg(\mu(x_i)) = 0$ if $\mu(x_i) = 1$ and $\neg(\mu(x_i)) = 1$ if $\mu(x_i) = 0$, for each $i \in [n]$. Let, moreover $E'$ be $E' = \text{EqRel}(E_\mu, \text{Obj}(\mathbb{D}^{\varphi}))$. Obviously, $|E| < |E'|$. We now conclude the proof by showing that $E' \in \text{Sol}(\mathbb{D}^{\varphi}, \Sigma''_{3\text{SAT}})$, which implies that $E \notin \text{OptSol}_{\text{maxEC}}(\mathbb{D}^{\varphi}, \Sigma''_{3\text{SAT}})$.

By construction, $(0, 1) \notin E'$, and therefore $\mathbb{D}^{\varphi}_{E'} \models \delta_0$. Furthermore, since by assumption the valuation $\mu$ satisfies all the clauses of $\varphi$, there cannot be any violations of the denial constraints $\delta_1$ to $\delta_8$, i.e. $\mathbb{D}^{\varphi}_{E'} \models \delta_k$, for every $k = 1, \dots, 8$. Finally, for no $i \in [n]$ we have that both $(x_i, 0)$ and $(x'_i, 0)$ occur in $E'$ as well as for no $i \in [n]$ we have that both $(x_i, 1)$ and $(x'_i, 1)$ occur in $E'$. Thus, $\mathbb{D}^{\varphi}_{E'} \models \delta''_9$ holds as well. We can therefore conclude that $E' \in \text{Sol}(\mathbb{D}^{\varphi}, \Sigma''_{3\text{SAT}})$.

We observe that the above proof works for the optimality criteria maxSC as well. To see this, note that, for every input $\varphi$ to 3SAT, one can easily see that $\text{OptSol}_{\text{maxEC}}(\mathbb{D}^{\varphi}, \Sigma''_{3\text{SAT}}) = \text{OptSol}_{\text{maxSC}}(\mathbb{D}^{\varphi}, \Sigma''_{3\text{SAT}})$. $\square$

# C ASP Encoding and Implementation

## C.1 Reified Format of ASP Encoding

In addition to the encoding format described in Section 4.1, database atoms (facts) can also be represented in a reified format. For example, the fact

author(t, x, n, d, p)

can be transformed into the set of reified facts

{tuple(author, t, 1, x), ..., tuple(author, t, 4, p)}.

While the reified format provides a more general and flexible representation, our preliminary experiments indicate that it leads to longer grounding times.

## C.2 Workflow Illustration

The workflow of ASPEN$^+$ illustrated in Figure 2, begins with an ASP encoding of an ER specification, a CSV/TSV dataset containing duplicate and potentially corrupted values (e.g., nulls), and a set of command-line options. A preprocessing component computes similarity scores between relevant constant pairs based on attributes referenced in similarity atoms. These scores, along with the dataset, are passed to a program transformer, which rewrites the encoding into the ASPEN$^+$ format and generates ASP facts for both database tuples and similarities. Finally, the ER controller, built on clingo, computes optimal solutions according to the specified input options.

# D Experiments

## D.1 Experimental Setup

**Datasets** Table 4 summarises the statistics of the datasets used in our experiments. Irrespective of the number of relations and attributes, datasets with more referential constraints exhibit greater structural complexity. Additionally, a higher number of distinct constants of datasets within the same domain (e.g. *Mu*, *MuC* and *MuCC*) indicates a greater degree of syntactic variation of constants. The original data sources are available at: **i) Imdb**: https:// contribute.imdb.com/dataset, **ii) Mu**: https://musicbrainz. org/doc/MusicBrainz_Database/Schema, **iii) Poke**: https:// pokemondb.net/about. We note that all synthetic datasets were created from clean database instances, hence do not contain errors other than syntactic variants.

<table><caption>Table 4: Dataset Statistics. #-columns represent the number of records, relations, attributes, referential constraints and duplicates, respectively.</caption><thead><tr><th>Name</th><th>#Rec</th><th>#Rel</th><th>#At</th><th>#Ref</th><th>#Dup</th><th>#Const</th></tr></thead><tbody><tr><td>Imdb</td><td>30k</td><td>5</td><td>22</td><td>4</td><td>6k</td><td>64k</td></tr><tr><td>ImdbC</td><td>30k</td><td>5</td><td>22</td><td>4</td><td>6k</td><td>66k</td></tr><tr><td>Mu</td><td>41k</td><td>11</td><td>72</td><td>12</td><td>15k</td><td>156k</td></tr><tr><td>MuC</td><td>41k</td><td>11</td><td>72</td><td>12</td><td>15k</td><td>160k</td></tr><tr><td>MuCC</td><td>41k</td><td>11</td><td>72</td><td>12</td><td>15k</td><td>166k</td></tr><tr><td>Poke</td><td>240k</td><td>20</td><td>104</td><td>20</td><td>4k</td><td>349k</td></tr></tbody></table>

**Similarity Measures and Metrics** We calculate the syntactic similarities of constants based on their data types (Bammani, Bertossi, and Vasiloglou 2017). (1) For numerical constants, we use the Levenshtein distance; (2) for short string constants (length< 25), we compute the score as the editing distance of two character sequences (Jaro-Winkler distance); (3) for long-textual constants (length≥ 25), we use the TF-IDF cosine score as the syntactic similarity measure. We adopt the commonly used metrics (Köpcke, Thor, and Rahm 2010) of Precision (P), Recall (R) and F1-Score (F₁) to examine the solutions derived from the specifications. Precision reflects the percentage of true merges in a solution and Recall indicates the coverage of true merges in a solution relative to the ground truth. The quality of a solution is then measured as $F1 = 2 \times \text{Precision} \times \text{Recall}/(\text{Precision} + \text{Recall})$.

**Environment** We implemented ASPEN$^+$ based on clingo 5.5$^1$ Python API. The ER programs follow the format of the ASPCore2.0 standard (Calimeri et al. 2020). All the experiments were run on a workstation using 3.8GHz AMD Ryzen Threadripper 5965WX cores and 128 GB of RAM.

## D.2 Optimisation Configuration Benchmarking

We evaluated the runtime performance of different solver configurations across multiple optimality criteria and datasets.

<footnote>$^1$https://potassco.org/clingo/python-api/5.5/</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 2: ASPEN⁺'s Workflow. Blue and yellow boxes indicate ASP programs and Python-based procedures, respectively.</figcaption></figure>

**Setup** For each dataset, we fixed the corresponding ER program and used ASPEN⁺ to compute between 1 and enumerate up to 50 optimal solutions, according to the criteria in Section 3.3, under a 128 GB RAM limit and a 5-hour time-out. For set-based optimization, we compared asprin and domain-specific heuristics (*heur*). For cardinality-based optimization, we evaluated: (i) optimization statements with multi-threaded solving using 36 CPU cores (*wc-36*), (ii) optimization statements combined with domain-specific heuristics (*wc+heur*), and (iii) asprin. We measured the solving time to compute the first optimal model ($t_s^1$) and the average solving time per model $t_s^n$, results are presented in Table 5 and Table 6.

**Results** For set-based optimization, *heur* consistently outperformed *asprin* across both $t_s^1$ and $t_s^n$ settings, often by substantial margins: it achieved speedups ranging from 1.3× to 15× on $t_s^1$ and from 146× to 909× on $t_s^n$. Notably, in both *MuC* and *MuCC*, *asprin* failed to complete due to memory overflow (m/o), while *heur* succeeded. These results indicate that *heur* is a significantly more effective configuration for computing set-optimal solutions compared to *asprin*.

A similar trend was observed for cardinality-based optimization, where *asprin* was consistently outperformed by both *wc+heur* and *wc-36*, often by substantial margins. While *wc+heur* frequently achieved better $t_s^1$ times than *wc-36* (1× to 2× faster), and significantly outperformed it in $t_s^n$—notably by 629k× when computing maxSC on *MuC*—it failed to complete within the time limit (t/o) when solving for minAC or minVC on more complex datasets, including *MuC*, *MuCC*, and *Poke*.

## D.3 Results on optimal solutions on simpler datasets

For the simpler datasets, *Imdb*, *ImdbC*, and *Mu*, we observe in Tables 7 and 8 that all optimization criteria produced a single optimal solution identical to maxES, resulting in the same $\bar{F}_1$.
<table><caption>Table 5: Comparisons of solving times for set-based optimisation across the datasets, using different methods: heuristic (heur) and asprin.</caption><thead><tr><th rowspan="2">Opt</th><th rowspan="2">Met.</th><th colspan="2">Imdb</th><th colspan="2">ImdbC</th><th colspan="2">Mu</th><th colspan="2">MuC</th><th colspan="2">MuCC</th><th colspan="2">Poke</th></tr><tr><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th></tr></thead><tbody><tr><td rowspan="2">maxES/SS</td><td rowspan="2">heur<br>asprin</td><td><strong>0.096</strong></td><td>N/A</td><td><strong>0.69</strong></td><td>N/A</td><td><strong>0.21</strong></td><td>N/A</td><td><strong>12.16</strong></td><td><strong>1.86</strong></td><td><strong>23.02</strong></td><td><strong>1.67</strong></td><td><strong>48.52</strong></td><td>N/A</td></tr><tr><td>1.48</td><td>N/A</td><td>10.53</td><td>N/A</td><td>3.16</td><td>N/A</td><td>174.24</td><td>m/o</td><td>251.70</td><td>m/o</td><td>76.51</td><td>N/A</td></tr><tr><td rowspan="2">minAS</td><td rowspan="2">heur<br>asprin</td><td><strong>0.18</strong></td><td>N/A</td><td><strong>0.64</strong></td><td>N/A</td><td><strong>0.44</strong></td><td>N/A</td><td><strong>12.8</strong></td><td><strong>1.7</strong></td><td><strong>23.01</strong></td><td><strong>1.54</strong></td><td><strong>51.58</strong></td><td><strong>0.06</strong></td></tr><tr><td>1.28</td><td>N/A</td><td>10.21</td><td>N/A</td><td>3.20</td><td>N/A</td><td>170.26</td><td>m/o</td><td>237.99</td><td>m/o</td><td>76.49</td><td>8.78</td></tr><tr><td rowspan="2">minVS</td><td rowspan="2">heur<br>asprin</td><td><strong>0.71</strong></td><td>N/A</td><td><strong>1.71</strong></td><td>N/A</td><td><strong>0.96</strong></td><td>N/A</td><td><strong>12.44</strong></td><td><strong>1.78</strong></td><td><strong>21.61</strong></td><td><strong>2.48</strong></td><td><strong>56.87</strong></td><td><strong>0.01</strong></td></tr><tr><td>3.77</td><td>N/A</td><td>13.62</td><td>N/A</td><td>4.73</td><td>N/A</td><td>175.04</td><td>m/o</td><td>242.49</td><td>m/o</td><td>74.78</td><td>9.09</td></tr></tbody></table>

<table><caption>Table 6: Comparisons of solving times for cardinality-based optimisation across the datasets, using different methods: 36-threaded weighted constraint (wc-36), combining heuristic and weighted constraint (wc+heur), and asprin.</caption><thead><tr><th rowspan="2">Opt</th><th rowspan="2">Met.</th><th colspan="2">Imdb</th><th colspan="2">ImdbC</th><th colspan="2">Mu</th><th colspan="2">MuC</th><th colspan="2">MuCC</th><th colspan="2">Poke</th></tr><tr><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th><th>t<sup>1</sup><sub>s</sub></th><th>t<sup>n</sup><sub>s</sub></th></tr></thead><tbody><tr><td rowspan="3">maxEC</td><td>wc-36</td><td>0.12</td><td>N/A</td><td>0.79</td><td>N/A</td><td>0.25</td><td>N/A</td><td>35.09</td><td>2.53</td><td>66.71</td><td>N/A</td><td><strong>48.52</strong></td><td>N/A</td></tr><tr><td>wc+heur</td><td><strong>0.11</strong></td><td>N/A</td><td><strong>0.75</strong></td><td>N/A</td><td><strong>0.22</strong></td><td>N/A</td><td><strong>23.05</strong></td><td><strong>1.75</strong></td><td><strong>33.77</strong></td><td>N/A</td><td><strong>48.58</strong></td><td>N/A</td></tr><tr><td>asprin</td><td>1.57</td><td>N/A</td><td>10.55</td><td>N/A</td><td>3.28</td><td>N/A</td><td>290.56</td><td>m/o</td><td>287.27</td><td>N/A</td><td>74.90</td><td>N/A</td></tr><tr><td rowspan="3">maxSC</td><td>wc-36</td><td>0.52</td><td>N/A</td><td>1.24</td><td>N/A</td><td>0.97</td><td>N/A</td><td><strong>30.1</strong></td><td><strong>12.09</strong></td><td>52.8</td><td>629.56</td><td>49.1</td><td>N/A</td></tr><tr><td>wc+heur</td><td><strong>0.41</strong></td><td>N/A</td><td><strong>1.12</strong></td><td>N/A</td><td><strong>0.65</strong></td><td>N/A</td><td>57.80</td><td>13.07</td><td><strong>50.68</strong></td><td><strong>0.001</strong></td><td><strong>48.82</strong></td><td>N/A</td></tr><tr><td>asprin</td><td>6.68</td><td>N/A</td><td>17.49</td><td>N/A</td><td>9.64</td><td>N/A</td><td>264.55</td><td>t/o</td><td>418.57</td><td>t/o</td><td>60.35</td><td>N/A</td></tr><tr><td rowspan="3">minAC</td><td>wc-36</td><td><strong>0.18</strong></td><td>N/A</td><td>0.89</td><td>N/A</td><td><strong>0.50</strong></td><td>N/A</td><td><strong>84.69</strong></td><td><strong>2.61</strong></td><td><strong>92.97</strong></td><td><strong>2.12</strong></td><td><strong>49.23</strong></td><td><strong>0.037</strong></td></tr><tr><td>wc+heur</td><td>0.21</td><td>N/A</td><td><strong>0.86</strong></td><td>N/A</td><td>0.61</td><td>N/A</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td></tr><tr><td>asprin</td><td>1.81</td><td>N/A</td><td>11.22</td><td>N/A</td><td>3.60</td><td>N/A</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td></tr><tr><td rowspan="3">minVC</td><td>wc-36</td><td><strong>0.93</strong></td><td>N/A</td><td><strong>1.91</strong></td><td>N/A</td><td><strong>1.22</strong></td><td>N/A</td><td><strong>48.97</strong></td><td><strong>5.66</strong></td><td><strong>67.82</strong></td><td><strong>8.42</strong></td><td><strong>49.11</strong></td><td><strong>1.15</strong></td></tr><tr><td>wc+heur</td><td><strong>0.88</strong></td><td>N/A</td><td>2.01</td><td>N/A</td><td><strong>1.22</strong></td><td>N/A</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td></tr><tr><td>asprin</td><td>4.24</td><td>N/A</td><td>14.52</td><td>N/A</td><td>5.52</td><td>N/A</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td><td>t/o</td></tr></tbody></table>

<table><caption>Table 7: Result on optimal solutions under different set-optimisation criteria over the datasets</caption><thead><tr><th>Data</th><th>Method</th><th>F&#x0304;<sub>1</sub></th><th>(P&#x0304; / R&#x0304;)</th><th>t<sup>1</sup><sub>s</sub></th><th>#e</th><th>t<sup>n</sup><sub>s</sub></th></tr></thead><tbody><tr><td rowspan="3">Imdb</td><td>maxES/SS</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.096</td><td>1</td><td>N/A</td></tr><tr><td>minAS</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.18</td><td>1</td><td>N/A</td></tr><tr><td>minVS</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.71</td><td>1</td><td>N/A</td></tr><tr><td rowspan="3">ImdbC</td><td>maxES/SS</td><td>99.13</td><td>99.39</td><td>98.87</td><td>0.69</td><td>1</td><td>N/A</td></tr><tr><td>minAS</td><td>99.13</td><td>99.39</td><td>98.87</td><td>0.64</td><td>1</td><td>N/A</td></tr><tr><td>minVS</td><td>99.13</td><td>99.39</td><td>98.87</td><td>1.71</td><td>1</td><td>N/A</td></tr><tr><td rowspan="3">Mu</td><td>maxES/SS</td><td>97.64</td><td>99.45</td><td>95.89</td><td>0.21</td><td>1</td><td>N/A</td></tr><tr><td>minAS</td><td>97.64</td><td>99.45</td><td>95.89</td><td>0.44</td><td>1</td><td>N/A</td></tr><tr><td>minVS</td><td>97.64</td><td>99.45</td><td>95.89</td><td>0.96</td><td>1</td><td>N/A</td></tr></tbody></table>

<table><caption>Table 8: Result on optimal solutions under different set-optimisation criteria over the datasets</caption><thead><tr><th>Data</th><th>Method</th><th>F&#x0304;<sub>1</sub></th><th>(P&#x0304; / R&#x0304;)</th><th>t<sup>1</sup><sub>s</sub></th><th>#e</th><th>t<sup>n</sup><sub>s</sub></th></tr></thead><tbody><tr><td rowspan="5">Imdb</td><td>maxEC</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.12</td><td>1</td><td>N/A</td></tr><tr><td>maxSC</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.52</td><td>1</td><td>N/A</td></tr><tr><td>minAC</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.18</td><td>1</td><td>N/A</td></tr><tr><td>minVC</td><td>99.27</td><td>99.39</td><td>99.14</td><td>0.93</td><td>1</td><td>N/A</td></tr><tr><td>maxEC</td><td>99.13</td><td>99.39</td><td>98.87</td><td>0.79</td><td>1</td><td>N/A</td></tr><tr><td rowspan="5">ImdbC</td><td>maxSC</td><td>99.27</td><td>99.39</td><td>99.14</td><td>1.24</td><td>1</td><td>N/A</td></tr><tr><td>minAC</td><td>99.13</td><td>99.39</td><td>98.87</td><td>0.89</td><td>1</td><td>N/A</td></tr><tr><td>minVC</td><td>99.13</td><td>99.39</td><td>98.87</td><td>1.91</td><td>1</td><td>N/A</td></tr><tr><td>maxEC</td><td>97.64</td><td>99.45</td><td>95.89</td><td>0.25</td><td>1</td><td>N/A</td></tr><tr><td>minAC</td><td>97.64</td><td>99.45</td><td>95.89</td><td>0.97</td><td>1</td><td>N/A</td></tr></tbody></table>