Document Open Access Logo

On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds

Authors Henrik Forssell, Evgeny Kharlamov, Evgenij Thorstensen

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2020.10.pdf
  • Filesize: 0.6 MB
  • 21 pages

Document Identifiers

Author Details

Henrik Forssell
  • University of Oslo, Norway
  • University of South East Norway, Drammen, Norway
Evgeny Kharlamov
  • Bosch Center for Artificial Intelligence, Renningen, Germany
  • University of Oslo, Norway
Evgenij Thorstensen
  • University of Oslo, Norway

Funding

This work was partially supported by the SIRIUS Centre, Norwegian Research Council project number 237898 and project number 230525.

Cite As Get BibTex

Henrik Forssell, Evgeny Kharlamov, and Evgenij Thorstensen. On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICDT.2020.10

Abstract

Data exchange heavily relies on the notion of incomplete database instances. Several semantics for such instances have been proposed and include open (OWA), closed (CWA), and open-closed (OCWA) world. For all these semantics important questions are: whether one incomplete instance semantically implies another; when two are semantically equivalent; and whether a smaller or smallest semantically equivalent instance exists. For OWA and CWA these questions are fully answered. For several variants of OCWA, however, they remain open. In this work we adress these questions for Closed Powerset semantics and the OCWA semantics of [Leonid Libkin and Cristina Sirangelo, 2011]. We define a new OCWA semantics, called OCWA*, in terms of homomorphic covers that subsumes both semantics, and characterize semantic implication and equivalence in terms of such covers. This characterization yields a guess-and-check algorithm to decide equivalence, and shows that the problem is NP-complete. For the minimization problem we show that for several common notions of minimality there is in general no unique minimal equivalent instance for Closed Powerset semantics, and consequently not for the more expressive OCWA* either. However, for Closed Powerset semantics we show that one can find, for any incomplete database, a unique finite set of its subinstances which are subinstances (up to renaming of nulls) of all instances semantically equivalent to the original incomplete one. We study properties of this set, and extend the analysis to OCWA*.

Subject Classification

ACM Subject Classification
  • Theory of computation → Incomplete, inconsistent, and uncertain databases
  • Theory of computation
Keywords
  • Incomplete Databases
  • Cores
  • Semantics
  • Open and Closed Worlds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  2. Marcelo Arenas, Pablo Barceló, Leonid Libkin, and Filip Murlak. Foundations of Data Exchange. Cambridge University Press, 2014. Google Scholar
  3. Marcelo Arenas, Elena Botoeva, Diego Calvanese, and Vladislav Ryzhikov. Knowledge base exchange: The case of OWL 2 QL. Artif. Intell., 238:11-62, 2016. Google Scholar
  4. Marcelo Arenas and Leonid Libkin. XML data exchange: Consistency and query answering. J. ACM, 55(2):7:1-7:72, 2008. Google Scholar
  5. Philip A. Bernstein and Sergey Melnik. Model management 2.0: manipulating richer mappings. In SIGMOD, pages 1-12, 2007. Google Scholar
  6. Surajit Chaudhuri and Moshe Y. Vardi. Optimization of Real Conjunctive Queries. In PODS, 1993. Google Scholar
  7. Ronald Fagin, Laura M. Haas, Mauricio A. Hernández, Renée J. Miller, Lucian Popa, and Yannis Velegrakis. Clio: Schema Mapping Creation and Data Exchange. In Conceptual Modeling: Foundations and Applications, pages 198-236, 2009. Google Scholar
  8. Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: semantics and query answering. Theor. Comput. Sci., 336(1):89-124, 2005. Google Scholar
  9. Ronald Fagin, Phokion G. Kolaitis, and Lucian Popa. Data exchange: getting to the core. ACM Trans. Database Syst., 30(1):174-210, 2005. Google Scholar
  10. Jan Foniok. Homomorphisms and Structural Properties of Relational Systems. PhD thesis, Charles University in Prague, 2007. Google Scholar
  11. Henrik Forssell, Evgeny Kharlamov, and Evgenij Thorstensen. Towards Characterising Data Exchange Solutions in Open and Closed Words (Extended Abstract). In AMW, 2017. Google Scholar
  12. Amélie Gheerbrant, Leonid Libkin, and Cristina Sirangelo. NaïVe Evaluation of Queries over Incomplete Databases. ACM Trans. Database Syst., 39(4):31:1-31:42, December 2014. Google Scholar
  13. Ladan Golshanara and Jan Chomicki. Temporal data exchange. Inf. Syst., 87, 2020. Google Scholar
  14. Georg Gottlob. On minimal constraint networks. Artif. Intell., 191-192:42-60, 2012. Google Scholar
  15. Gösta Grahne, Ali Moallemi, and Adrian Onet. Recovering Exchanged Data. In PODS, pages 105-116, 2015. Google Scholar
  16. Pavol Hell and Jaroslav Nešetřil. The core of a graph. Discrete Mathematics, 109(1):117-126, 1992. Google Scholar
  17. André Hernich. Answering Non-monotonic Queries in Relational Data Exchange. In ICDT, pages 143-154, 2010. Google Scholar
  18. André Hernich, Leonid Libkin, and Nicole Schweikardt. Closed world data exchange. ACM Trans. Database Syst., 36(2):14:1-14:40, 2011. Google Scholar
  19. Angelika Kimmig, Alex Memory, Renée J. Miller, and Lise Getoor. A Collective, Probabilistic Approach to Schema Mapping Using Diverse Noisy Evidence. IEEE Trans. Knowl. Data Eng., 31(8):1426-1439, 2019. Google Scholar
  20. Kolja Knauer and Torsten Ueckerdt. Three ways to cover a graph. Discrete Mathematics, 339(2):745-758, 2016. Google Scholar
  21. Phokion G. Kolaitis. Schema mappings, data exchange, and metadata management. In PODS, 2005. Google Scholar
  22. Egor V. Kostylev, Juan L. Reutter, and András Z. Salamon. Classification of annotation semirings over containment of conjunctive queries. ACM Trans. Database Syst., 39(1):1, 2014. Google Scholar
  23. Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering Queries Using Views. In PODS, pages 95-104, 1995. Google Scholar
  24. Leonid Libkin and Cristina Sirangelo. Data exchange and schema mappings in open and closed worlds. J. Comput. Syst. Sci., 77(3):542-571, 2011. Google Scholar
  25. Thomas Lukasiewicz, Maria Vanina Martinez, Livia Predoiu, and Gerardo I. Simari. Basic Probabilistic Ontological Data Exchange with Existential Rules. In AAAI, pages 1023-1029, 2016. Google Scholar
  26. Lucian Popa, Yannis Velegrakis, Renée J. Miller, Mauricio A. Hernández, and Ronald Fagin. Translating Web Data. In VLDB, 2002. Google Scholar
  27. Balder ten Cate, Phokion G. Kolaitis, Kun Qian, and Wang-Chiew Tan. Approximation Algorithms for Schema-Mapping Discovery from Data Examples. ACM Trans. Database Syst., 42(2):12:1-12:41, 2017. Google Scholar
  28. Balder ten Cate, Phokion G. Kolaitis, Kun Qian, and Wang-Chiew Tan. Active Learning of GAV Schema Mappings. In PODS, pages 355-368, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact