×

zbMATH — the first resource for mathematics

Expressive power of entity-linking frameworks. (English) Zbl 1421.68036
Summary: We develop a unifying approach to declarative entity linking by introducing the notion of an entity-linking framework and an accompanying notion of the certain links in such a framework. In an entity-linking framework, logic-based constraints are used to express properties of the desired link relations in terms of source relations and, possibly, in terms of other link relations. The definition of the certain links in such a framework makes use of weighted repairs and consistent answers in inconsistent databases. We demonstrate the modeling capabilities of this approach by showing that numerous concrete entity-linking scenarios can be cast as such entity-linking frameworks for suitable choices of constraints and weights. By using the certain links as a measure of expressive power, we investigate the relative expressive power of several entity-linking frameworks and obtain sharp comparisons.
MSC:
68P15 Database theory
Software:
ERBlox
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arasu, Arvind; Re, Christopher; Suciu, Dan, Large-scale deduplication with constraints using Dedupalog, (ICDE, (2009)), 952-963
[2] Arenas, Marcelo; Bertossi, Leopoldo E.; Chomicki, Jan, Consistent query answers in inconsistent databases, (PODS, (1999)), 68-79
[3] Bach, Stephen H., Hinge-Loss Markov Random Fields and Probabilistic Soft Logic: A Scalable Approach to Structured Prediction, (2015), University of Maryland, PhD thesis
[4] Bach, Stephen H.; Broecheler, Matthias; Huang, Bert; Getoor, Lise, Hinge-loss Markov random fields and probabilistic soft logic, (2015), CoRR · Zbl 1435.68252
[5] Bahmani, Zeinab; Bertossi, Leopoldo E.; Vasiloglou, Nikolaos, ERBlox: combining matching dependencies with machine learning for entity resolution, Int. J. Approx. Reason., 83, 118-141, (2017) · Zbl 1404.68093
[6] Bertossi, Leopoldo E.; Kolahi, Solmaz; Lakshmanan, Laks V. S., Data cleaning and query answering with matching dependencies and matching functions, Theory Comput. Syst., 52, 3, 441-482, (2013) · Zbl 1270.68102
[7] Bhattacharya, Indrajit; Getoor, Lise, Collective entity resolution in relational data, ACM Trans. Knowl. Discov. Data, 1, 1, (2007) · Zbl 1161.68756
[8] Bröcheler, Matthias; Mihalkova, Lilyana; Getoor, Lise, Probabilistic similarity logic, (UAI 2010, Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, July 8-11, 2010, (2010)), 73-82
[9] Burdick, Douglas; Fagin, Ronald; Kolaitis, Phokion G.; Popa, Lucian; Tan, Wang-Chiew, A declarative framework for linking entities, ACM Trans. Database Syst., 41, 3, 17, (2016), Preliminary version appeared in ICDT, 2015, pp. 25-43 · Zbl 1365.68198
[10] Burdick, Douglas; Fagin, Ronald; Kolaitis, Phokion G.; Popa, Lucian; Tan, Wang Chiew, Expressive power of entity-linking frameworks, (20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, (2017)) · Zbl 1402.68043
[11] Chomicki, Jan; Marcinkowski, Jerzy, Minimal-change integrity maintenance using tuple deletions, Inf. Comput., 197, 1-2, 90-121, (2005) · Zbl 1075.68022
[12] Dong, Xin; Halevy, Alon Y.; Madhavan, Jayant, Reference reconciliation in complex information spaces, (SIGMOD, (2005)), 85-96
[13] Du, Jianfeng; Qi, Guilin; Shen, Yi-Dong, Weight-based consistent query answering over inconsistent SHIQ knowledge bases, Knowl. Inf. Syst., 34, 2, 335-371, (2013)
[14] Elmagarmid, Ahmed K.; Ipeirotis, Panagiotis G.; Verykios, Vassilios S., Duplicate record detection: a survey, IEEE Trans. Knowl. Data Eng., 19, 1, 1-16, (2007)
[15] Fan, Wenfei, Dependencies revisited for improving data quality, (PODS, (2008)), 159-170
[16] Fellegi, Ivan P.; Sunter, Alan B., A theory for record linkage, J. Am. Stat. Assoc., 64, 328, 1183-1210, (1969)
[17] Gaifman, Haim, On local and non-local properties, (Proc. Herbrand Symp. - Logic Colloquium ’81, (1982)) · Zbl 0518.03008
[18] Galhardas, Helena; Florescu, Daniela; Shasha, Dennis; Simon, Eric; Saita, Cristian-Augustin, Declarative data cleaning: language, model, and algorithms, (VLDB, (2001)), 371-380
[19] Hernández, Mauricio A.; Koutrika, Georgia; Krishnamurthy, Rajasekar; Popa, Lucian; Wisnesky, Ryan, HIL: a high-level scripting language for entity integration, (EDBT, (2013)), 549-560
[20] Hernández, Mauricio A.; Stolfo, Salvatore J., The merge/purge problem for large databases, (SIGMOD, (1995)), 127-138
[21] Köpcke, Hanna; Rahm, Erhard, Frameworks for entity matching: a comparison, Data Knowl. Eng., 69, 2, 197-210, (2010)
[22] Köpcke, Hanna; Thor, Andreas; Rahm, Erhard, Evaluation of entity resolution approaches on real-world match problems, Proc. VLDB Endow., 3, 1, 484-493, (2010)
[23] Koudas, Nick; Sarawagi, Sunita; Srivastava, Divesh, Record linkage: similarity measures and algorithms, (SIGMOD, (2006)), 802-803
[24] Libkin, Leonid, Logics with counting and local properties, ACM Trans. Comput. Log., 1, 1, 33-59, (2000) · Zbl 1365.03025
[25] Libkin, Leonid, Elements of Finite Model Theory, Texts in Theoretical Computer Science. An EATCS Series, (2004), Springer · Zbl 1060.03002
[26] Lopatenko, Andrei; Bertossi, Leopoldo E., Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics, (ICDT, (2007)), 179-193
[27] Richardson, Matthew; Domingos, Pedro, Markov logic networks, Mach. Learn., 62, 1-2, 107-136, (2006)
[28] Staworko, Slawek; Chomicki, Jan; Marcinkowski, Jerzy, Prioritized repairing and consistent query answering in relational databases, Ann. Math. Artif. Intell., 64, 2-3, 209-246, (2012) · Zbl 1250.68099
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.