Relational languages for metadata integration

ABSTRACT

In this article, we develop a relational algebra for metadata integration, Federated Interoperable Relational Algebra (FIRA). FIRA has many desirable properties such as compositionality, closure, a deterministic semantics, a modest complexity, support for nested queries, a subalgebra equivalent to canonical Relational Algebra (RA), and robustness under certain classes of schema evolution. Beyond this, FIRA queries are capable of producing fully dynamic output schemas, where the number of relations and/or the number of columns in relations of the output varies dynamically with the input instance. Among existing query languages for relational metadata integration, only FIRA provides generalized dynamic output schemas, where the values in any (fixed) number of input columns can determine output schemas.Further contributions of this article include development of an extended relational model for metadata integration, the Federated Relational Data Model, which is strictly downward compatible with the relational model. Additionally, we define the notion of Transformational Completeness for relational query languages and postulate FIRA as a canonical transformationally complete language. We also give a declarative, SQL-like query language that is equivalent to FIRA, called Federated Interoperable Structured Query Language (FISQL).While our main contributions are conceptual, the federated model, FISQL/FIRA, and the notion of transformational completeness nevertheless have important applications to data integration and OLAP. In addition to summarizing these applications, we illustrate the use of FIRA to optimize FISQL queries using rule-based transformations that directly parallel their canonical relational counterparts. We conclude the article with an extended discussion of related work as well as an indication of current and future work on FISQL/FIRA.

REFERENCES

• 1: Serge Abiteboul , Stéphane Grumbach, COL: a logic-based language for complex objects, Advances in database programming languages, ACM Press, New York, NY, 1990 [doi>10.1145/101620.101641]
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: 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]
• 4: Chaitan Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu, XML-based information mediation with MIX, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.597-599, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: Chawathe, S., Garcia-Molina, H., Hammer, J., Ireland, K., Papakonstantinou, Y., Ullman, J. D., and Widom, J. 1994. The TSIMMIS project: Integration of heterogeneous information sources. In Proceedings of the 16th Meeting of the Information Processing Society of Japan. IPSJ, Tokyo, Japan, 7--18.
• 6: Chen, W., Kifer, M., and Warren, D. S. 1989. HiLog: A first-order semantics for higher-order logic programming constructs. In Logic Programming, Proceedings of the North American Conference 1989, E. L. Lusk and R. A. Overbeek, Eds. (Cleveland, Ohio). MIT Press, Cambridge, Mass., 1090--1114.
• 7: Chen, W., Kifer, M., and Warren, D. S. 1990a. HiLog: A foundation for higher-order logic programming. Tech. Rep., State University of New York at Stony Brook, Stony Brook, N.Y.
• 8: Weidong Chen , Michael Kifer , David S. Warren, HiLog as a platform for database languages, Proceedings of the second international workshop on Database programming languages, p.315-329, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 9: Claypool, K., Jin, J., and Rundensteiner, E. A. 1998. SERF: Schema evolution through an extensible, re-usable and flexible framework. Tech. Rep. WPI-CS-TR-98-9, Worcester Polytechnic Institute.
• 10: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 11: Cunningham, C., Galindo-Legaria, C. A., and Graefe, G. 2004. PIVOT and UNPIVOT: Optimization and execution strategies in an RDBMS. In Proceedings of the 30th International Conference on Very Large DataBases (VLDB 2004) (Toronto, Ont., Canada). Morgan-Kaufmann, San Francisco, Calif., 998--1009.
• 12: Dalkilic, M., Jain, M., Van Gucht, D., and Mendhekar, A. 1996. Design and implementation of reflective SQL. Tech. Rep. TR 451, Indiana University.
• 13: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 14: 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
• 15: Georg Gottlob , Christoph Koch , Robert Baumgartner , Marcus Herzog , Sergio Flesca, The Lixto data extraction project: back and forth between theory and practice, 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.1055560]
• 16: 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
• 17: 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]
• 18: Halevy, A. 2004. Structures, semantics, and statistics. Keynote Address. In Proceedings of the 30th International Conference on Very Large Databases (Toronto, Ont., Canada). 4--6.
• 19: Manoj Kumar Jain , Dirk Van Gucht, Database models and query languages for relational data and metadata query processing, 1996
• 20: Michael Kifer , Georg Lausen, F-logic: a higher-order language for reasoning about objects, inheritance, and scheme, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.134-146, June 1989, Portland, Oregon, United States
• 21: 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
• 22: Ravi Krishnamurthy , Shamim A. Naqvi, Towards a Real Horn Clause Language, Proceedings of the 14th International Conference on Very Large Data Bases, p.252-263, August 29-September 01, 1988
• 23: Lakshmanan, L. V., Sadri, F., and Subramanian, I. N. 1993. On the logical foundations of schema integration and evolution in heterogeneous database systems. In Proceedings of the 3rd International Conference on Deductive and Object-Oriented Databases, S. Ceri, K. Tanaka, and S. Tsur, Eds. (Phoenix, Az.). Springer-Verlag, New York, 81--100.
• 24: Laks V. S. Lakshmanan , Iyer N. Subramanian , Fereidoon Sadri, A Declarative Language for Querying and Restructuring the Web, Proceedings of the 6th International Workshop on Research Issues in Data Engineering (RIDE '96) Interoperability of Nontraditional Database Systems, p.12, February 26-27, 1996
• 25: 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
• 26: Lakshmanan, L. V. S., Sadri, F., and Subramanian, I. N. 1997. Logic and algebraic languages for interoperability in multidatabase systems. J. Logic Prog. 32, 2 (Nov.), 101--149.
• 27: 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
• 28: Laks V. S. Lakshmanan , Fereidoon Sadri , Subbu N. Subramanian, SchemaSQL: An extension to SQL for multidatabase interoperability, ACM Transactions on Database Systems (TODS), v.26 n.4, p.476-519, December 2001 [doi>10.1145/503099.503102]
• 29: 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]
• 30: W. Litwin , A. Abdellatif , A Zeroual , B. Nicolas , Ph. Vigier, MSQL: a multidatabase language, Information Sciences: an International Journal, v.49 n.1-3, p.59-101, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90024-8]
• 31: Ute Masermann , Gottfried Vossen, SISQL: Schema-Independent Database Querying (On and Off the Web), Proceedings of the 2000 International Symposium on Database Engineering & Applications, p.55-64, September 18-20, 2000
• 32: S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989
• 33: Yannis Papakonstantinou , Hector Garcia-Molina , Jeffrey D. Ullman, MedMaker: A Mediation System Based on Declarative Specifications, Proceedings of the Twelfth International Conference on Data Engineering, p.132-141, February 26-March 01, 1996
• 34: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 35: Robertson, E. L. and Wyss, C. M. 2004. Optimal tuple merge is NP-Complete. Tech. Rep. TR599, Indiana University Computer Science. July.
• 36: Rood, C. M., Van Gucht, D., and Wyss, F. I. 1999. MD-SQL: A language for meta-data queries over relational databases. Tech. Rep. TR-528, Indiana University at Bloomington. July.
• 37: 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]
• 38: Fèlix Saltor , Malú Castellanos , Manuel García-Solaco, Overcoming Schematic Discrepancies in Interoperable Databases, Proceedings of the IFIP WG 2.6 Database Semantics Conference on Interoperable Database Systems (DS-5), p.191-205, November 16-20, 1992
• 39: Su, H., Claypool, K., and Rundensteiner, E. A. 2000. Extending the object query language for transparent metadata access. Tech. Rep. WPI-CS-TR-00-19, Worcester Polytechnic Institute.
• 40: Jan Van den Bussche , Dirk Van Gucht , Gottfried Vossen, Reflective programming in the relational algebra, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.17-25, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153852]
• 41: Van den Bussche, J., Vansummeren, S., and Vossen, G. 2004. Meta-SQL: Towards practical meta-querying. In Advances in Database Technology (EDBT 2004): 9th International Conference on Extending Database Technology (Heraklion, Crete, Greece). Springer-Verlag, New York, 823--825.
• 42: Van den Bussche, J. and Waller, E. 2002. Polymorphic type inference for the relational algebra. J. Comput. Syst. Sci. 64, 3, 694--718.
• 43: Catharine Wyss , Dirk Van Gucht, A relational algebra for data/metadata integration in a federated database system, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502597]
• 44: Wyss, C., Wyss, F., and Van Gucht, D. 2001. Augmenting SQL with dynamic restructuring to support interoperability in a relational federation. In Engineering Federated Information Systems, Proceedings of the 4th Workshop (EFIS 2001), R.-D. Kutsche, S. Conrad, and W. Hasselbring, Eds. (Berlin, Germany Oct. 9--10). IOS Press, 5--18.
• 45: Catharine Merle Wyss , Edward L. Robertson, Relational interoperability, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages

Keywords:
Data integration, federated data model, federated databases, interoperability, metadata integration, metadata querying, multidatabases, relational query algebra, schema integration, transformational completeness