Bogdan Alexe
ABSTRACT
Schema mappings are high-level specifications that describe the relationship between two database schemas; they are considered to be the essential building blocks in data exchange and data integration, and have been the object of extensive research investigations. Since in real-life applications schema mappings can be quite complex, it is important to develop methods and tools for understanding, explaining, and refining schema mappings. A promising approach to this effect is to use "good" data examples that illustrate the schema mapping at hand.
We develop a foundation for the systematic investigation of data examples and obtain a number of results on both the capabilities and the limitations of data examples in explaining and understanding schema mappings. We focus on schema mappings specified by source-to-target tuple generating dependencies (s-t tgds) and investigate the following problem: which classes of s-t tgds can be "uniquely characterized" by a finite set of data examples? Our investigation begins by considering finite sets of positive and negative examples, which are arguably the most natural choice of data examples. However, we show that they are not powerful enough to yield interesting unique characterizations. We then consider finite sets of universal examples, where a universal example is a pair consisting of a source instance and a universal solution for that source instance. We unveil a tight connection between unique characterizations via universal examples and the existence of Armstrong bases (a relaxation of the classical notion of Armstrong databases). On the positive side, we show that every schema mapping specified by LAV s-t tgds is uniquely characterized by a finite set of universal examples with respect to the class of LAV s-t tgds. Moreover, this positive result extends to the much broader classes of n-modular schema mappings, n a positive integer. Finally, we show that, on the negative side, there are schema mappings specified by GAV s-t tgds that are not uniquely characterized by any finite set of universal examples and negative examples with respect to the class of GAV s-t tgds (hence also with respect to the class of all s-t tgds).
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
Digital Library
- B. Alexe, L. Chiticariu, R. J. Miller, and W. C. Tan. Muse: Mapping Understanding and deSign by Example. In International Conference on Data Engineering (ICDE), pages 10--19, 2008. Google ScholarDigital Library
- B. Alexe, W. C. Tan, and Y. Velegrakis. STBenchmark: Towards a Benchmark for Mapping Systems. Proceedings of the VLDB Endowment (PVLDB), 1(1):230--244, 2008. Google ScholarDigital Library
- W. W. Armstrong. Dependency Structures of Data Base Relationships. In IFIP Congress, pages 580--583, 1974.Google Scholar
- L. Chiticariu and W. C. Tan. Debugging schema mappings with routes. In International Conference on Very Large Data Bases (VLDB), pages 79--90, 2006. Google ScholarDigital Library
- P. Erdös. Graph theory and probability. Canadian J. of Mathematics, 11:34--38, 1959.Google ScholarCross Ref
- R. Fagin. Armstrong Databases. In 7th IBM Symposium on Mathematical Foundations of Computer Science, 1982.Google Scholar
- R. Fagin. Horn Clauses and Database Dependencies. Journal of the Association for Computing Machinery (JACM), 29(4):952--985, Oct. 1982. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. Theoretical Computer Science (TCS), 336(1):89--124, 2005. Google ScholarCross Ref
- R. Fagin, P. G. Kolaitis, A. Nash, and L. Popa. (PODS), 2008. In ACM Symposium on Principles of Database Systems (PODS), pages 33--42, 2008. Google ScholarDigital Library
- R. Fagin and M. Y. Vardi. Armstrong Databases for Functional and Inclusion Dependencies. Inf. Process. Lett., 16(1):13--19, 1983.Google Scholar
- R. Fagin and M. Y. Vardi. The Theory of Data Dependencies - A Survey. In M. Anshel and W. Gewirtz, editors, Proc. of Symposia in Applied Mathematics, volume 34 - Mathematics of Information Processing, pages 19--71. American Mathematical Society, Providence, Rhode Island, 1986.Google ScholarCross Ref
- L. M. Haas, M. A. Hernández, H. Ho, L. Popa, and M. Roth. Clio Grows Up: From Research Prototype to Industrial Tool. In ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 805--810, 2005. Google ScholarDigital Library
- P. Hell and J. Neaetril. Graphs and Homomorphisms. Oxford University Press, 2004.Google ScholarCross Ref
- M. A. Hernández, R. J. Miller, L. Haas, L. Yan, C. T. H. Ho, and X. Tian. Clio: A Semi-Automatic Tool for Schema Mapping, System Demonstration. ACM SIGMOD International Conference on Management of Data (SIGMOD), 30(2), May 2001. Google ScholarDigital Library
- W. Hodges. A Shorter Model Theory. Cambridge University Press, 1997. Google ScholarDigital Library
- M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory. The MIT Press, 1994. Google ScholarDigital Library
- P. G. Kolaitis. Schema Mappings, Data Exchange, and Metadata Management. In ACM Symposium on Principles of Database Systems (PODS), pages 61--75, 2005. Google ScholarDigital Library
- M. Lenzerini. Data Integration: A Theoretical Perspective. In ACM Symposium on Principles of Database Systems (PODS), pages 233--246, 2002. Google ScholarDigital Library
- A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.Google ScholarCross Ref
- J. Neaetril and V. Rödl. Chromatically optimal rigid graphs. J. Comb. Theory, Ser. B, 46(2):133--141, 1989. Google ScholarDigital Library
- C. Olston, S. Chopra, and U. Srivastava. Generating example data for dataflow programs. In ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 245--256, 2009. Google ScholarDigital Library
- P. Senellart and G. Gottlob. On the complexity of deriving schema mappings from database instances. In ACM Symposium on Principles of Database Systems (PODS), pages 23--32, 2008. Google ScholarDigital Library
- B. ten Cate and P. G. Kolaitis. Structural Characterizations of Schema-Mapping Languages. In International Conference on Database Theory (ICDT), pages 63--72, 2009. Google ScholarDigital Library
- B. ten Cate and P. G. Kolaitis and W. C. Tan. Database Constraints and Homomorphism Dualities. Work in Progress, 2010.Google Scholar
- L.-L. Yan, R. J. Miller, L. M. Haas, and R. Fagin. Data-Driven Understanding and Refinement of Schema Mappings. In ACM SIGMOD International Conference on Management of Data (SIGMOD), pages 485--496, 2001. Google ScholarDigital Library
Index Terms
- Characterizing schema mappings via data examples
Recommendations
Characterizing schema mappings via data examples
Schema mappings are high-level specifications that describe the relationship between two database schemas; they are considered to be the essential building blocks in data exchange and data integration, and have been the object of extensive research ...
Reflections on Schema Mappings, Data Exchange, and Metadata Management
PODS '18: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsA schema mapping is a high-level specification of the relationship between two database schemas. For the past fifteen years, schema mappings have played an essential role in the modeling and analysis of data exchange, data integration, and related data ...
Designing and refining schema mappings via data examples
SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of dataA schema mapping is a specification of the relationship between a source schema and a target schema. Schema mappings are fundamental building blocks in data integration and data exchange and, as such, obtaining the right schema mapping constitutes a ...
Comments