On Combining Collective Entity Resolution and Repairing (Extended Abstract)

Abstract

This work summarizes the salient aspects of our recent work [1], about combining collective entity resolution and repairing.

Keywords

• eol>Data Quality
• Declarative Framework
• Logical Rules and Constraints
• Entity Resolution
• Database Repairing

-

Data quality (DQ) is one of the most fundamental prob- of constants and adopting the well-known class of delems in data management, encompassing several issues nial constraints [ 8 ], which generalize the conditional FDs such as entity resolution (ER), consistency, completeness, considered in [ 5 ], to express consistency requirements. currency, etc. The diferent facets of DQ have mostly A hard rule takes the form (, ) ⇒ EqO(, ), where been considered in isolation, giving rise to increasingly (, ) is a conjunctive query (CQ) composed by standard sophisticated methods over the years. However, datasets relational atoms and atoms using similarity predicates can be expected to sufer from multiple DQ issues. (≈ ), and EqO is a special symbol used to store merges.

In our work, we propose a novel declarative framework Intuitively, such a rule states that (1, 2) being an anfor jointly tackling the ER and the consistency issues. The swer to provides suficient conditions for concluding ER task is the problem of identifying/matching/merg- that 1 and 2 refer to the same entity. Soft rules have ing pairs of syntactically diferent entity references (con- a similar form (, ) ‧‧➡ EqO(, ), but state instead stants occurring in a database) that are actually denoting that (1, 2) being an answer to provides reasonable the same real-world entity [ 2 ]. We consider so-called evidence for 1 and 2 denoting the same entity. collective ER [ 3 ], in which we consider multiple tables and/or entity types together, e.g. a merge of a pair of au- Definition 1. A DQ specification takes the form Σ = thors may trigger a subsequent merge of a pair of papers. ⟨Γ , ∆ ⟩, where Γ = Γ ℎ ∪ Γ is a finite set of hard and soft As regards data consistency, we assume that the consis- rules, and ∆ is a finite set of denial constraints. tency requirements are specified by means of declarative constraints, and we consider the problem of restoring The semantics of Replace is based on the notion of consistency through the removal of conflicting database (optimal) solutions to database-specification pairs (, Σ) . facts, as in classical database repairing [ 4 ]. More specifically, a solution for a pair (, Σ) takes the

The idea of combining ER and repairing has been pio- form of a pair = (, ), where is a subset of and neered in [ 5 ], with the goal of generating a single repair is an equivalence relation over the constants appearing of optimal cost. On the contrary, to the best of our knowl- in the database ′ = ∖ . Intuitively, indicates the edge, ours is the first work to explore the computational facts to remove from while expresses the constants properties of reasoning over a space of alternative solu- to merge, i.e. all constants from the same equivalence tions for the combined task, analogously to how consis- class are deemed to be references to the same entity. tent query answering reasons over alternative repairs [ 6 ]. Formally, a pair = (, ) is a solution to a

Our framework, called Replace, builds upon the re- database-specification pair (, Σ) if ⊆ and is an cently proposed Lace framework [ 7 ], employing hard ER solution to ( ∖ , Σ) in the sense of [ 7 ]. We recall and soft rules to define mandatory and possible merges that in the latter work ER solutions are build ‘dynamically’, which means that (soft and hard) rule bodies are evaluated on induced databases resulting from applying the already ‘derived’ merges.

ENIGMA-23, September 03–04, 2023, Rhodes, Greece " [e-mail] (M. Bienvenu); [e-mail] (G. Cima); [e-mail] (V. Gutiérrez-Basulto) Example 1. Consider Figure 1. First note that ex ̸|= 1 0000-0001-6229-8103 (M. Bienvenu); 0000-0003-1783-5605 as both 3 and 4 are chairs of KR-12. Notice, however, that (G. Cima); 0000-0002-9421-8566 (V. Gutiérrez-Basulto)

© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License 3 and 4 can be merged due to 1, which resolves the inCPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) consistency. So we obtain a first solution 1 = (1, 1), aid 1 2 3 4

Author(aid, email, inst)

email [e-mail] [e-mail] [e-mail] [e-mail] inst Tokyo Tokyo NYU NYU pid cid 3 3 2 3 4 1 = ¬(∃, , f , , , c, ′, ′, f ′, c′. Paper(, , f , , , c) ∧ Paper(′, ′, f ′, , , c′) ∧ c ̸= c′) 2 = ¬(∃, , , , . Paper(, , , , , )) 1 = Paper(, , f , , , c) ∧ Paper(, ′, f , , , c) ∧ ≈ ′ ⇒ EqO(, ) 1 = Author(, , ) ∧ Author(, ′, ) ∧ ≈ ′ ‧‧➡ EqO(, ) where 1 = ∅ and 1 is the equivalence relation induced about alternative solutions. For ∈ {Mer, Del, Par}, by {(3, 4)}. Constants 1 and 2 can also be merged we say that a tuple ⃗ is an -certain answer (resp. due to 1. However, if we merge them, then the resulting possible answer) to a query w.r.t. (, Σ) if ⃗ is an andatabase is such that: ( i) 2 is violated because the first au- swer to in every (resp. some) -optimal solution. We thor of paper 3 is the chair of the conference where 3 was use -certAns(, , Σ) and -possAns(, , Σ) for published, and ( ii) 1 and 2 must be merged due to 1. the sets of -certain and -brave answers. We further So we have a second solution 2 = (2, 2), where 2 introduce the novel notions of most informative possicontains the tuples with pid 3 and 2 is the equivalence ble and certain answers (-MIpossAns(, , Σ) and relation induced by {(1, 2), (3, 4), (1, 2)}. MIcertAns(, , Σ) ), which take the form of tuples of sets of constants. Most informative answers ofer a more

Among all the solutions, it is natural to focus only compact presentation of query results, avoiding the outon the ‘best’ ones, i.e. those maximizing the merges per- put of distinct but equivalent tuples. In our running exformed and minimizing the facts removed. These two ample, this would mean returning ({3, 4}) rather than criteria may conflict, as deleting more facts may enable both (3) and (4) when querying for chair of KR-12. more merges. We thus consider three natural ways to We refer readers to the full paper for formal definitions. compare solutions: give priority to the maximization Aside from introducing the new framework, we outof merges (Mer), give priority to the minimization of lined the precise data complexity of the following tasks: deletions (Del), or adopt the Pareto principle and accord equal priority to both criteria (Par). Specifically, the preorders ≺ Mer, ≺ Del, and ≺ Par are defined as follows: • (, ) ≺ Mer (′, ′) if either ( i) ⊂ ′ or (ii)

⊆ ′ and ′ ⊂ ; • (, ) ≺ Del (′, ′) if either ( i) ′ ⊂ or (ii)

′ ⊆ and ⊂ ′; • (, ) ≺ Par (′, ′) if either ( i) ⊂ ′ and ′ ⊆ or (ii) ′ ⊂ and ⊆ ′.

In future work, we plan to develop a prototype imple

For ∈ {Mer, Del, Par}, a solution for (, Σ) is mentation of Replace based on logic-based technologies, an ⪯ -optimal solution for (, Σ) if there is no solution such as answer set programming (ASP). Most informa ′ for (, Σ) such that ≺ ′, and denote by tive certain answers will require special treatment, due Sol (, Σ) the set of ⪯ -optimal solutions for (, Σ) . to their DP2 complexity, which goes beyond what is supported by ASP. It would also be relevant to integrate Example 2. Recall Example 1. We have that SolMer = similarity measures defined via machine learning pred{2}, SolDel = {1}, and SolPar = {1, 2}. icates, in the style of [ 9 ], and to allow for both global merges (the ones considered here) and local merges (suit

As there may be many optimal solutions, we adopt the able when merging values rather than references), as has notions of possible and certain query answers to reason been recently considered in [ 10, 11 ]. • -MaxRec: decide whether ∈ Sol (, Σ) ; • -CertAns (resp. -PossAns): decide whether ⃗ ∈ -certAns(, , Σ) (resp. ⃗ ∈ possAns(, , Σ) ); • -MIcertAns (resp. -MIpossAns): decide whether a tuple of sets of constants ⃗ is such that ⃗ ∈ -MIcertAns(, , Σ) (resp. ⃗ ∈ MIpossAns(, , Σ) ).

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

tity resolution and query answering in knowledge bases, in: Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning (KR 2023), 2023.

References

[1] M. Bienvenu , G. Cima , V. Gutiérrez-Basulto, REPLACE: A logical framework for combining collective entity resolution and repairing , in: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023 ), 2023 .

[2] P. Singla , P. M. Domingos , Entity resolution with markov logic , in: Proceedings of the Sixth IEEE International Conference on Data Mining (ICDM 2006 ), 2006 , pp. 572 - 582 .

[3] I. Bhattacharya , L. Getoor, Collective entity resolution in relational data , ACM Transactions on Knowledge Discovery from Data 1 ( 2007 ) 5 .

[4] J. Chomicki , J. Marcinkowski , Minimal-change integrity maintenance using tuple deletions , Information and Computation 197 ( 2005 ) 90 - 121 .

[5] W. Fan , S. Ma, N. Tang , W. Yu , Interaction between record matching and data repairing , Journal of Data and Information Quality 4 ( 2014 ) 16 : 1 - 16 : 38 .

[6] M. Arenas , L. E. Bertossi , J. Chomicki , Consistent query answers in inconsistent databases , in: Proceedings of the Eighteenth ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems (PODS 1999 ), 1999 , pp. 68 - 79 .

[7] M. Bienvenu , G. Cima , V. Gutiérrez-Basulto, LACE: A logical approach to collective entity resolution , in: Proceedings of the Forty-First ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2022 ), 2022 , pp. 379 - 391 .

[8] L. E. Bertossi , Database Repairing and Consistent Query Answering, Synthesis Lectures on Data Management , Morgan & Claypool Publishers, 2011 .

[9] T. Deng , W. Fan , P. Lu , X. Luo , X. Zhu , W. An, Deep and collective entity resolution in parallel , in: Proceedings of the Thirty-Eighth IEEE International Conference on Data Engineering (ICDE 2022 ), 2022 , pp. 2060 - 2072 .

[10] M. Bienvenu , G. Cima , V. Gutiérrez-Basulto , Y. Ibáñez-García , Combining global and local merges in logic-based entity resolution , in: Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning (KR 2023 ), 2023 .

[11] R. Fagin , P. G. Kolaitis , D. Lembo , L. Popa , F. Scafoglieri , A framework for combining en-