Structural characterizations of schema-mapping languages

ABSTRACT

Schema mappings are declarative specifications that describe the relationship between two database schemas. In recent years, there has been an extensive study of schema mappings and of their applications to several different data inter-operability tasks, including applications to data exchange and data integration. Schema mappings are expressed in some logical formalism that is typically a fragment of first-order logic or a fragment of second-order logic. These fragments are chosen because they possess certain desirable structural properties, such as existence of universal solutions or closure under target homomorphisms. In this paper, we turn the tables and focus on the following question: can we characterize the various schema-mapping languages in terms of structural properties possessed by the schema mappings specified in these languages? We obtain a number of characterizations of schema mappings specified by source-to-target (s-t) dependencies, including characterizations of schema mappings specified by LAV (local-as-view) s-t tgds, schema mappings specified by full s-t tgds, and schema mappings specified by arbitrary s-t tgds. These results shed light on schema-mapping languages from a new perspective and, more importantly, demarcate the properties of schema mappings that can be used to reason about them in data inter-operability applications.

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: Franz Baader , Jörg H. Siekmann, Unification theory, Handbook of logic in artificial intelligence and logic programming, Oxford University Press, Inc., New York, NY, 1994
• 3: F. Bancilhon. On the completeness of query languages for relational data bases. In MFCS, pages 112--123, 1978.
• 4: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 5: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 6: Ronald Fagin , Phokion G. Kolaitis , Alan Nash , Lucian Popa, Towards a theory of schema-mapping optimization, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376922]
• 7: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Composing schema mappings: Second-order dependencies to the rescue, ACM Transactions on Database Systems (TODS), v.30 n.4, p.994-1055, December 2005 [doi>10.1145/1114244.1114249]
• 8: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Quasi-inverses of schema mappings, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-52, June 2008 [doi>10.1145/1366102.1366108]
• 9: Ariel Fuxman , Mauricio A. Hernandez , Howard Ho , Renee J. Miller , Paolo Papotti , Lucian Popa, Nested mappings: schema mapping reloaded, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 10: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, 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.1065176]
• 11: 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]
• 12: Johann A. Makowsky , Moshe Y. Vardi, On the expressive power of data dependencies, Acta Informatica, v.23 n.3, p.231-244, June 1986 [doi>10.1007/BF00289111]
• 13: J. Paredaens. On the expressive power of the relational algebra. Inf. Process. Lett., 7(2):107--111, 1978.
• 14: Benjamin Rossman, Existential Positive Types and Preservation under Homomorphisisms, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, p.467-476, June 26-29, 2005 [doi>10.1109/LICS.2005.16]
• 15: B. Trakhtenbrot. Impossibility of an algorithm for the decision problem on finite classes. Dokl. Akad. Nauk. SSSR, 70:569--572, 1950.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Languages, Theory

Keywords:
data exchange, data integration, definability, schema mapping