Incremental evaluation of schema-directed XML publishing

ABSTRACT

When large XML documents published from a database are maintained externally, it is inefficient to repeatedly recompute them when the database is updated. Vastly preferable is incremental update, as common for views stored in a data warehouse. However, to support schema-directed publishing, there may be no simple query that defines the mapping from the database to the external document. To meet the need for efficient incremental update, this paper studies two approaches for incremental evaluation of ATGs [4], a formalism for schema-directed XML publishing. The reduction approach seeks to push as much work as possible to the underlying DBMS. It is based on a relational encoding of XML trees and a nontrivial translation of ATGs to SQL 99 queries with recursion. However, a weakness of this approach is that it relies on high-end DBMS features rather than the lowest common denominator. In contrast, the bud-cut approach pushes only simple queries to the DBNS and performs the bulk of the work in middleware. It capitalizes on the tree-structure of XML views to minimize unnecessary recomputations and leverages optimization techniques developed for XML publishing. While implementation of the reduction approach is not yet in the reach of commercial DBMS, we have implemented the bud-cut approach and experimentally evaluated its performance compared to recomputation.

REFERENCES

• 1: Serge Abiteboul , Jason McHugh , Michael Rys , Vasilis Vassalos , Janet L. Wiener, Incremental Maintenance for Materialized Views over Semistructured Data, Proceedings of the 24rd International Conference on Very Large Data Bases, p.38-49, August 24-27, 1998
• 2: V. Apparao et al. Document Object Model (DOM) Level 1 Specification. W3C Recommendation, Oct. 1998.
• 3: Michael Benedikt , Chee-Yong Chan , Wenfei Fan , Juliana Freire , Rajeev Rastogi, Capturing both types and constraints in data integration, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872792]
• 4: M. Benedikt, C. Y. Chan, W. Fan, R. Rastogi, S. Zheng, and A. Zhou. DTD-directed publishing with attribute translation grammars. In VLDB, 2002.
• 5: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 6: José A. Blakeley , Neil Coburn , Per-:1Vke Larson, Updating derived relations: detecting irrelevant and autonomously computable updates, ACM Transactions on Database Systems (TODS), v.14 n.3, p.369-400, Sept. 1989 [doi>10.1145/68012.68015]
• 7: P. Bohannon, S. Ganguly, H. Korth, P. Narayan, and P. Shenoy. Optimizing view queries in ROLEX to support navigable result trees. In VLDB, 2002.
• 8: 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
• 9: Susan B. Davidson , Anthony Kosky, WOL: A Language for Database Transformations and Constraints, Proceedings of the Thirteenth International Conference on Data Engineering, p.55-65, April 07-11, 1997
• 10: K. Dimitrova, M. EL-Sayed, and E. Rundensteiner. Order-sensitive view maintenance of materialized XQuery views. In ER, 2003.
• 11: Mary Fernandez , Atsuyuki Morishima , Dan Suciu, Efficient evaluation of XML middle-ware queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.103-114, May 21-24, 2001, Santa Barbara, California, United States
• 12: Dieter Gluche , Torsten Grust , Christof Mainberger , Marc H. Scholl, Incremental Updates for Materialized OQL Views, Proceedings of the 5th International Conference on Deductive and Object-Oriented Databases, p.52-66, December 08-12, 1997
• 13: A. Gupta and I. Mumick. Materialized Views. MIT Press, 2000.
• 14: A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques, and applications, Data Engineering Bulletin, 18(2), 1995.
• 15: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 16: Intelligent Systems Research. XML from databases: ODBC2XML. http://www.intsysr.com/odbc2xml.htm.
• 17: R. Krishnamurthy, R. Kaushik, J. Naughton, and V. Chakaravarthy. Recursive XML schemes, recursive XML queries, and relational storage: XML-to-SQL query translation. In ICDE, 2003.
• 18: Harumi A. Kuno , Elke A. Rundensteiner, Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.768-792, September 1998 [doi>10.1109/69.729731]
• 19: Alexandros Labrinidis , Nick Roussopoulos, WebView materialization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.367-378, May 15-18, 2000, Dallas, Texas, United States
• 20: Alexandros Labrinidis , Nick Roussopoulos, Update Propagation Strategies for Improving the Quality of Data on the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.391-400, September 11-14, 2001
• 21: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 22: James J. Lu , Guido Moerkotte , Joachim Schue , V. S. Subrahmanian, Efficient maintenance of materialized mediated views, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.340-351, May 22-25, 1995, San Jose, California, United States
• 23: B. Ludäscher, Y. Papakonstantinou, and P. Velikhov. Navigation-driven evaluation of virtual mediated views. In EDBT, 2000.
• 24: Jim Melton , Alan Simon, SQL:1999: understanding relational language components, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 25: Oracle. Using XML in Oracle internet applications. http://technet.oracle.com/tech/xml/.
• 26: Yannis Papakonstantinou , Victor Vianu, Incremental Validation of XML Documents, Proceedings of the 9th International Conference on Database Theory, p.47-63, January 08-10, 2003
• 27: G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158710]
• 28: Michael Rys, Bringing the Internet to Your Database: Using SQLServer 2000 and XML to Build Loosely-Coupled Systems, Proceedings of the 17th International Conference on Data Engineering, p.465-472, April 02-06, 2001
• 29: D. Saha and C. R. Ramakrishnan. Incremental evaluation of tabled logic programs. In ICLP, 2003.
• 30: M. Staudt and M. Jarke. Incremental maintenance of externally materialized views. In VLDB Journal, 1996.
• 31: Dan Suciu, Query Decomposition and View Maintenance for Query Languages for Unstructured Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.227-238, September 03-06, 1996
• 32: Y. Wang, D. DeWitt, and J. Cai. X-Diff: An effective change detection algorithm for XML documents. In ICDE, 2003.
• 33: Yue Zhuge , Hector Garcia-Molina, Graph Structured Views and Their Incremental Maintenance, Proceedings of the Fourteenth International Conference on Data Engineering, p.116-125, February 23-27, 1998
• 34: Yue Zhuge , Héctor García-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States