| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Incremental Maintenance of Schema-Restructuring Views in SchemaSQL
September 2004 (vol. 16 no. 9)
pp. 1096-1111
The integration of data, especially from heterogeneous sources, is a hard and widely studied problem. One particularly challenging issue is the integration of sources that are semantically equivalent but schematically heterogeneous. While two such data sources may represent the same information, one may store the information inside tuples (data) while the other may store it in attribute or relation names (schema). The SchemaSQL query language is a recent solution to this problem powerful enough to restructure such sources into each other without the loss of information. In this paper, we propose the first incremental view maintenance strategy for such schema-restructuring views. Our strategy, based on an algebraic representation of the view query, correctly transforms a data update or a schema change to a source into sequences of schema and data updates to be applied to the view. We also introduce an optimization of incremental maintenance using batching. We present a proof of correctness of the propagation approach. We also describe the implementation of our SchemaSQL Query Processor and View Maintainer. Last, our experimental results demonstrate that, in many cases, incremental SchemaSQL view maintenance is significantly faster than complete view recomputation.
[1] 1096 D. Florescu, L. Raschid, and P. Valduriez, Using Heterogenous Equivalence for Query Rewriting in Multidatabase Systems Proc. Third Int'l Conf. Cooperative Information Systems, pp. 158-169, 1995.[2] J.-R. Gruser, L. Raschid, M.E. Vidal, and L. Bright, Wrapper Generation for Web-Accessible Data Sources Proc. Sixth Int'l Conf. Cooperative Information Systems, pp. 14-23, 1998.[3] J. Hammer, H. Garcia-Molina, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom, Information Translation, Mediation, and Mosaic-Based Browsing in the TSIMMIS System Proc. SIGMOD, pp. 483-483, 1995.[4] R.J. Miller, Y. Ioannidis, and R. Ramakrishnan, The Use of Information Capacity in Schema Integration and Translation Proc. 19th Int'l Conf. Very Large Data Bases (VLDB), pp. 120-133, Aug. 1993.[5] L.V.S. Lakshmanan, F. Sadri, and I.N. Subramanian, SchemaSQL A Language for Interoperability in Relational Multi-Database Systems Proc. Int'l Conf. Very Large Data Bases, T.M. Vijayaraman et al., eds., pp. 239-250, Sept. 1996.[6] L.V.S. Lakshmanan, F. Sadri, and S.N. Subramanian, On Efficiently ImplementingSchemaSQLon an SQL Database System Proc. Int'l Conf. Very Large Data Bases, pp. 471-482, 1999.[7] L.V.S. Lakshmanan, F. Sadri, and S.N. Subramanian, SchemaSQL An Extension to SQL for Multidatabase Interoperability ACM Trans. Database Systems (TODS), vol. 26, no. 4, pp. 476-519, Dec. 2001.[8] R.J. Miller, Using Schematically Heterogeneous Structures SIGMOD Record (ACM Special Interest Group on Management of Data), vol. 27, no. 2, pp. 189-200, 1998.[9] J.A. Blakeley, P.-E. Larson, and F.W. Tompa, Efficiently Updating Materialized Views Proc. SIGMOD, pp. 61-71, 1986.[10] X. Qian and G. Wiederhold, Incremental Recomputation of Active Relational Expressions IEEE Trans. Knowledge and Data Eng. (TKDE), vol. 3, no. 3, pp. 337-341, Sept. 1991.[11] A. Gupta, I.S. Mumick, and V.S. Subrahmanian, Maintaining Views Incrementally Proc. SIGMOD, pp. 157-166, 1993.[12] T. Griffin and L. Libkin, Incremental Maintenance of Views with Duplicates Proc. SIGMOD, pp. 328-339, 1995.[13] M.K. Mohania, S. Konomi, and Y. Kambayashi, Incremental Maintenance of Materialized Views Database and Expert Systems Applications (DEXA), pp. 551-560, 1997.[14] Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom, View Maintenance in a Warehousing Environment Proc. SIGMOD, pp. 316-327, May 1995.[15] A. Koeller and E.A. Rundensteiner, Incremental Maintenance of Schema-Restructuring Views Proc. Int'l Conf. Extending Database Technology (EDBT), pp. 354-371, 2002.[16] M. Gyssens, L.V.S. Lakshmanan, and I.N. Subramanian, Tables as a Paradigm for Querying and Restructuring (extended abstract) Proc. ACM Symp. Principles of Database Systems, vol. 15, pp. 93-103, 1996.[17] A. Koeller and E.A. Rundensteiner, Incremental Maintenance of Schema-Restructuring Views inSchemaSQL Worcester Polytechnic Inst., Dept. of Computer Science, Technical Report WPI-CS-TR-00-25, Jan. 2001, www.cs.wpi.edu/Resourcestechreports.[18] M. Tork Roth, M. Arya, L.M. Haas, M.J. Carey, W. Cody, R. Fagin, P.M. Schwarz, J. Thomas, and E.L. Wimmers, The Garlic Project SIGMOD Record (ACM Special Interest Group on Management of Data), vol. 25, no. 2, p. 557, 1996.[19] A. Tomasic, L. Raschid, and P. Valduriez, Scaling Heterogeneous Databases and the Design of DISCO INRIA, technical report, 1995.[20] R. Krishnamurthy, W. Litwin, and W. Kent, Language Features for Interoperability of Databases with Schematic Discrepancies SIGMOD Record (ACM Special Interest Group on Management of Data), vol. 20, no. 2, pp. 40-49, June 1991.[21] W. Chen, M. Kifer, and D. Warren, Hilog as a Platform for Database Languages IEEE Data Eng. Bull., vol. 12, no. 3, p. 37, Sept. 1989.[22] F. Gingras, L. Lakshmanan, I.N. Subramanian, D. Papoulis, and N. Shiri, Languages for Multi-Database Interoperability Proc. SIGMOD, pp. 536-538, 1997.[23] W. Litwin, A. Abdellatif, A. Zeroual, B. Nicolas, and P. Vigier, MSQL: A Multidatabase Language Information Sciences, vol. 49, no. 1, 1989.[24] D. Agrawal, A. El Abbadi, A. Singh, and T. Yurek, Efficient View Maintenance at Data Warehouses Proc. SIGMOD, pp. 417-427, 1997.[25] L.S. Colby, T. Griffin, L. Libkin, I.S. Mumick, and H. Trickey, Algorithms for Deferred View Maintenance Proc. SIGMOD, pp. 469-480, 1996.
Index Terms:
Heterogeneous databases, materialized views, SchemaSQL, incremental view maintenance, schema restructuring.
Citation:
Andreas Koeller, Elke A. Rundensteiner, "Incremental Maintenance of Schema-Restructuring Views in SchemaSQL," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1096-1111, Sept. 2004, doi:10.1109/TKDE.2004.42
