Updates and views dependencies in semi-structured databases

ABSTRACT

In this paper we study the classical problem of the impact of an update on a view defined over semi-structured data. We adopt the following working hypotheses: (i) the source document is modeled by an unranked, labeled, ordered tree, (ii) a view v is a tree query whose evaluation on the source document provides a desired partial view of the document, (iii) a class of updates C is also given by a tree query selecting the nodes to modify. We then study the following problem: given a view query v and a class of updates C, is it possible to detect if the view v is independent of each update q in C? We show that the problem is in general PSPACE-hard. We propose a sufficient condition evaluable in polynomial time ensuring the independence of a view v with respect to a class of updates C. We then consider the class of linear view queries for which the problem becomes polynomial.

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: M. Akhtar Ali , Alvaro A. A. Fernandes , Norman W. Paton, MOVIE: an incremental maintenance system for materialized object views, Data & Knowledge Engineering, v.47 n.2, p.131-166, November 2003 [doi>10.1016/S0169-023X(03)00048-X]
• 3: Andrei Arion , Véronique Benzaken , Ioana Manolescu , Yannis Papakonstantinou, Structured materialized views for XML queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 4: Andrey Balmin , Fatma Özcan , Kevin S. Beyer , Roberta J. Cochrane , Hamid Pirahesh, A framework for using materialized XPath views in XML query processing, Proceedings of the Thirtieth international conference on Very large data bases, p.60-71, August 31-September 03, 2004, Toronto, Canada
• 5: M. Benedikt, A. Bonifati, S. Flesca, and A. Vyas. Verification of tree updates for optimization. In CAV, volume 3576, pages 379--393. Springer, 2005.
• 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: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 8: Changwoo Byun , Ilkook Yun , Seog Park, An Efficient Detection of Conflicting Updates in Valid XML, Proceedings of the 7th IEEE International Conference on Computer and Information Technology, p.17-22, October 16-19, 2007
• 9: K. Dimitrova, M. El-Sayed, and E. Rundensteiner. Order-sensitive view maintenance of materialized xquery views, 2003.
• 10: G. Ghelli, K. H. Rose, and J. Siméon. Commutativity analysis in XML update languages. In ICDT, pages 374--388, 2007.
• 11: T. Griffin and L. Libkin. Incremental maintenance of views with duplicates. pages 328--339, 1995.
• 12: A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques, and applictions. In Proc. 24th Int. Conf. Very Large Data Bases, VLDB, 1995.
• 13: 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
• 14: Laks V. S. Lakshmanan , Hui Wang , Zheng Zhao, Answering tree pattern queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 15: D. Laurent , J. Lechtenbörger , N. Spyratos , G. Vossen, Monotonic complements for independent data warehouses, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.295-315, December 2001 [doi>10.1007/s007780100055]
• 16: 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
• 17: Gerome Miklau , Dan Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM (JACM), v.51 n.1, p.2-45, January 2004 [doi>10.1145/962446.962448]
• 18: M. Onizuka, F. Y. Chan, R. Michigami, and T. Honishi. Incremental maintenance for materialized XPath/XSLT views.
• 19: L. Quan, L. Chen, and E. Rundensteiner. Efficient refresh in an XQL-based web caching system, 2000.
• 20: M. Raghavachari and O. Shmueli. Conflicting XML updates. In Advances in Database Technology - EDBT, volume 3896, pages 552--569, 2006.
• 21: Arsany Sawires , Junichi Tatemura , Oliver Po , Divyakant Agrawal , K. SelÇuk Candan, Incremental maintenance of path-expression views, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066208]
• 22: M. H. Scholl, C. Laasch, and M. Tresch. Updatable views in object-oriented databases. In Proc. 2nd Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), number 566, 1991.
• 23: Dimitra Vista , Alberto O. Mendelzon, Optimizing incremental view maintenance expressions in relational databases, University of Toronto, Toronto, Ont., Canada, 1997
• 24: W. C. XPath. XML path language(XPath) version 1.0. Novembre 1999.
• 25: 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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Design

Keywords:
XML queries, semi-structured data, tree automata, updates, views