Incremental maintenance for materialized XPath/XSLT views

ABSTRACT

This paper proposes an incremental maintenance algorithm that efficiently updates the materialized XPath/XSLT views defined using XPath expressions in XP^{([],*,//,vars)}. The algorithm consists of two processes. 1) The dynamic execution flow of an XSLT program is stored as an XT (XML Transformation) tree during the full transformation. 2) In response to a source XML data update, the impacted portions of the XT-tree are identified and maintained by partially re-evaluating the XSLT program. This paper discusses the XPath/XSLT features of incremental view maintenance for subtree insertion/deletion and applies them to the maintenance algorithm. Experiments show that the incremental maintenance algorithm outperforms full XML transformation algorithms by factors of up to 500.

REFERENCES

• 1: Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
• 2: 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
• 3: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68--88, 1997.
• 4: Geert Jan Bex , Sebastian Maneth , Frank Neven, A formal model for an expressive fragment of XSLT, Information Systems, v.27 n.1, p.21-39, March 2002 [doi>10.1016/S0306-4379(01)00033-3 ]
• 5: J. Clark. XSL transformations (XSLT) version 1.0, 16 November 1999. http://www.w3.org/TR/xslt.
• 6: J. Clark and S. DeRose. XML path language (XPath) version 1.0, 16 November 1999. http://www.w3.org/TR/xpath.
• 7: Y. Diao and M. J. Franklin. High-performance XML filtering: An overview of YFilter. In IEEE Data Engineering Bulletin, 2003.
• 8: K. Dimitrova, M. El-Sayed, and E. A. Rundensteiner. Order-sensitive view maintenance of materialized XQuery views. In Computer Science Technical Report Series. Worcester Polytechnic Institute, 2003.
• 9: M. El-Sayed, L. Wang, L. Ding, and E. A. Rundensteiner. An algebraic approach for incremental maintenance of materialized XQuery views. In Computer Science Technical Report Series. Worcester Polytechnic Institute, 2003.
• 10: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 11: A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques and applications. IEEE Data Engineering Bulletin, 18(2):3--18, 1995.
• 12: 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
• 13: I. JTC1/SC29/WG11. Mpeg-7 description definition language (DDL). http://archive.dstc.edu.au/mpeg7-ddl/.
• 14: Hyunchul Kang , Hosang Sung , ChanHo Moon, Deferred incremental refresh of XML materialized views: algorithms and performance evaluation, Proceedings of the fourteenth Australasian database conference, p.217-226, February 01, 2003, Adelaide, Australia
• 15: M. H. Kay. SAXON the XSLT and XQuery processor. http://saxon.sourceforge.net/.
• 16: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 17: Hartmut Liefke , Susan B. Davidson, View Maintenance for Hierarchical Semistructured Data, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.114-125, September 04-06, 2000
• 18: Dan Olteanu , Holger Meuss , Tim Furche , François Bry, XPath: Looking Forward, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.109-127, March 24-28, 2002
• 19: M. Onizuka, T. Honishi, F. Y. Chan, and R. Michigami. Incremental maintenance for materialized XPath/XSLT views (full version). http://xmltk.sourceforge.net/xtim.pdf.
• 20: C. Owens. PMC project P/META. http://www.ebu.ch/departments/technical/pmc/pmc_meta.html.
• 21: 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
• 22: Igor Tatarinov , Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Updating XML, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.413-424, May 21-24, 2001, Santa Barbara, California, United States
• 23: The XML:DB Initiative. XUpdate - XML update language, September 14 2000. http://www.xmldb.org/xupdate/.
• 24: TV-Anytime Forum. http://www.tv-anytime.org/.
• 25: Lionel Villard , Nabil Layaïda, An incremental XSLT transformation processor for XML document manipulation, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511508]
• 26: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages, Performance

Keywords:
XML, XPath, XSLT, materialized view, view maintenance