A framework for combining entity resolution and query answering in knowledge bases
AUTHORs: 
Ronald Fagin, 
Phokion G. Kolaitis, Domenico Lembo, Lucian Popa, Federico ScafoglieriAuthors Info & Claims
Article No.: 23, Pages 229 - 239
Abstract
We propose a new framework for combining entity resolution and query answering in knowledge bases (KBs) with tuple-generating dependencies (tgds) and equality-generating dependencies (egds) as rules. We define the semantics of the KB in terms of special instances that involve equivalence classes of entities and sets of values. Intuitively, the former collect all entities denoting the same real-world object, while the latter collect all alternative values for an attribute. This approach allows us to both resolve entities and bypass possible inconsistencies in the data. We then design a chase procedure that is tailored to this new framework and has the feature that it never fails; moreover, when the chase procedure terminates, it produces a universal solution, which in turn can be used to obtain the certain answers to conjunctive queries. We finally discuss challenges arising when the chase does not terminate.
References
[1]
Arasu, A.; Ré, C.; and Suciu, D. 2009. Large-scale deduplication with constraints using dedupalog. In Proc. of the 25th IEEE Int. Conf. on Data Engineering (ICDE), 952-963.
[2]
Baader, F.; Calvanese, D.; McGuinness, D.; Nardi, D.; and Patel-Schneider, P. F., eds. 2007. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2nd edition.
[3]
Baget, J.; Leclère, M.; Mugnier, M.; and Salvat, E. 2011. On rules with existential variables: Walking the decidability line. Artificial Intelligence 175(9-10):1620-1654.
[4]
Bahmani, Z.; Bertossi, L. E.; Kolahi, S.; and Lakshmanan, L. V. S. 2012. Declarative entity resolution via matching dependencies and answer set programs. In Brewka, G.; Eiter, T.; and McIlraith, S. A., eds., Proc. of the 13th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), 380-390.
[5]
Beeri, C., and Vardi, M. Y. 1984. A proof procedure for data dependencies. J. of the ACM 31(4):718-741.
[6]
Benjelloun, O.; Garcia-Molina, H.; Menestrina, D.; Su, Q.; Whang, S. E.; and Widom, J. 2009. Swoosh: a generic approach to entity resolution. Very Large Database J. 18(1):255-276.
[7]
Bertossi, L. E.; Kolahi, S.; and Lakshmanan, L. V. S. 2013. Data cleaning and query answering with matching dependencies and matching functions. Theoretical Computer Science 52(3):441-482.
[8]
Bienvenu, M., and Ortiz, M. 2015. Ontology-mediated query answering with data-tractable description logics. In Faber, W., and Paschke, A., eds., Reasoning Web. Semantic Technologies for Intelligent Data Access - 11th Int. Summer School Tutorial Lectures (RW), volume 9203, 218-307.
[9]
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 Proc. of the 20th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR).
[10]
Bienvenu, M.; Cima, G.; and Gutiérrez-Basulto, V. 2022. LACE: A logical approach to collective entity resolution. In
[11]
Proc. of the 41st ACM SIGACT SIGMOD SIGAI Symp. on Principles of Database Systems (PODS), 379-391.
[12]
Burdick, D.; Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W. 2016. A declarative framework for linking entities. ACM Trans. on Database Systems 41(3):17:1-17:38.
[13]
Burdick, D.; Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W. 2019. Expressive power of entity-linking frameworks. J. of Computer and System Sciences 100:44-69.
[14]
Calautti, M., and Pieris, A. 2021. Semi-oblivious chase termination: The sticky case. Theoretical Computer Science 65(1):84-121.
[15]
Calì, A.; Gottlob, G.; and Kifer, M. 2013. Taming the infinite chase: Query answering under expressive relational constraints. J. of Artificial Intelligence Research 48:115-174.
[16]
Calì, A.; Gottlob, G.; and Lukasiewicz, T. 2012. A general datalog-based framework for tractable query answering over ontologies. J. of Web Semantics 14:57-83.
[17]
Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 39(3):385-429.
[18]
Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2018. Ontology-based data access and integration. In Liu, L., and Özsu, M. T., eds., Encyclopedia of Database Systems, Second Edition. Springer.
[19]
Cuenca Grau, B.; Horrocks, I.; Krötzsch, M.; Kupke, C.; Magka, D.; Motik, B.; and Wang, Z. 2013. Acyclicity notions for existential rules and their application to query answering in ontologies. J. of Artificial Intelligence Research 47:741-808.
[20]
Deutsch, A.; Nash, A.; and Remmel, J. B. 2008. The chase revisited. In Proc. of the 27 th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 149-158.
[21]
Doan, A.; Halevy, A. Y.; and Ives, Z. G. 2012. Principles of Data Integration. Morgan Kaufmann.
[22]
Fagin, R.; Kolaitis, P. G.; Miller, R. J.; and Popa, L. 2005. Data exchange: Semantics and query answering. Theoretical Computer Science 336(1):89-124.
[23]
Fan, W. 2008. Dependencies revisited for improving data quality. In Proc. of the 27th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 159-170.
[24]
Grahne, G., and Onet, A. 2018. Anatomy of the chase. Fundamenta Informaticae 157(3):221-270.
[25]
Johnson, D. S., and Klug, A. C. 1984. Testing containment of conjunctive queries under functional and inclusion dependencies. J. of Computer and System Sciences 28(1):167-189.
[26]
Krötzsch, M.; Marx, M.; and Rudolph, S. 2019. The power of the terminating chase (invited talk). In Proc. of the 22nd Int. Conf. on Database Theory (ICDT), volume 127 of LIPIcs, 3:1-3:17.
[27]
Lenzerini, M. 2002. Data integration: A theoretical perspective. In Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 233-246.
[28]
Lutz, C.; Toman, D.; and Wolter, F. 2009. Conjunctive query answering in the description logic EL using a relational database system. In Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI), 2070-2075.
[29]
Marnette, B. 2009. Generalized schema-mappings: from termination to tractability. In Proc. of the 28th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 13-22.
[30]
Papadakis, G.; Ioannou, E.; Thanos, E.; and Palpanas, T. 2021. The Four Generations of Entity Resolution. Synthesis Lectures on Data Management. Morgan & Claypool Publishers.
Recommendations
Query-time entity resolution
Entity resolution is the problem of reconciling database references corresponding to the same real-world entities. Given the abundance of publicly available databases that have unresolved entities, we motivate the problem of query-time entity resolution:...
Handling data quality in entity resolution
IQIS '05: Proceedings of the 2nd international workshop on Information quality in information systemsEntity resolution (ER) is a problem that arises in many information integration scenarios: We have two or more sources containing records on the same set of real-world entities (e.g., customers).However, there are no unique identifiers that tell us what ...
Query-time entity resolution
KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data miningThe goal of entity resolution is to reconcile database references corresponding to the same real-world entities. Given the abundance of publicly available databases where entities are not resolved, we motivate the problem of quickly processing queries ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2023
778 pages
ISBN:978-1-956792-02-7
Copyright © 2023 International Joint Conferences on Artificial Intelligence Organization.
Sponsors
- Principles of Knowledge Representation and Reasoning, Incorporated (KR, Inc.)
- Artificial Intelligence Journal
- National Science Foundation
- Association for Logic Programming
- School of Embedded Composite Artificial Intelligence
Publisher
Unknown publishers
Publication History
Published: 02 September 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024