On Efficiently Implementing SchemaSQL on an SQL Database System.

Laks V. S. Lakshmanan, Fereidoon Sadri, Subbu N. Subramanian: On Efficiently Implementing SchemaSQL on an SQL Database System. VLDB 1999: 471-482
  author    = {Laks V. S. Lakshmanan and
               Fereidoon Sadri and
               Subbu N. Subramanian},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {On Efficiently Implementing SchemaSQL on an SQL Database System},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {471-482},
  ee        = {db/conf/vldb/LakshmananSS99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP,}


SchemaSQL is a recently proposed extension to SQL for enabling multi-database interoperability. Several recently identified applications for SchemaSQL, however, mainly rely on its ability to treat data and schema labels in a uniform manner, and call for an efficient implementation of it on a single RDBMS. We first develop a logical algebra for SchemaSQL by combining classical relational algebra with four restructuring operators - unfold, fold, split, and unite - originally introduced in the context of the tabular data model by Gyssens et al. [GLS96], and suitably adapted to fit the needs of SchemaSQL. We give an algorithm for translating SchemaSQL queries/views involving restructuring, into the logical algebra above. We also provide physical algebraic operators which are useful for query optimization. Using the various operators as a vehicle, we give several alternate implementation strategies for SchemaSQL queries/views. All the proposed strategies can be implemented non-intrusively on top of existing relational DBMS, in that they do not require any additions to the existing set of plan operators. We conducted a series of performance experiments based on TPC-D benchmark data, using the IBM DB2 DBMS running on Windows/NT. In addition to showing the relative tradeoffs between various alternate strategies, our experiments show the feasibility of implementing SchemaSQL on top of traditional RDBMS in a non-intrusive manner. Furthermore, they also suggest new plan operators which might profitably be added to the existing set available to relational query optimizers, to further boost their performance.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents BibTeX


Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami: Database Mining: A Performance Perspective. IEEE Trans. Knowl. Data Eng. 5(6): 914-925(1993) BibTeX
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX
Weidong Chen, Michael Kifer, David Scott Warren: HILOG: A Foundation for Higher-Order Logic Programming. J. Log. Program. 15(3): 187-230(1993) BibTeX
Ashish Gupta, Venky Harinarayan, Dallan Quass: Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995: 358-369 BibTeX
Himanshu Gupta, Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman: Index Selection for OLAP. ICDE 1997: 208-219 BibTeX
Frédéric Gingras, Laks V. S. Lakshmanan: nD-SQL: A Multi-Dimensional Language for Interoperability and OLAP. VLDB 1998: 134-145 BibTeX
John Grant, Witold Litwin, Nick Roussopoulos, Timos K. Sellis: Query Languages for Relational Multidatabases. VLDB J. 2(2): 153-171(1993) BibTeX
Marc Gyssens, Laks V. S. Lakshmanan, Iyer N. Subramanian: Tables as a Paradigm for Querying and Restructuring. PODS 1996: 93-103 BibTeX
Ashish Gupta, Inderpal Singh Mumick: What is the Data Warehousing Problem? (Are Materialized Views the Answer?). VLDB 1996: 602 BibTeX
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX
Joachim Hammer, Hector Garcia-Molina, Jennifer Widom, Wilburt Labio, Yue Zhuge: The Stanford Data Warehousing Project. IEEE Data Eng. Bull. 18(2): 41-48(1995) BibTeX
Venky Harinarayan, Anand Rajaraman, Jeffrey D. Ullman: Implementing Data Cubes Efficiently. SIGMOD Conference 1996: 205-216 BibTeX
Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402 BibTeX
Ravi Krishnamurthy, Moshé M. Zloof: RBE: Rendering By Example. ICDE 1995: 288-297 BibTeX
Ravi Krishnamurthy, Witold Litwin, William Kent: Language Features for Interoperability of Databases with Schematic Discrepancies. SIGMOD Conference 1991: 40-49 BibTeX
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX
Laks V. S. Lakshmanan, Fereidoon Sadri, Iyer N. Subramanian: On the Logical Foundations of Schema Integration and Evolution in Heterogeneous Database Systems. DOOD 1993: 81-100 BibTeX
Laks V. S. Lakshmanan, Fereidoon Sadri, Iyer N. Subramanian: SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems. VLDB 1996: 239-250 BibTeX
Laks V. S. Lakshmanan, Fereidoon Sadri, Iyer N. Subramanian: Logic and Algebraic Languages for Interoperability in Multidatabase Systems. J. Log. Program. 33(2): 101-149(1997) BibTeX
Renée J. Miller: Using Schematically Heterogeneous Structures. SIGMOD Conference 1998: 189-200 BibTeX
Renée J. Miller, Odysseas G. Tsatalos, John H. Williams: DataWeb: Customizable Database Publishing for the Web. IEEE MultiMedia 4(4): 14-21(1997) BibTeX
Kenneth A. Ross: Relations with Relation Names as Arguments: Algebra and Calculus. PODS 1992: 346-353 BibTeX
Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. VLDB 1996: 318-329 BibTeX
Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB J. 5(2): 101-118(1996) BibTeX
Min Wang, Balakrishna R. Iyer, Jeffrey Scott Vitter: Scalable Mining for Classification Rules in Relational Databases. IDEAS 1998: 58-67 BibTeX
Ramana Yerneni, Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Fusion Queries over Internet Databases. EDBT 1998: 57-71 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:46:28 2009