Combining Entity Resolution and Query Answering in Ontologies: A Formal Conceptual Framework

Abstract

This paper reports on a recent formal framework for integrating entity resolution and query answering within ontologies governed by rules expressed in the form of tuple-generating dependencies and equality-generating dependencies. Our framework outlines the semantics of the ontology by defining special instances involving equivalence classes of entities and sets of values. The former serve to gather entities referring to the same real-world object, and the latter to catalog alternative attribute values. This approach not only addresses entity resolution but also overcomes potential inconsistencies within the data. Additionally, we introduce a tailored chase procedure for this framework, ensuring non-failure and ultimately yielding a universal solution. This universal solution, in turn, can be used to obtain certain answers to conjunctive queries.

Keywords

• eol>Formal Conceptual Framework
• Entity Resolution
• Query Answering
• Knowledge Bases
• Ontology
• Chase
• Universal Model
• tuple-generating dependencies
• equality-generating dependencies
• entity-resolution rules

1. Introduction

Entity resolution is the problem of determining whether different data records refer to the same real-world object, such as the same individual or the same organization, etc. [ 1, 2 ].

In this discussion paper we summarize a framework recently appeared in [ 3 ] for entity resolution in combination with query answering in the context of ontologies consisting of ground atoms and rules specified as tuple-generating dependencies (tgds) and equality-generating dependencies (egds). These rules have been widely investigated in databases and knowledge representation, e.g. in [ 4, 5, 6, 7 ]; they can express axioms that are used in Description Logics (DLs) [ 8 ], as well as in knowledge bases that are similar to Datalog +/- programs [ 9 ]. Additionally, egds are employed to express typical entity resolution rules that one may write in practice, as in [ 10 ]. These rules specify the conditions under which to entities have to be made equal, to say, for instance, that two persons are indeed the same person if they have similar names and the same date of birth. In the following, we call such rules entity-egds, whereas we name value-egds the egds imposing equality on values, used, e.g., to express that a person has only one name.

In the proposed framework, the first challenge we face is to come up with a consistent way to complete or modify the original ontology, while respecting all its rules. To this aim we propose a new notion of valid models, called ontology solutions. They must satisfy all entity resolution rules along with all other ontology rules. Furthermore, the solutions must include all original data (i.e., no information is ever dropped or altered). Our approach is guided by the intuitive principle that for each real-world object there must be a single node in the solution that represents all “equivalent” entities denoting the object. To achieve this, we use equivalence classes of entities that become first-class citizens in our framework. In addition, we relax the standard way in which value-egds are satisfied by allowing solutions to use sets of values. Intuitively, we interpret egds as matching dependencies [ 11, 1, 12 ]. That is, when the conditions expressed by (the body of) an entity-egd or a value-egd hold in the data, and thus two entities or two values must be made equal, we combine them through a merging function that amounts to taking the union of all the alternatives. In this way, we group all entities that denote the same real-world object into a unique set, which turns out to be an equivalence class. Similarly, when two values exist where only one value is instead allowed according to the TBox, we explicitly form their union. Note that we consider the union of entities a “global” feature for a solution, that is, an entity may belong to exactly one equivalence class; in contrast, the union of values is “local” to the context in which a value occurs, that is, a particular value may belong to more than one set of values.

We also remark that the semantics we adopt for value-egds allows us to always have a solution (that is, a model) for an ontology, even when there are no models according to the standard ifrst-order semantics. Indeed, if a value-egd enforces the equality of different values, we collect together such values, whereas first-order logic would conclude that the ontology is inconsistent.

Besides formalizing the aforementioned ideas, our contribution is on how to combine entity resolution with query answering. In this respect, () we define universal solutions and show that, as for standard tgd and egd semantics, universal solutions can be used to obtain the certain answers of Conjunctive Queries (CQs); () we propose a variant of the classical chase procedure [ 4, 5 ] tailored to our approach; () we show that, when the chase procedure terminates, it returns a universal solution (and thus we have an algorithm for computing the certain answers to CQs).

In the following, we discuss our findings mainly by examples and refer the reader to [ 3 ] for a complete formal treatment.

2. Framework

We refer the reader to [ 13 ] for an introduction to equivalence classes and relations. In the following, let ∼ be an equivalence relation, we write [] to denote the equivalence class containing , instead of []∼ . Moreover, we may write, for example [, , ]∼ (or simply [, , ]) to denote the equivalence class consisting of the elements , , and .

Syntax. An atom is an expression of the form (1, . . . , ), where is a symbol to denote an -ary ontology or built-in predicate, i.e. a pre-interpreted predicate like the Jaccard similarity (JaccSim). Each is either a variable or a constant, which can be in turn a value or an entity, the latter used to denote a real-world object. We impose that when is a built-in predicate, constants occurring in (1, . . . , ) are only values. A ground atom is an atom with no variables.

A conjunction () of atoms is an expression 1(1) ∧ . . . ∧ (), where each ( ) is an atom such that each variable in the tuple of terms is among those in the tuple of variables.

An ontology is a pair ( , ), consisting of a TBox and a ABox . The TBox is a finite set of tuple-generating dependencies (tgds) and equality-generating dependencies (egds).

A tgd is a formula of the form:

∀ (() → ∃ (, )), where () and (, ) are conjunctions of atoms, such that and have no variables in common and (, ) is built-in free and, for simplicity, constant-free. As in [ 5 ], we assume that all variables in appear in (), but not necessarily in (, ). We call () the body of the tgd, and (, ) the head of it.

An egd is a formula of the form:

∀ (() → = ), where () is a conjunction of atoms and and are distinct variables occurring in (), such that either both and are entity-variables (in which case we have an entity-egd) or both and are value-variables (in which case we have a value-egd). We call () the body of the egd.

In the examples, for simplicity, we will omit the universal quantification in tgds and egds.

Example 1. Let be the TBox consisting of the rules:

(1) Name(1, 1) ∧ Name(2, 2) ∧ JaccSim(1, 2, 0.7) → 1 = 2 (2) Name(, 1) ∧ Name(, 2) → 1 = 2 (3) HPhone(, 1) ∧ HPhone(, 2) → 1 = 2 (4) HPhone(1, ) ∧ HPhone(2, ) → SameHouse(1, 2, )

Here 1, 2, are entity-variables, i.e., occur in predicate arguments ranging over entities, whereas 1, 2, 1, 2, are value-variables, i.e., occur in predicate arguments ranging over values. The predicates have the meaning suggested by their names. In particular, the predicate Name maintains the individual’s name, HPhone stores their home phone contact, whereas SameHouse associates individuals living in the same house with their phone number. Each of the four rules makes an assertion about the predicates. In particular, the first rule ( 1) states that if the Jaccard similarity of two names is higher then 0.7, then these names are associated to the same individual. The TBox also says that everyone can have only one name (2) and only one landline phone number (3), and that two individuals with the same landline phone number live in the same house (4).

The ABox of an ontology is a finite set of ground atoms of the form (1, . . . , ) where each is an entity or a value.

Example 2. Let be the ABox consisting of the atoms

(1) Name(Doe1, John Doe), (2) HPhone(Doe1, 358) (3) Name(Doe2, Johnny Doe), (4) HPhone(Doe2, 635) (5) Name(Doe3, Mary Doe), (6) HPhone(Doe3, 358)

In words, the ABox specifies that Doe1 has name John Doe and home phone number 358, Doe2 has name Johnny Doe and home phone number 635, Doe3 has name Mary Doe and phone number 358.

Semantics. We assume to have countably infinite many entity-nulls and value-nulls (note that we consider generic tgds, i.e. possibly having existential variables in the rule head, even though, for space limits we do not provide examples of this kind). The semantics of the ontology is given using special ABoxes, called ontology instances, whose ground atoms have components that are either equivalence classes of entities and entity-nulls, which we call E-sets, or non-empty sets of values and value-nulls, which we call V-sets.

Ontology Instance (Definition 1 of [ 3 ]). An instance ℐ for an ontology w.r.t. an equivalence relation ∼ is a set of facts (1, . . . , ) such that is a -ary predicate in , and each is either an E-set w.r.t. ∼ or a V-set.

Example 3. Let = ( , ) be an ontology such that and are as in Example 1 and in Example 2, respectively. Consider the following set ℐ of facts. (1) Name([Doe1, Doe2], {John Doe, Johnny Doe}) (2) HPhone([Doe1, Doe2], {358, 635}) (3) Name([Doe3], {Mary Doe}) (4) HPhone([Doe3], {358}) (5) SameHouse([Doe1, Doe2], [Doe3]) (6) SameHouse([Doe3], [Doe1, Doe2]) ℐ is an instance for w.r.t. the equivalence relation ∼ over the set {Doe1, Doe2, Doe3} such that Doe1 ∼ Doe2, i.e. Doe1 and Doe2 are in the same equivalence class and Doe3 is the only element of another obviously disjoint equivalence class.

To define the notions of satisfaction of tgds and egds by an instance, we first introduce the notion of an assignment from a conjunction () of atoms to an instance ℐ for an ontology . Assignment (Definition 3 of [ 3 ]). An assignment from a conjunction () of atoms to an instance ℐ is a mapping from the variables and values in () to E-sets and V-sets of ℐ such that • each entity-variable is mapped to an E-set; • different occurrences of a value-variable are mapped to V-sets with non-empty intersection; • each value is mapped to a V-set , such that ∈ ; • for each atom (, , ) of (), where is a variable, is an entity and is a value, ℐ contains a fact of the form ( (), [], ()) (the definition generalizes in the obvious way for atoms of different form).

Example 4. Let ℐ be the instance in Example 3. A possible assignment from the body of rule (4) of Example 1 to ℐ is given below:

We are now ready to define the semantics of tgds and egds.

Semantics of tgds (Definition 4 of [ 3 ]). An instance ℐ for an ontology satisfies a tgd ∀(() → ∃ (, )) if for each assignment from () to ℐ there is an assignment ′ from (, ) to ℐ such that, for each in • () = ′(), if is an entity-variable • the intersection of V-sets assigned by to each occurrence of in () is contained in the intersection of V-sets assigned by ′ to each occurrence of in (, ), if is a value-variable Example 5. Let ℐ be the instance in Example 3 and (4) be the tgd in Example 1. Let be an assignment from the body of (4) to ℐ and let ′ be an assignment from the head of (4) to ℐ as described below: Since is the only assignment from the body of (4) to ℐ, we conclude that ℐ satisfies (4). Semantics of egds (Definition 4 of [ 3 ]). An instance ℐ for an ontology satisfies an egd ∀(() → = ) if each assignment from () to ℐ is such that () = ()

Note that according to the above definition, in every assignment () to ℐ all occurrences of and must be mapped to the same set, for an egd to be satisfied by an ontology instance. Example 6. Let ℐ be the instance in Example 3 and (3) be the egd in Example 1. Let be an assignment from the body of (3) to ℐ as described below: The assignment trivially enjoys the conditions of the definition of egd satisfaction. It is easy to see that the same holds for all assignments from the body of (3) to ℐ, and thus we conclude that ℐ satisfies (3).

Finally, we define when an instance is a solution for an ontology.

Ontology Solution (Definition 5 of [ 3 ]). Let = ( , ) be an ontology and ℐ be an instance. ℐ is a solution for if ℐ satisfies and , i.e.: • ℐ satisfies if ℐ satisfies every tgd and egd in . • ℐ satisfies if it satisfies every ground atom (1, . . . , ) in . A ground atom is satisfied if there is a fact (1, . . . , ) in ℐ such that ∈ , for 1 ≤ ≤ .

Among all ontology solutions we are interested to the so-called universal solutions, which exhibit special properties with respect to the task of query answering (see, e.g., [ 5, 14, 15 ]). Universal Solution (Definitions 8 of [ 3 ]). A solution for an ontology is universal if, for every solution ℐ for , there is a homomorphism ℎ : → ℐ.

The notion of homomorphism used in the previous definition is tailored to our framework and suitably considers E-sets and V-sets occurring in instances. Informally, for an instance ℐ, we denote with under (ℐ) the set containing all entities, entity-nulls, values, and value-nulls occurring in ℐ. Then, let ℐ1 and ℐ2 be two instances, an homomorphism ℎ : ℐ1 → ℐ2 is a structure-preserving mapping from under (ℐ1) to under (ℐ2) (we refer to Definition 7 of [ 3 ] for further details).

3. Query Answering

A conjunctive query (CQ) () is a formula ∃ (, ), where (, ) is a built-in free conjunction of atoms.

Answers to CQs. The answer ℐ to a CQ (1, . . . , ) on an instance ℐ is the set of all tuples ⟨1, . . . , ⟩ such that there is an assignment from to ℐ for which: • = (), if is an entity-variable; • , is the intersection of the V-sets assigned to the various occurrences of , if is a value-variable.

Example 7. Below we give an example of query, assignment from the query to the instance ℐ of Example 3, and answers to the query.

It is easy to see that ℐ = {⟨{358}⟩}.

When querying an ontology , we are interested in reasoning over all solutions for . We thus adapt the classical notion of certain answers to our framework. To this aim, we need some preliminary definitions. A tuple = ⟨1, . . . , ⟩ is null-free if each is non-empty and contains no nulls. Let = ⟨1, . . . , ⟩ and ′ = ⟨1′ , . . . , ′⟩ be two tuples of E-sets and V-sets, we say that ′ dominates , denoted ≤ ′, if ⊆ ′, for all 1 ≤ ≤ . Certain Answers (Definition 9 of [ 3 ]). A null-free tuple of E-sets and V-sets is a certain answer to a CQ w.r.t. an ontology if 1. for every solution ℐ for , there is a tuple ′ ∈ ℐ such that ≤ ′ 2. there is no null-free tuple ′ that satisfies (1) and < ′ We write (, ) to denote the set of certain answers to w.r.t.

We are now able to present the main result of this section, which asserts that universal solutions can be used to compute certain answers to CQs in our framework.

Compute Certain Answers over a Universal Solution (Theorem 1 of [ 3 ]). Let be a CQ, let be an ontology, and let be a universal solution for . Then (, ) = ↓ .

The operator ↓ first eliminates nulls occurring in , then, in the resulting set, it eliminates tuples that are dominated by other tuples (see [ 3 ] for the details).

4. Computing Universal Solution

In order to compute the universal solution that can be used to obtain the certain answers to CQs, we adapt here the well-known notion of restricted chase [ 4, 16, 5, 15 ] to our framework. Intuitively, given an ontology = ( , ), we define a procedure that starts from an instance for “specular” to the ABox , which we call the base instance of , and incrementally constructs an instance that satisfies the tgds and the egds of the TBox .

Example 8. Let = ( , ) be an ontology such that and are as in Example 1 and in Example 2, respectively. The base instance of is as follows: (1) Name([Doe1], {John Doe}) (2) Name([Doe2], {Johnny Doe}) (3) HPhone([Doe1], {358}) (4) HPhone([Doe2], {635}) (5) Name([Doe3], {Mary Doe}) (6) HPhone([Doe3], {358})

A universal solution for is obtained by iteratively applying three chase rules, one for each kind of rule that may occur in , as long as they are triggered in the (current) instance. (i) entity-egd chase rule. An entity-egd ∀(() → = ) is triggered in an instance ℐ if there is an assignment from () to ℐ such that () ̸= (). Then, the chase substitutes () and () everywhere ℐ with () ∪ ().

Example 9. Let ℐ0 be the starting instance in Example 8 and (1) be the e-egd Name(1, 1) ∧ Name(2, 2) ∧ JaccSim(1, 2, 0.7) → 1 = 2. The egd (1) is triggered in ℐ0 because of (1),(2). Its application generates ℐ1, which is as follows: (7) Name([Doe1, Doe2], {John Doe}) (8) Name([Doe1, Doe2], {Johnny Doe}) (9) HPhone([Doe1, Doe2], {358}) (10) HPhone([Doe1, Doe2], {635}) (5) Name([Doe3], {Mary Doe}) (6) HPhone([Doe3], {358}) ℐ1 is obtained from ℐ0 by replacing everywhere [Doe1] and [Doe2] with [Doe1, Doe2]. (ii) value-egd chase rule. Similarly to the entity-edg case, when a value-egd forces two different sets of values to be equated, we take the union of the two sets and modify the instance accordingly. Example 10. Let ℐ1 be the instance in Example 9 and (3) be the value-egd HPhone(, 1) ∧ HPhone(, 2) → 1 = 2. The egd (3) is triggered in ℐ1 because of (9),(10). Its application generates ℐ2, shown below: (7) Name([Doe1, Doe2], {John Doe}) (8) Name([Doe1, Doe2], {Johnny Doe}) (11) HPhone([Doe1, Doe2], {358, 635}) (6) HPhone([Doe3], {358}) (5) Name([Doe3], {Mary Doe}) ℐ2 is obtained from ℐ1 by replacing in 9 and 10 {358} and {635} with their union {358, 635}. (iii) tgd chase rule. A tgd ∀ (() → ∃ (, )) is triggered in an instance ℐ if there is an assignment from () to ℐ such that there is no assignment ′ from (, ) to ℐ, as required by the definition of tgd satisfaction. Then, the chase adds new facts to ℐ so that ′ does exist in the obtained instance.

Example 11. Let ℐ2 be the instance in Example 10 and (4) be the tgd HPhone(1, ) ∧ HPhone(2, ) → SameHouse(1, 2, ). The tgd (4) is triggered in ℐ2 because of (11),(6). Its application generates ℐ3, shown below: (7) Name([Doe1, Doe2], {John Doe}) (8) Name([Doe1, Doe2], {Johnny Doe}) (11) HPhone([Doe1, Doe2], {358, 635}) (6) HPhone([Doe3], {358}) (5) Name([Doe3], {Mary Doe}) (12) SameHouse([Doe1, Doe2], [Doe3], {358}) ℐ3 is obtained by adding SameHouse([Doe1, Doe2], [Doe3], {358}) to ℐ2.

The chase procedure terminates when it produces an instance for which no rule in the TBox is applicable. One such sequence = ℐ0, ℐ1, . . . , ℐ is called a finite chase and the result of the chase, chase(, ), coincides with ℐ.

The result of the chase is an Universal Solution (Theorem 2 of [ 3 ]). If is an ontology and is a finite chase for , then chase(, ) is a universal solution for .

Given the ontology composed by the TBox in Example 1 and the ABox in Example 2, it is possible to construct a finite chase sequence ℐ0, ℐ1, ℐ2, ℐ3, . . . ℐ, where ℐ0, ℐ1, ℐ2, ℐ3 are as in Examples 8–11 and ℐ is the universal solution of Example 3 (and thus ℐ coincides with the set of certain answers to ).

5. Conclusion and Future Works

In this paper we reported on a principled approach to query answering and entity resolution that may be relevant to several areas, like Data Exchange [ 5 ] and Integration [ 17 ], or Ontology-based Data Access [ 18, 19 ] considered the central role played by tgds and egds in those contexts, but also in Information Extraction [20, 21, 22] or in general for data-intensive tasks [23]. Our investigation is however still initial and several aspects need further study. Although not explicitly shown in this document, tgds could give rise to an infinite universal solution because of the possible infinite creation of existentials. We left open how to obtain a universal solution from a non-terminating chase sequence. Solving this case would extend our approach even to settings where all universal solutions are infinite. Though not fully materializable, the infinite chase is generally considered an important theoretical tool to show properties of query answering, such as rewritability [ 15 ], possibly combined with partial materialization of the chase result [24]. Morover our framework intentionally considers expressive tgds and egds, in order to encompass several popular ontology languages. It is however well-known that without suitable restrictions query answering (and reasoning in general) is undecidable [25, 26]. It is thus crucial to identify conditions ensuring decidability, and possibly tractability, of query answering.

Acknowledgments

Scafoglieri’s research was entirely and exclusively supported by PNRR MUR project PE0000013FAIR. Lembo’s research was supported by EU ICT-48 2020 project TAILOR (No. 952215), EU ERA-NET Cofund ICT-AGRI-FOOD project ADCATER (No. 40705), PNRR MUR project PE0000013-FAIR and the MUR PRIN 2022LA8XBH project Polar (POLicy specificAtion and enfoRcement for privacy-enhanced data management). logics, in: W. Faber, A. Paschke (Eds.), Reasoning Web. Semantic Technologies for Intelligent Data Access – 11th Int. Summer School Tutorial Lectures (RW), volume 9203, 2015, pp. 218–307. [19] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Ontology-based data access and integration, in: L. Liu, M. T. Özsu (Eds.), Encyclopedia of Database Systems, Second Edition, Springer, 2018. [20] D. Lembo, Y. Li, L. Popa, K. Qian, F. Scafoglieri, Ontology mediated information extraction with MASTRO SYSTEM-T, in: Proceedings of the ISWC 2020 Demos and Industry Tracks, volume 2721 of CEUR Electronic Workshop Proceedings, http://ceur-ws.org/, CEUR-WS.org, 2020, pp. 256–261. [21] D. Lembo, F. M. Scafoglieri, Ontology-based document spanning systems for information extraction, Int. J. Semantic Comput. 14 (2020) 3–26. URL: https://doi.org/10.1142/ S1793351X20400012. doi:10.1142/S1793351X20400012. [22] R. Fagin, B. Kimelfeld, F. Reiss, S. Vansummeren, Document spanners: A formal approach to information extraction, Journal of the ACM (JACM) 62 (2015) 1–51. [23] V. Christophides, V. Efthymiou, T. Palpanas, G. Papadakis, K. Stefanidis, An overview of end-to-end entity resolution for big data, ACM Computing Surveys (CSUR) 53 (2020) 1–42. [24] C. Lutz, D. Toman, F. Wolter, Conjunctive query answering in the description logic ℰ ℒ using a relational database system, in: Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI), 2009, pp. 2070–2075. [25] C. Beeri, M. Y. Vardi, The implication problem for data dependencies, in: Proc. of the 8th Coll. on Automata, Languages and Programming (ICALP), volume 115 of Lecture Notes in Computer Science, Springer, 1981, pp. 73–85. [26] A. Calì, D. Lembo, R. Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, in: Proc. of the 22nd ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 2003, pp. 260–271.

References

[1] O. Benjelloun , H. Garcia-Molina , D. Menestrina , Q. Su , S. E. Whang , J. Widom , Swoosh: a generic approach to entity resolution , Very Large Database J . 18 ( 2009 ) 255 - 276 .

[2] G. Papadakis , E. Ioannou , E. Thanos, T. Palpanas, The Four Generations of Entity Resolution, Synthesis Lectures on Data Management , Morgan & Claypool Publishers, 2021 .

[3] R. Fagin , P. G. Kolaitis , D. Lembo , L. Popa , F. Scafoglieri , A Framework for Combining Entity Resolution and Query Answering in Knowledge Bases , in: Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning , 2023 , pp. 229 - 239 .

[4] C. Beeri , M. Y. Vardi , A proof procedure for data dependencies , J. of the ACM 31 ( 1984 ) 718 - 741 .

[5] R. Fagin , P. G. Kolaitis , R. J. Miller , L. Popa , Data exchange: Semantics and query answering , Theoretical Computer Science 336 ( 2005 ) 89 - 124 .

[6] J. Baget , M. Leclère , M. Mugnier , E. Salvat, On rules with existential variables: Walking the decidability line , Artificial Intelligence 175 ( 2011 ) 1620 - 1654 .

[7] M. Krötzsch , M. Marx , S. Rudolph, The power of the terminating chase (invited talk) , in: Proc. of the 22nd Int. Conf. on Database Theory (ICDT) , volume 127 of LIPIcs, 2019 , pp. 3 : 1 - 3 : 17 .

[8] F. Baader , D. Calvanese , D. McGuinness , D. Nardi , P. F. Patel-Schneider (Eds.), The Description Logic Handbook: Theory, Implementation and Applications , 2nd ed., Cambridge University Press, 2007 .

[9] A. Calì , G. Gottlob, T. Lukasiewicz , A general datalog-based framework for tractable query answering over ontologies , J. of Web Semantics 14 ( 2012 ) 57 - 83 .

[10] M. Bienvenu , G. Cima , V. Gutieérrez-Basulto, LACE: A logical approach to collective entity resolution , in: Proc. of the 41st ACM SIGACT SIGMOD SIGAI Symp. on Principles of Database Systems (PODS) , 2022 , pp. 379 - 391 .

[11] L. E. Bertossi , S. Kolahi , L. V. S. Lakshmanan , Data cleaning and query answering with matching dependencies and matching functions , Theoretical Computer Science 52 ( 2013 ) 441 - 482 .

[12] W. Fan , Dependencies revisited for improving data quality , in: Proc. of the 27th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS) , 2008 , pp. 159 - 170 .

[13] K. Devlin , Sets, functions, and logic: an introduction to abstract mathematics, Chapman and Hall/CRC, 2018 .

[14] A. Calì , G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints , J. of Artificial Intelligence Research 48 ( 2013 ) 115 - 174 .

[15] D. Calvanese , G. De Giacomo, D. Lembo , M. Lenzerini , R. Rosati , Tractable reasoning and efcfiient query answering in description logics: The DL-Lite family , J. of Automated Reasoning 39 ( 2007 ) 385 - 429 .

[16] D. S. Johnson , A. C. Klug , Testing containment of conjunctive queries under functional and inclusion dependencies , J. of Computer and System Sciences 28 ( 1984 ) 167 - 189 .

[17] A. Doan , A. Y. Halevy , Z. G. Ives , Principles of Data Integration, Morgan Kaufmann, 2012 .

[18] M. Bienvenu , M. Ortiz , Ontology-mediated query answering with data-tractable description