SchemaSQL: An extension to SQL for multidatabase interoperability

ABSTRACT

We provide a principled extension of SQL, called SchemaSQL, that offers the capability of uniform manipulation of data and schema in relational multidatabase systems. We develop a precise syntax and semantics of SchemaSQL in a manner that extends traditional SQL syntax and semantics, and demonstrate the following. (1) SchemaSQL retains the flavor of SQL while supporting querying of both data and schema. (2) It can be used to transform data in a database in a structure substantially different from original database, in which data and schema may be interchanged. (3) It also permits the creation of views whose schema is dynamically dependent on the contents of the input instance. (4) While aggregation in SQL is restricted to values occurring in one column at a time, SchemaSQL permits "horizontal" aggregation and even aggregation over more general "blocks" of information. (5) SchemaSQL provides a useful facility for interoperability and data/schema manipulation in relational multidatabase systems. We provide many examples to illustrate our claims. We clearly spell out the formal semantics of SchemaSQL that accounts for all these features. We describe an architecture for the implementation of SchemaSQL and develop implementation algorithms based on available database technology that allows for powerful integration of SQL based relational DBMS. We also discuss the applicability of SchemaSQL for handling semantic heterogeneity arising in a multidatabase system.

REFERENCES

• 1: ACM. 1990. ACM Computing Surveys 22, 3 (Sept.). Special issue on HDBS.
• 2: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• 3: Rakesh Agrawal , Amit Somani , Yirong Xu, Storage and Querying of E-Commerce Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.149-158, September 11-14, 2001
• 4: Rafi Ahmed , Philippe De Smedt , Weimin Du , William Kent , Mohammad A. Ketabchi , Witold A. Litwin , Abbas Rafii , Ming-Chien Shan, The Pegasus Heterogeneous Multidatabase System, Computer, v.24 n.12, p.19-27, December 1991 [doi>10.1109/2.116885]
• 5: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 6: David Beech, Collections of Objects in SQL3, Proceedings of the 19th International Conference on Very Large Data Bases, p.244-255, August 24-27, 1993
• 7: S. Bergamaschi , S. Castano , M. Vincini, Semantic integration of semistructured and structured data sources, ACM SIGMOD Record, v.28 n.1, p.54-59, March 1999 [doi>10.1145/309844.309897]
• 8: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Daniele Nardi , Riccardo Rosati, Information Integration: Conceptual Modeling and Reasoning Support, Proceedings of the 3rd IFCIS International Conference on Cooperative Information Systems, p.280-291, August 20-22, 1998
• 9: Michael J. Carey , Jerry Kiernan , Jayavel Shanmugasundaram , Eugene J. Shekita , Subbu N. Subramanian, XPERANTO: Middleware for Publishing Object-Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.646-648, September 10-14, 2000
• 10: Silvana Castano , Valeria De Antonellis, Semantic Dictionary Design for Database Interoperability, Proceedings of the Thirteenth International Conference on Data Engineering, p.43-54, April 07-11, 1997
• 11: CHOMICKI,J.AND LITWIN, W. 1993. Declarative definition of object-oriented multidatabase mappings. In Distributed Object Management. M. T. Ozsu, U. Dayal, and P. Valduriez, Eds. Morgan- Kaufmann, Los Altos, Calif.
• 12: CODD,E.F.,CODD,S.B.,AND SALLEY, C. T. 1995. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. White paper-URL:http://www.arborsoft.com/papers/ coddTOC.html.
• 13: Keir B. Davis , Fereidoon Sadri, Optimization of SchemaSQL Queries, Proceedings of the International Database Engineering & Applications Symposium, p.111-116, July 16-18, 2001
• 14: Ahmed Elmagarmid , Marek Rusinkiewicz , Amit Sheth, Management of heterogeneous and autonomous database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 15: FLORESCU,D.AND KOSSMANN, D. 1999. Storing and querying XML data using an RDMBS. IEEE Data Eng. Bull. 22, 3, 27-34.
• 16: 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]
• 17: GINGRAS, F. 1997. Extending SchemaSQL towards multidimensional databases and OLAP. Master's dissertation, Dept. Computer Science. Concordia Univ., Montreal, Que., Canada.
• 18: 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
• 19: Frédéric Gingras , Laks V. S. Lakshmanan , Iyer N. Subramanian , Despina Papoulis , Nematollaah Shiri, Languages for multi-database interoperability, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.536-538, May 11-15, 1997, Tucson, Arizona, United States
• 20: 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
• 21: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 22: 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]
• 23: HAMMER,J.AND MCLEOD, D. 1993. An approach to resolving semantic heterogeneity in a federation of autonomous, heterogeneous database systems. Int. J. Intell. Coop. Inf. Syst. 2, 1, 51-83.
• 24: David K. Hsiao, Federated databases and systems: part I --- a tutorial on their data sharing, The VLDB Journal — The International Journal on Very Large Data Bases, v.1 n.1, p.127-180, July 1992 [doi>10.1007/BF01228709]
• 25: IBM. DB2 datajoiner. http://www.software.ibm.com/data/datajoiner.
• 26: William Kelley , Sunit Gala , Won Kim , Tom Reyes , Bruce Graham, Schema architecture of the UniSQL/M multidatabase system, Modern database systems: the object model, interoperability, and beyond, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 27: Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States
• 28: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 29: Won Kim , Injun Choi , Sunit Gala , Mark Scheevel, On resolving schematic heterogeneity in multidatabase systems, Distributed and Parallel Databases, v.1 n.3, p.251-279, July 1993 [doi>10.1007/BF01263333]
• 30: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• 31: 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
• 32: 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
• 33: Ravi Krishnamurthy , Moshé M. Zloof, RBE: Rendering By Example, Proceedings of the Eleventh International Conference on Data Engineering, p.288-297, March 06-10, 1995
• 34: LAKSHMANAN,L.V.S.,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 (DOOD '93) (Dec.). Lecture Notes in Computer Science, Vol. 760. Springer-Verlag, New York, pp. 81-100.
• 35: LAKSHMANAN,L.V.S.,SADRI,F.,AND SUBRAMANIAN, I. N. 1997. Logic and algebraic languages for interoperability in multidatabase systems. J. Logic prog. 33, 2 (Nov.), 101-149.
• 36: 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
• 37: LEFEBVRE, A., BERNUS,P.,AND TOPOR, R. 1992. Query transformation for accessing heterogeneous databases. In Workshop on Deductive Databases in conjunction with JICSLP (Nov.), pp. 31-40.
• 38: Richard J. Lipton , Jeffrey F. Naughton, Query size estimation by adaptive sampling (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.40-46, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298540]
• 39: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 40: 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]
• 41: Witold Litwin , Leo Mark , Nick Roussopoulos, Interoperability of multiple autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.267-293, Sept. 1990 [doi>10.1145/96602.96608]
• 42: Leonardo Meo-Evoli , Fabrizio L. Ricci , Arie Shoshani, On the semantic completeness of macro-data operators for statistical aggregation, Proceedings of the 6th international working conference on Scientific and statistical database management, p.239-258, June 09-12, 1992, Monte Verita, Switzerland
• 43: Reée J. Miller, Using schematically heterogeneous structures, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.189-200, June 01-04, 1998, Seattle, Washington, United States
• 44: Renée J. Miller , Yannis E. Ioannidis , Raghu Ramakrishnan, The Use of Information Capacity in Schema Integration and Translation, Proceedings of the 19th International Conference on Very Large Data Bases, p.120-133, August 24-27, 1993
• 45: Renée J. Miller , Odysseas G. Tsatalos , John H. Williams, DataWeb: Customizable Database Publishing for the Web, IEEE MultiMedia, v.4 n.4, p.14-21, October 1997 [doi>10.1109/93.641875]
• 46: Paolo Missier , Marek Rusinkiewicz, Extending a Multidatabase Manipulation Language to Resolve Schema and Data Conflicts, Proceedings of the Sixth IFIP TC-2 Working Conference on Data Semantics: Database Applications Semantics, p.93-115, May 30-June 02, 1995
• 47: MUMICK,I.S.AND ROSS, K. A. 1993. Noodle: A language for declarative querying in objectoriented database. In Proceedings of the 3rd International Conference on Deductive and Object- Oriented Databases (DOOD'93) (Dec.). Lecture Notes in Computer Science, Vol. 760, Springer-Verlag, New York.
• 48: Gultekin Özsoyoğlu , Victor Matos , Meral Özsoyoğlu, Query processing techniques in the summary-table-by-example database query language, ACM Transactions on Database Systems (TODS), v.14 n.4, p.526-573, Dec. 1989 [doi>10.1145/76902.76906]
• 49: Gultekin Ozsoyoglu , Z. Meral Ozsoyoglu , Francisco Mata, A language and a physical organization technique for summary tables, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.3-16, May 1985, Austin, Texas, United States
• 50: Maurizio Panti , Luca Spalazzi , Alberto Giretti, A Case-Based Approach to Information Integration, Proceedings of the 26th International Conference on Very Large Data Bases, p.557-565, September 10-14, 2000
• 51: 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]
• 52: SADRI,F.AND WILSON, S. B. 1997. Implementation of SchemaSQL-A language for relational multi-database systems. Manuscript, www.uncg.edu/csadrif/papers.html.
• 53: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 54: Edward Sciore , Michael Siegel , Arnon Rosenthal, Using semantic values to facilitate interoperability among heterogeneous information systems, ACM Transactions on Database Systems (TODS), v.19 n.2, p.254-290, June 1994 [doi>10.1145/176567.176570]
• 55: Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
• 56: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 57: SHETH, A., ED. December, 1991. Semantic Issues in Multidatabase Systems. SIGMOD Record 20,4.
• 58: 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]
• 59: Arie Shoshani, OLAP and statistical databases: similarities and differences, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.185-196, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263682]
• 60: SQL STANDARDS HOME PAGE. 1996. SQL 3 articles and publications. URL: www.jcc.com/ sql articles.html.
• 61: SUBRAMANIAN,S.N.AND VENKATARAMAN, S. 1998. Query optimization using restructuring views. IBM Internal Report.
• 62: M. Wang , B. Iyer , J. S. Vitter, Scalable Mining for Classification Rules in Relational Databases, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.58, July 08-10, 1998

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: Relational databases
      H.2.5 Heterogeneous Databases

General Terms:
Algorithms, Languages

Keywords:
Information integration, SchemaSQL, multidatabase systems, restructuring views, schematic heterogeneity