A relational algebra for data/metadata integration in a federated database system

ABSTRACT

The need for interoperability among databases has increased dramatically with the proliferation of readily available DBMS and application software. Even within a single organization, data from disparate relational databases must be integrated. A framework for interoperability in a federated system of relational databases should be inherently relational, so that it can use existing techniques for query evaluation and optimization where possible and retain the key features of SQL, such as a modest complexity and ease of query formulation. Our contribution is a logspace relational algebra, the Meta-Algebra (MA), for data/metadata integration among relational databases containing semantically similar information in schematically disparate formats. The MA is a simple yet powerful extension of the classical relational algebra (RA). The MA has a natural declarative counterpart, the Meta-Query Language (MQL), which we briefly describe. We state a result showing MQL and the MA are computationally equivalent, which enables us to algebratize MQL queries in fundamentally the same way as ordinary SQL queries. This algebratization in turn enables us to use MA equivalences to facilitate the application of known query optimization techniques to MQL query evaluation.

REFERENCES

• 1: Alanoly J. Andrews , Nematollaah Shiri , Laks V. S. Lakshmanan , Iyer N. Subramanian, On implementing SchemaLog—a database programming language, Proceedings of the fifth international conference on Information and knowledge management, p.309-316, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238565]
• 2: P. A. Bemsten, A. Y. Levy, and R. A. Pottinger. A vision for management of complex models. Technical Report MSR-TR-2000-53, Microsoft Research, 2000.
• 3: S. Busse, R.-D. Kutsche, U. Leser, and H. Weber. Federated information systems: Concepts, terminology and architectures. Technical Report 99-9, Technische Universitat Berlin, 1999.
• 4: W. Chen, M. Kifer, and D. S. Warren. HiLog: A foundation for higher-order logic programming. Technical report, Computer Science Department, SUNY at Stony Brook, 1990.
• 5: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 6: Frédéric Gingras , Laks V. S. Lakshmanan, nD-SQL: A Multi-Dimensional Language for Interoperability and OLAP, Proceedings of the 24rd International Conference on Very Large Data Bases, p.134-145, August 24-27, 1998
• 7: Frédéric Gingras , Laks V. S. Lakshmanan , Iyer N. Subramanian , Despina Papoulis , Nematollaah Shiri, Languages for multi-database interoperability, ACM SIGMOD Record, v.26 n.2, p.536-538, June 1997
• 8: John Grant , Witold Litwin , Nick Roussopoulos , Timos Sellis, Query languages for relational multidatabases, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.2, April 1993
• 9: Marc Gyssens , Laks V. S. Lakshmanan , Iyer N. Subramanian, Tables as a paradigm for querying and restructuring (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.93-103, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237688]
• 10: Theo Härder , Günter Sauter , Joachim Thomas, The intrinsic problems of structural heterogeneity and an approach to their solution, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.25-43, April 1999 [doi>10.1007/s007780050072]
• 11: R. Jakobovits. Integrating autonomous heterogeneous information sources. Technical report, Computer Science Department, University of Washington, 1997.
• 12: Ravi Krishnamurthy , Witold Litwin , William Kent, Language features for interoperability of databases with schematic discrepancies, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.40-49, May 29-31, 1991, Denver, Colorado, United States
• 13: L. V. Lakshmanan, F. Sadri, and I. N. Subramanian. On the logical foundations of schema integration and evolution in heterogeneous database systems. In DOOD '93, 1993.
• 14: Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian, SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.239-250, September 03-06, 1996
• 15: L. V Lakshmanan, F. Sadri, and I. N. Subramanian. Logic and algebraic languages for interoperability in multidatabase systems. Journal ofLogic Programming, 32(2):101-149, 1997.
• 16: L. V Lakshmanan, F. Sadri, and S. N. Subramanian. SchemaSQL: An extension to SQL for multi-database interoperability. http: //www. uncg. edu/~sadrif
• 17: Laks V. S. Lakshmanan , Fereidoon Sadri , Subbu N. Subramanian, On Efficiently Implementing SchemaSQL on an SQL Database System, Proceedings of the 25th International Conference on Very Large Data Bases, p.471-482, September 07-10, 1999
• 18: Sharad Mehrotra , Henry F. Korth , Avi Silberschatz, An Architecture for Large Multidatabase Systems, University of Texas at Austin, Austin, TX, 1993
• 19: S. B. Navathe and M. J. Donahoo. Towards intelligent integration of heterogeneous information sources. In Proceedings of the 6th International Hong Kong Computer Society Database Workshop, 1995.
• 20: C. M. Rood, D. Van Gucht, and F. I. Wyss. MD-SQL: A language for meta-data queries over relational databases. Technical Report TR-528, Computer Science Department, Indiana University, 1999.
• 21: Kenneth A. Ross, Relations with relation names as arguments: algebra and calculus, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.346-353, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137905]
• 22: F. Sadri and S. B. Wilson. Implementation of SchemaSQL -a language for relational multi-database systems. Technical report, Department of Mathematical Sciences, University of North Carolina at Greensboro, 1997.
• 23: Amit P. Sheth , Vipul Kashyap, So Far (Schematically) yet So Near (Semantically), Proceedings of the IFIP WG 2.6 Database Semantics Conference on Interoperable Database Systems (DS-5), p.283-312, November 16-20, 1992
• 24: M. Tresch and M. H. Scholl. A classification of multi-database languages. Technical Report 94-07, University of Ulm Faculty of Computer Science, 1994.
• 25: Mark W. W. Vermeer , Peter M. G. Apers, On the Applicability of Schema Integration Techniques to Database Interoperation, Proceedings of the 15th International Conference on Conceptual Modeling, p.179-194, October 07-10, 1996
• 26: Jennifer Widom, Research problems in data warehousing, Proceedings of the fourth international conference on Information and knowledge management, p.25-30, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221319]
• 27: C. Wyss, F. Wyss, and D. Van Gucht. Augmenting SQL with dynamic typing to support interoperability in a relational federation. In Proceedings of the 4th International Conference on Engineering Federated Information Systems (EFIS 2001), 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema; Data models
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Distributed databases; Relational databases; Query processing
      H.2.5 Heterogeneous Databases

General Terms:
Languages

Keywords:
database integration, database schema integration, federated data-base systems, federated information system (FIS), interoperability, metadata, metaquery, multidatabase, query languages, relation-al algebra, schema transparency