Digital Symposium Collection 2000

On Efficiently Implementing SchemaSQL on an SQL Database System Laks V. S. Lakshmanan, Fereidoon Sadri, and Subbu N. Subramanian   View Paper (PDF)   Return to Implementing Advanced Data Models Abstract 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. References Note: References link to DBLP on the Web. [AIS93] Rakesh Agrawal , Tomasz Imielinski , Arun N. Swami : Database Mining: A Performance Perspective. TKDE 5(6) : 914-925(1993) [BLT86] José A. Blakeley , Per-Åke Larson , Frank Wm. Tompa : Efficiently Updating Materialized Views. SIGMOD Conference 1986 : 61-71 [CKPS95] Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200 [CKW93] Weidong Chen , Michael Kifer , David Scott Warren : HILOG: A Foundation for Higher-Order Logic Programming. JLP 15(3) : 187-230(1993) [CHQ95] Ashish Gupta , Venky Harinarayan , Dallan Quass : Aggregate-Query Processing in Data Warehousing Environments. VLDB 1995 : 358-369 [GHRU97] Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman : Index Selection for OLAP. ICDE 1997 : 208-219 [GL98] Frédéric Gingras , Laks V. S. Lakshmanan : nD-SQL: A Multi-Dimensional Language for Interoperability and OLAP. VLDB 1998 : 134-145 [GLRS93] John Grant , Witold Litwin , Nick Roussopoulos , Timos K. Sellis : Query Languages for Relational Multidatabases. VLDB Journal 2(2) : 153-171(1993) [GLS96] Marc Gyssens , Laks V. S. Lakshmanan , Iyer N. Subramanian : Tables as a Paradigm for Querying and Restructuring. PODS 1996 : 93-103 [GM96] Ashish Gupta , Inderpal Singh Mumick : What is the Data Warehousing Problem? (Are Materialized Views the Answer?). VLDB 1996 : 602 [GMS93] Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian : Maintaining Views Incrementally. SIGMOD Conference 1993 : 157-166 [HGW+95] Joachim Hammer , Hector Garcia-Molina , Jennifer Widom , Wilburt Labio , Yue Zhuge : The Stanford Data Warehousing Project. Data Engineering Bulletin 18(2) : 41-48(1995) [HRU96] Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman : Implementing Data Cubes Efficiently. SIGMOD Conf. 1996 : 205-216 [KKS92] Michael Kifer , Won Kim , Yehoshua Sagiv : Querying Object-Oriented Databases. SIGMOD Conference 1992 : 393-402 [KZ95] Ravi Krishnamurthy , Moshé M. Zloof : RBE: Rendering By Example. ICDE 1995 : 288-297 [KLK91] Ravi Krishnamurthy , Witold Litwin , William Kent : Language Features for Interoperability of Databases with Schematic Discrepancies. SIGMOD Conference 1991 : 40-49 [LMSS95] Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104 [LSS93] 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 [LSS96] Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian : SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems. VLDB 1996 : 239-250 [LSS97] Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian : Logic and Algebraic Languages for Interoperability in Multidatabase Systems. JLP 33(2) : 101-149(1997) [LSS99] ... [Mil98] Renée J. Miller : Using Schematically Heterogeneous Structures. SIGMOD Conference 1998 : 189-200 [MTW97] Renée J. Miller , Odysseas G. Tsatalos , John H. Williams : DataWeb: Customizable Database Publishing for the Web. IEEE MultiMedia 4(4) : 14-21(1997) [Ros92] Kenneth A. Ross : Relations with Relation Names as Arguments: Algebra and Calculus. PODS 1992 : 346-353 [SAB+95] ... [SDJL96] Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy : Answering Queries with Aggregation Using Views. VLDB 1996 : 318-329 [Sub97] ... [SV98] ... [TSY96] Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal 5(2) : 101-118(1996) [TPC93] ... [WIV98] Min Wang , Balakrishna R. Iyer , Jeffrey Scott Vitter : Scalable Mining for Classification Rules in Relational Databases. IDEAS 1998 : 58-67 [YPAG98] Ramana Yerneni , Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina : Fusion Queries over Internet Databases. EDBT 1998 : 57-71 BIBTEX @inproceedings{DBLP:conf/vldb/LakshmananSS99,   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,                 UK},    publisher = {Morgan Kaufmann},    year      = {1999},    isbn      = {1-55860-615-5},    pages     = {471-482},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM