Schema mappings, data exchange, and metadata management

ABSTRACT

Schema mappings are high-level specifications that describe the relationship between database schemas. Schema mappings are prominent in several different areas of database management, including database design, information integration, data exchange, metadata management, and peer-to-peer data management systems. Our main aim in this paper is to present an overview of recent advances in data exchange and metadata management, where the schema mappings are between relational schemas. In addition, we highlight some research issues and directions for future work.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: Krzysztof R. Apt, Logic programming, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 3: Marcelo Arenas , Leonid Libkin, XML data exchange: consistency and query answering, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065171]
• 4: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 5: C. Beeri and M. Y. Vardi. Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. on Computing, 13(1):76--98, 1984.
• 6: P. A. Bernstein. Applying Model Management to Classical Meta-Data Problems. In Conference on Innovative Data Systems Research (CIDR), pages 209--220, 2003.
• 7: P. A. Bernstein. Generic Model Management: A Database Infrastructure for Schema Manipulation. Keynote Address, IDM 2003 Workshop, Seattle, Washington, September 2003.
• 8: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 9: E. F. Codd. Further normalization of the data base relational model. In R. Rustin, editor, Data Base Systems, pages 33--64. Prentice-Hall, 1972.
• 10: S. S. Cosmadakis and P. C. Kanellakis. Functional and Inclusion Dependencies: A Graph Theoretic Approach. In Advances in Computing Research, volume 3, pages 163--184. JAI Press, 1986.
• 11: Anuj Dawar, A restricted second order logic for finite structures, Information and Computation, v.143 n.2, p.154-174, June 15, 1998 [doi>10.1006/inco.1998.2703]
• 12: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 13: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 14: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773163]
• 15: Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055572]
• 16: Tomás Feder , Moshe Y. Vardi, Monotone monadic SNP and constraint satisfaction, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.612-622, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167245]
• 17: Ariel Fuxman , Phokion G. Kolaitis , Renée J. Miller , Wang-Chiew Tan, Peer data exchange, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065188]
• 18: Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065187]
• 19: Laura M. Haas , Mauricio A. Hernández , Howard Ho , Lucian Popa , Mary Roth, Clio grows up: from research prototype to industrial tool, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066252]
• 20: Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
• 21: P. Hell and J. Nešetřil. Graphs and Homomorphisms. Oxford University Press, 2004.
• 22: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 23: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 24: T. Luczak and J. Nešetřil. A probabilistic approach to the dychotomy problem. Technical Report 640, Charles University, Prague, 2003.
• 25: J. Madhavan and A. Y. Halevy. Composing Mappings Among Data Sources. In International Conference on Very Large Data Bases (VLDB), pages 572--583, 2003.
• 26: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 27: Aleksander Madry, Data exchange: on the complexity of answering queries with inequalities, Information Processing Letters, v.94 n.6, p.253-257, 30 June 2005 [doi>10.1016/j.ipl.2005.03.001]
• 28: Sergey Melnik, Generic Model Management: Concepts And Algorithms (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 29: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 30: Alan Nash , Philip A. Bernstein , Sergey Melnik, Composition of mappings given by embedded dependencies, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065189]
• 31: C. H. Papadimitriou , M. Yannakakis, The complexity of facets (and some facets of complexity), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.255-260, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802199]
• 32: C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 33: L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating Web Data. In International Conference on Very Large Data Bases (VLDB), pages 598--609, 2002.
• 34: N. C. Shu , B. C. Housel , R. W. Taylor , S. P. Ghosh , V. Y. Lum, EXPRESS: a data EXtraction, Processing, and Restructuring System, ACM Transactions on Database Systems (TODS), v.2 n.2, p.134-174, June 1977 [doi>10.1145/320544.320549]
• 35: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 36: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]