Extending relational query optimization to dynamic schemas for information integration in multidatabases

ABSTRACT

This paper extends relational processing and optimization to the FISQL/FIRA languages for dynamic schema queries over multidatabases. Dynamic schema queries involve the creation and restructuring of metadata at runtime. We present a full implementation of a FISQL/FIRA engine, which includes subqueries and all transformational capabilities of FISQL/FIRA on distributed, multidatabase platforms. An important application of the system is to enhance traditional information architectures by enabling the creation and maintenance of dynamic wrappers and mapping queries at source databases within GAV, LAV, GLAV, peer-to-peer, or other integration frameworks. In addition to fully supporting FISQL/FIRA on multidatabases, our implementation introduces a bi-level optimization paradigm where purely relational sub-fragments of queries are pushed into source engines. This paradigm shares features of canonical distributed database processing, but has a new dimension through the extension of the relational model to dynamic schemas. We present empirical results showing the feasibility of optimization in this context, and discuss tradeoffs involved. Our system is the first to extend relational databases with these capabilities on this scale.

REFERENCES

• 1: Francois Barbancon and Daniel P. Miranker. Implementing Federated Database Systems by Compiling Schema SQL. IDEAS 2002.
• 2: Conor Cunningham, C&3233;sar A. Galindo-Legaria, and Goetz Graefe. PIVOT and UNPIVOT: Optimization and Execution Strategies in an RDBMS. VLDB 2004.
• 3: Keir B. Davis and Fereidoon Sadri. Optimization of Schema SQL Queries. IDEAS 2001.
• 4: R. Dhamanka, Y. Lee, A. Doan, A. Halevy, and P. Domingos. iMAP: Discovering Complex Semantic Matches Between Database Schema. SIGMOD 2004.
• 5: George H. L. Fletcher and Catharine M. Wyss. Data Mapping as Search. EDBT 2006.
• 6: Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey Ullman , Vasilis Vassalos , Jennifer Widom, The TSIMMIS Approach to Mediation: Data Models and Languages, Journal of Intelligent Information Systems, v.8 n.2, p.117-132, March/April 1997 [doi>10.1023/A:1008683107812 ]
• 7: John Grant, Witold Litwin, Nick Roussopoulos, and Timos Sellis. Query Languages for Relational Multidatabases. VLDB Journal, vol2. pp 153--171, 1993.
• 8: 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]
• 9: Laura Haas, Renee Miller, Bartholomew Niswonger, Mary Tork Roth, Peter Schwarz, and Edward Wimmers. Transforming Heterogeneous Data with Database Middleware: Beyond Integration. IEEE Bulletin of the Technical Committee on Data Engineering, March 1999. Vol. 22, no. 1, pp 31--36.
• 10: Qi He and Tok Wang Ling. Extending and Inferring Functional Dependencies in Schema Transformation. CIKM 2005.
• 11: L. V. S. Lakshmanan, F. Sadri, and S. N. Subramanian. On Efficiently Implementing SchemaSQL on an SQL Database System. VLDB 1999.
• 12: 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]
• 13: 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]
• 14: Lin Liu. SIGMOD Record: Special Issue on Semantic Integration. 33:4, December 2004.
• 15: Witold Litwin , M. Ketabchi , Ravi Krishnamurthy, First order normal form for relational databases and multidatabases, ACM SIGMOD Record, v.20 n.4, p.74-76, Dec. 1991 [doi>10.1145/141356.141389]
• 16: Peter McBrien and Alexandra Poulovassilis. Data Integration by Bi-Directional Schema Transformation Rules. ICDE 2003.
• 17: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 18: Amit P. Sheth , James A. Larson, Federated database systems for managing distributed, heterogeneous, and autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.183-236, Sept. 1990 [doi>10.1145/96602.96604]
• 19: M. T. Ozsu and P. Valduriez. Principles of Distributed Database Systems, 2nd ed. Prentice Hall, 1999.
• 20: Catharine M. Wyss , Edward L. Robertson, Relational languages for metadata integration, ACM Transactions on Database Systems (TODS), v.30 n.2, p.624-660, June 2005 [doi>10.1145/1071610.1071618]
• 21: Catharine M. Wyss , Edward L. Robertson, A formal characterization of PIVOT/UNPIVOT, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099709]
• 22: http://www.microsoft.com/net, http://www.microsoft.com/vcsharp
• 23: http://www.antlr.org
• 24: http://www.microsoft.com/sql

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Languages

Keywords:
FIRA, FISQL, data integration, dynamic schema query processing, federated data model, federated databases, federated interoperable RA, federated interoperable SQL, metadata integration, metadata query processing