• Database and Knowledge-Based Systems • Previous Articles     Next Articles

Updating Recursive XML Views of Relations

Byron Choi1,4, Gao Cong2,4, Wenfei Fan3,4, and Stratis D. Viglas4   

  1. 1Division of Information System, School of Computer Engineering, Nanyang Technological University, 639798, Singapore 2Microsoft Research Asia, Beijing 100080, China 3Bell Laboratories, Murray Hill, NJ07974-0636, U.S.A. 4University of Edinburgh, Edinburgh EH8 9LE, Scotland, U.K.
  • Received:2007-09-03 Revised:2008-03-07 Online:2008-07-10 Published:2008-07-10

This paper investigates the view update problem for {\sc XML} views published from relational data. We consider {\sc XML} views defined in terms of mappings directed by possibly recursive {\sc DTD}s compressed into {\sc DAG}s and stored in relations. We provide new techniques to efficiently support {\sc XML} view updates specified in terms of {\sc XP}ath expressions with recursion and complex filters. The interaction between {\sc XP}ath recursion and {\sc DAG} compression of {\sc XML} views makes the analysis of the {\sc XML} view update problem rather intriguing. Furthermore, many issues are still open even for relational view updates, and need to be explored. In response to these, on the {\sc XML} side, we revise the notion of side effects and update semantics based on the semantics of {\sc XML} views, and present efficient algorithms to translate {\sc XML} updates to relational view updates. On the relational side, we propose a mild condition on {\sc SPJ} views, and show that under this condition the analysis of deletions on relational views becomes { PTIME} while the insertion analysis is { NP}-complete. We develop an efficient algorithm to process relational view deletions, and a heuristic algorithm to handle view insertions. Finally, we present an experimental study to verify the effectiveness of our techniques.

Key words: Open Directory; Zero-Keyword Inquiry; information matching engine; layered keyword mapping;

[1] Stavros S Cosmadakis, Christos H Papadimitriou. Updates of relational views. {\it Journal of ACM}, 1984, 31(4): 742--760.
[2]} Umeshwar Dayal, Philip A Bernstein. On the correct translation of update operations on relational views. {\it ACM Transactions on Database Systems $($TODS$)$}, 1982, 7(3): 381--416.
[3]} Arthur Keller. Algorithms for translating view updates to database updates for views involving selections, projections, and joins. In {\it Proc. the fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems $($PODS$)$}, Portland, Oregon, USA, 1985, pp.154--163.
[4]} Jens Lechtenborger, Gottfried Vossen. On the computation of relational view complements. {\it ACM Transactions on Database Systems $($TODS$)$}, 2003, 28(2): 175--208.
[5]} IBM DB2 universal database {SQL} reference. IBM. www-306.ibm.com/software/data/db2/.
[6]} SQL reference. Oracle. www.oracle.com/technology/documen\-tation/.
[7]} SQL server. MSDN Library. msdn.microsoft.com/en-us/sqlserver/.
[8]} Philip Bohannon, Byron Choi, Wenfei Fan. Incremental evaluation of schema-directed {XML} publishing. In {\it Proc. the 2004 ACM SIGMOD International Conference on Management of Data $($SIGMOD$)$}, Paris, France, 2004, pp.503--514.
[9]} Michael J Carey, Jerry Kiernan, Jayavel Shanmugasundaram, Eugene J Shekita, Subbu N Subramanian. XPERANTO: Middleware for publishing object-relational data as {XML} documents. In {\it Proc. the 26th International Conference on Very Large Data Bases $($VLDB$)$}, Cairo, Egypt, 2000, pp.646--648.
[10]} Mary F Fernandez, Atsuyuki Morishima, Dan Suciu. Efficient evaluation of XML middleware queries. In {\it Proc. the 2001 ACM SIGMOD International Conference on Management of Data $($SIGMOD$)$}, Santa Barbara, CA, USA, 2001, pp.103--114.
[11]} Vanessa P Braganholo, Susan B Davidson, Carlos A Heuser. From {XML} view updates to relational view updates: Old solutions to a new problem. In {\it Proc. the Thirtieth International Conference on Very Large Data Bases $($VLDB$)$}, Toronto, Canada, 2004, pp.276--287.
[12]} L Wang, E A Rundensteiner, Murali Mani. UFilter: A lightweight {XML} view update checker. In {\it Proc. the 22nd International Conference on Data Engineering $($ICDE$)$}, Atlanta, USA, 2006, p.126.
[13]} L Wang, E A Rundensteiner, Murali Mani. Updating {XML} view published over relational databases: Towards the existence of a correct update mapping. {\it Data and Knowledge Engineering $($DKE$)$}, 2006, 58(3): 263--298.
[14]} Laux A, Martin L. XUpdate --- XML Update Language. 2000, http://www.xmldb.org /xupdate/xupdate-wd.html.
[15]} Sur G, Hammer J, Sim\'eon J. An XQuery-based language for processing updates in XML. In {\it Proc. Programming Language Technologies for XML $($PLAN-X$)$}, Venice, Italy, 2004.
[16]} Byron Choi. What are real {DTDs} like. In {\it Proc. the Fifth International Workshop on the Web and Databases $($Webdb$)$}, Madison, Wisconsin, USA, 2002, pp.43--48.
[17]} Rajasekar Krishnamurthy, Raghav Kaushik, Jeffrey Naughton. XML-SQL query translation literature: The state of the art and open problems. In {\it Proc. Database and XML Technologies, First International XML Database Symposium $($XSym$)$}, Berlin, Germany, 2003, pp.1--18.
[18]} Buneman P, Khanna S, Tan W. On propagation of deletions and annotations through views. In {\it Proc. the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems $($PODS$)$}, Wisconsin, USA, 2002, pp.150--158.
[19]} Byron Choi, Gao Cong, Wenfei Fan, Stratis Viglas. Updating recursive XML views of relations. In {\it Proc. the 23nd International Conference on Data Engineering $($ICDE$)$}, Istanbul, Turkey, 2007, pp.766--775.
[20]} Michael Benedikt, Chee Yong Chan, Weifei Fan, Rajeev Rastogi, Shihui Zheng, Aoying Zhou. DTD-directed publishing with attribute translation grammars. In {\it Proc, the 28th International Conference on Very Large Data Bases $($VLDB$)$}, Hong Kong, China, 2002, pp.838--849.
[21]} Jayavel Shanmugasundaram, Kristin Tufte, Chun Zhang, Gang He, David J DeWitt, Jeffrey F Naughton. Relational databases for querying XML documents: Limitations and opportunities. In {\it Proc. 25th International Conference on Very Large Data Bases $($VLDB$)$}, Edinburgh, Scotland, UK, 1999, pp.302--314.
[22]} Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms. McGraw-Hill, 2001.
[23]} Li Chen, Amarnath Gupta, M Erdem Kurul. Stack-based algorithms for pattern matching on DAGs. In {\it Proc. the 31st International Conference on Very Large Data Bases $($VLDB$)$}, Trondheim, Norway, 2005, pp.493--504.
[24]} Ralf Schenkel, Anja Theobald, Gerhard Weikum. Efficient creation and incremental maintenance of the {HOPI} index for complex {XML} document collections. In {\it Proc. the 21st International Conference on Data Engineering $($ICDE$)$}, Tokyo, Japan, 2005, pp.360--371.
[25]} Christoph Koch. Efficient processing of expressive node-selecting queries on {XML} data in secondary storage: A tree automata-based approach. In {\it Proc. the 29th International Conference on Very Large Data Bases $($VLDB$)$}, Berlin, Germany, 2003, pp.249--260.
[26]} Italiano G F. Finding paths and deleting edges in directed acyclic graphs. {\it Inf. Process. Lett.}, 1988, 28.
[27]} King V, Sagert G. A fully dynamic algorithm for maintaining the transitive closure. In {\it Proc. ACM Symposium on Theory of Computing}, 1999.
[28]} Alberto Marchetti-Spaccamela, Umberto Nanni, Hans Rohnert. Maintaining a topological order under edge insertions. {\it Information Processing Letters}, 1996, 59(1): 53--58.
[29]} Michael Garey, David Johnson. Computers and Intractability: A Guide to the Theory of {NP}-Completeness. 1979.
[30]} Bart Selman, Henry Kautz. Walksat Home Page. 2004. http://www.cs.washington.edu/homes/kautz/walksat/.
[31]} Elias Koutsoupias, Christos H Papadimitriou. On the greedy algorithm for satisfiability. {\it Information Processing Letters}, 1992, 43(1): 53--55.
[32]} Wang L, Mulchandani M, Rundensteiner E. Updating {XQuery} views published over relational data: A round-trip case study. In {\it Proc. XML Database Symposium}, 2003, pp.223--237.
[33]} Wang L, Rundensteiner E A. Updating {XML} views published over relational databases: Towards the existence of a correct update mapping. {Technical Report, Worcester Polytechnic Institute}, 2004.
[34]} Yingwei Cui, Jennifer Widom. Run-time translation of view tuple deletions using data lineage. Technical Report, Stanford University, 2001.
[35]} Gao Cong, Wenfei Fan, Floris Geerts. Annotation propagation revisited for key preserving views. In {\it Proc. the 15th ACM International Conference on Information and Knowledge Management}, Arlington, Virginia, USA, 2006, pp.632--641.
[36]} Cohen E, Kaplan H, Milo T. Labeling dynamic {XML} tree. In {\it Proc. the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems $($PODS$)$}, Madison, Wisconsin, USA, 2002, pp.271--281.
[1] LIU Bin; LU Zengxiang; GAN Quan; FENG Ao; WANG Pu;. Infomarker—A New Internet Information Service System [J]. , 2000, 15(3): 300-304.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved