Proceedings

Bidirectional Constraints for Exchanging Data: Beyond Monotone Queries

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2698-2704.

© 2015 International Joint Conferences on Artificial Intelligence

Abstract

In this paper, we propose to use the language of bidirectional constraints to specify schema mappings in the context of data exchange. These constraints impose restrictions over both the source and the target data, and have the potential to minimize the ambiguity in the description of the target data to be materialized. We start by making a case for the usefulness of bidirectional constraints to give a meaningful closed-world semantics for st-tgds, which is motivated by Clark's predicate completion and Reiter's formalization of the closed-world assumption of a logical theory. We then formally study the use of bidirectional constraints in data exchange. In particular, we pinpoint the complexity of the existence-of-solutions and the query evaluation problems in several different scenarios, including in the latter case both monotone and non-monotone queries.

  1. [Abiteboul and Duschka, 1998] Serge Abiteboul and Oliver M. Duschka. Complexity of answering queries using materialized views. In PODS, pages 254-263, 1998.
  2. [Afrati and Kolaitis, 2008] Foto N. Afrati and Phokion G. Kolaitis. Answering aggregate queries in data exchange. In PODS, pages 129-138, 2008.
  3. [Arenas et al., 2004] Marcelo Arenas, Pablo Barceló, Ronald Fagin, and Leonid Libkin. Locally consistent transformations and query answering in data exchange. In PODS, pages 229-240, 2004.
  4. [Arenas et al., 2014a] Marcelo Arenas, Pablo Barceló, Leonid Libkin, and Filip Murlak. Foundations of Data Exchange. Cambridge University Press, 2014.
  5. [Arenas et al., 2014b] Marcelo Arenas, Gabriel Diéguez, and Jorge Pérez. Expressiveness and complexity of bidi- rectional constraints for data exchange. In Alberto Mendel- zon Workshop, 2014.
  6. [Arocena et al., 2010] Patricia C. Arocena, Ariel Fuxman, and Renée J. Miller. Composing local-as-view mappings: closure and applications. In ICDT, pages 209-218, 2010.
  7. [Bernstein et al., 2006] Philip A. Bernstein, Todd J. Green, Sergey Melnik, and Alan Nash. Implementing mapping composition. In VLDB, pages 55-66, 2006.
  8. [Clark, 1977] Keith L. Clark. Negation as failure. In Logic and Data Bases, pages 293-322, 1977.
  9. [Evans, 1951] T. Evans. The word problem for abstract alge- bras. Journal of the London Mathematical Society, 26:64- 71, 1951.
  10. [Evans, 1953] T. Evans. Embeddability and the word prob- lem. Journal of the London Mathematical Society, 28:76- 80, 1953.
  11. [Evans, 1978] T. Evans. Word problems. Bulletin of the American Mathematical Society, 84(5):789-802, 1978.
  12. [Fagin et al., 2003] Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: Se- mantics and query answering. In ICDT, pages 207-224, 2003.
  13. [Fagin et al., 2005a] Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: seman- tics and query answering. Theor. Comput. Sci., 336(1):89- 124, 2005.
  14. [Fagin et al., 2005b] Ronald Fagin, Phokion G. Kolaitis, and Lucian Popa. Data exchange: getting to the core. TODS, 30(1):174-210, 2005.
  15. [Fuxman et al., 2006] Ariel Fuxman, Phokion G. Kolaitis, Renée J. Miller, and Wang Chiew Tan. Peer data exchange. TODS, 31(4):1454-1498, 2006.
  16. [Gottlob and Papadimitriou, 2003] Georg Gottlob and Chris- tos H. Papadimitriou. On the complexity of single-rule datalog queries. Inf. Comput., 183(1):104-122, 2003.
  17. [Gottlob et al., 2011] Georg Gottlob, Reinhard Pichler, and Vadim Savenkov. Normalization and optimization of schema mappings. VLDB J., 20(2):277-302, 2011.
  18. [Gurevich, 1966] Yuri Gurevich. The word problem for cer- tain classes of semigroups. Algebra and Logic, 5:25-35, 1966.
  19. [Haas et al., 2005] Laura M. Haas, Mauricio A. Hernández, Howard Ho, Lucian Popa, and Mary Roth. Clio grows up: from research prototype to industrial tool. In SIGMOD Conference, pages 805-810, 2005.
  20. [Halevy, 2000] Alon Y. Halevy. Theory of answering queries using views. SIGMOD Record, 29(4):40-47, 2000.
  21. [Halevy, 2001] Alon Y. Halevy. Answering queries using views: A survey. VLDB J., 10(4):270-294, 2001.
  22. [Hernich et al., 2011] André Hernich, Leonid Libkin, and Nicole Schweikardt. Closed world data exchange. TODS, 36(2):14, 2011.
  23. [Hernich, 2012] André Hernich. Computing universal mod- els under guarded tgds. In ICDT, pages 222-235, 2012.
  24. [Hernich, 2013] André Hernich. Semantics for non- monotone queries in data exchange and data integration. In Data Exchange, Information, and Streams, volume 5 of Dagstuhl Follow-Ups, pages 161-184.
  25. [Kolaitis et al., 2006] Phokion G. Kolaitis, Jonathan Pant- taja, and Wang Chiew Tan. The complexity of data ex- change. In PODS, pages 30-39, 2006.
  26. [Lenzerini, 2002] Maurizio Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233-246, 2002.
  27. [Levy et al., 1995] Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering queries using views. In PODS, pages 95-104, 1995.
  28. [Libkin and Sirangelo, 2011] Leonid Libkin and Cristina Sirangelo. Data exchange and schema mappings in open and closed worlds. J. Comput. Syst. Sci., 77(3):542-571, 2011.
  29. [Libkin, 2006] Leonid Libkin. Data exchange and incom- plete information. In PODS, pages 60-69, 2006.
  30. [Maier et al., 1979] David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. Testing implications of data depen- dencies. TODS, 4(4):455-469, 1979.
  31. [Melnik et al., 2008] Sergey Melnik, Atul Adya, and Philip A. Bernstein. Compiling mappings to bridge applications and databases. TODS, 33(4), 2008.
  32. [Papadimitriou, 1994] Christos H. Papadimitriou. Computa- tional complexity. Addison-Wesley, 1994.
  33. [Reiter, 1977] Raymond Reiter. On closed world data bases. In Logic and Data Bases, pages 55-76, 1977.
  34. [Stockmeyer, 1976] Larry J. Stockmeyer. The polynomial- time hierarchy. Theor. Comput. Sci., 3(1):1-22, 1976.
  35. [Vardi, 1982] Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In STOC, pages 137- 146, 1982.
  36. [Wrathall, 1976] Celia Wrathall. Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci., 3(1):23- 33, 1976.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards