research-article

View update translation for XML

Authors:

Anne-Cécile Caron,

Sławek StaworkoAuthors Info & Claims

ICDT '11: Proceedings of the 14th International Conference on Database Theory

Pages 42 - 53

https://doi.org/10.1145/1938551.1938560

Published: 21 March 2011 Publication History

Abstract

We study the problem of update translation for views on XML documents. More precisely, given an XML view definition and a user defined view update program, find a source update program that translates the view update without side effects on the view. Additionally, we require the translation to be defined on all possible source documents; this corresponds to Hegner's notion of uniform translation. The existence of such translation would allow to update XML views without the need of materialization.

The class of views we consider can remove parts of the document and rename nodes. Our update programs define the simultaneous application of a collection of atomic update operations among insertion/deletion of a subtree and node renaming. Such update programs are compatible with the XQuery Update Facility (XQUF) snapshot semantics. Both views and update programs are represented by recognizable tree languages. We present as a proof of concept a small fragment of XQUF that can be expressed by our update programs, thus allows for update propagation.

Two settings for the update problem are studied: without source constraints, where all source updates are allowed, and with source constraints, where there is a restricted set of authorized source updates. Using tree automata techniques, we establish that without constraints, all view updates are uniformly translatable and the translation is tractable. In presence of constraints, not all view updates are uniformly translatable. However, we introduce a reasonable restriction on update programs for which uniform translation with constraints becomes possible.

References

[1]

I. J. Aalbersberg and H. J. Hoogeboom. Decision problems for regular trace languages. In 14th International Colloquium on Automata, languages and programming, pages 250--259, London, UK, 1987. Springer-Verlag.

Digital Library

[2]

C. Allauzen and M. Mohri. An optimal pre-determinization algorithm for weighted transducers. Theoretical Computer Science, 328(1--2):3--8, 2004.

Digital Library

[3]

F. Bancilhon and N. Spyratos. Update semantics of relational views. ACM Trans. Database Syst., 6(4):557--575, 1981.

Digital Library

[4]

J. Berstel. Transductions and context-free languages, volume 38 of Leitfäden der Angewandten Mathematik und Mechanik. B. G. Teubner, Stuttgart, 1979.

[5]

M. Bojańczyk and I. Waluciewicz. Forest algebras. In "Logic and Automata". Amsterdam University Press, 2007.

[6]

P. Boncz, T. Grust, M. Keulen, S. Manegold, J. Rittinger, and J. Teubner. MonetDB/XQuery: a fast XQuery processor powered by a relational engine. In ACM SIGMOD International Conference on Management of Data, pages 479--490, 2006.

Digital Library

[7]

V. P. Braganholo, S. B. Davidson, and C. A. Heuser. PATAXÓ: A framework to allow updates through XML views. ACM Transactions on Database Systems (TODS), 31, 2006.

Digital Library

[8]

D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi. An automata-theoretic approach to regular XPath. In DBPL, pages 18--35, 2009.

Digital Library

[9]

B. Choi, G. Cong, W. Fan, and S. D. Viglas. Updating recursive XML views of relations. Journal of Computer Science and Technology, 23, 2008.

Digital Library

[10]

E. F. Codd. Recent investigations in relational data base systems. In IFIP Congress, pages 1017--1021, 1974.

[11]

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, 2007. release October, 12th 2007.

[12]

S. S. Cosmadakis and C. H. Papadimitriou. Updates of relational views. J. ACM, 31(4):742--760, 1984.

Digital Library

[13]

U. Dayal and P. A. Bernstein. On the correct translation of update operations on relational views. ACM Trans. Database Syst., 7(3):381--416, 1982.

Digital Library

[14]

R. Fagin, J. D. Ullman, and M. Y. Vardi. On the semantics of updates in databases. In PODS, pages 352--365, 1983.

Digital Library

[15]

W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis. Rewriting regular XPath queries on XML views. In ICDE, pages 666--675, 2007.

[16]

L. Fegaras. Propagating updates through XML views using lineage tracing. In International Conference on Data Engineering (ICDE), 2010.

[17]

E. Filiot, J.-F. Raskin, P.-A. Reynier, F. Servais, and J.-M. Talbot. Properties of visibly pushdown transducers. In To appear in MFCS, 2010.

Digital Library

[18]

J. Foster, B. Pierce, and S. Zdancewic. Updatable security views. In Computer Security Foundations Symposium, 2009.

Digital Library

[19]

J. N. Foster, M. B. Greenwald, J. T. Moore, B. C. Pierce, and A. Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 2007.

Digital Library

[20]

X. Franc. XQuery update for the impatient. Available on http://www.xmlmind.com/tutorials/XQueryUpdate/index.html.

[21]

G. Gottlob, P. Paolini, and R. Zicari. Properties and update semantics of consistent views. ACM Trans. Database Syst., 13(4):486--524, 1988.

Digital Library

[22]

T. V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. J. ACM, 15(3):409--413, 1968.

Digital Library

[23]

B. Groz, S. Staworko, A.-C. Caron, Y. Roos, and S. Tison. XML security views revisited. In International Symposium on Database Programming Languages (DBPL), volume 5708 of Lecture Notes in Computer Science. Springer, August 2009.

Digital Library

[24]

S. J. Hegner. Foundations of canonical update support for closed database views. In Third International Conference on Database Theory Paris (ICDT'90), 1990.

Digital Library

[25]

T. Jiang, L. Wang, and K. Zhang. Alignment of trees - an alternative to tree edit. Theor. Comput. Sci., 143(1):137--148, 1995.

Digital Library

[26]

C. Koch. Efficient processing of expressive node-selecting queries on XML data in secondary storage: A tree automata-based approach. In VLDB, pages 249--260, 2003.

Digital Library

[27]

L. Libkin and C. Sirangelo. Reasoning about XML with temporal logics and automata. In Proceedings of the International Conferences on Logic for Programming, Artificial Intelligence and Reasoning (LPAR'08), 2008.

Digital Library

[28]

D. Liu, Z. Hu, and M. Takeichi. Bidirectional interpretation of XQuery. In ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation (PEPM), pages 21--30, 2007.

Digital Library

[29]

M. Murata. Hedge automata: A formal model for XML schemata. Technical report, Fuji Xerox Information Systems, 1999.

[30]

W. Plandowski. Testing equivalence of morphisms on context-free languages. In ESA, pages 460--470, 1994.

Digital Library

[31]

M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Bull. Amer. Math. Soc., 74:1025--1029, 1968.

[32]

J.-F. Raskin and F. Servais. Visibly pushdown transducers. In ICALP (2), pages 386--397, 2008.

Digital Library

[33]

N. Rassadko. Query rewriting algorithm evaluation for XML security views. In Secure Data Management (VLDB Workshop), volume 4721 of Lecture Notes in Computer Science, pages 64--80. Springer, 2007.

Digital Library

[34]

T. Schwentick. Automata for XML - a survey. J. Comput. Syst. Sci., 73(3):289--315, 2007.

Digital Library

[35]

S. Staworko, I. Boneva, and B. Groz. The view update problem for XML. In EDBT/ICDT workshop (XML Updates), March 2010.

Digital Library

[36]

I. Tatarinov, K. Beyer, and J. Shanmugasundaram. Storing and querying ordered XML using a relational database system. In ACM SIGMOD International Conference on Management of Data, 2002.

Digital Library

[37]

R. Vercammen, J. Hidders, and J. Paredaens. Query translation for XPath-based security views. In EDBT Workshops, volume 4254 of Lecture Notes in Computer Science, pages 250--263. Springer, 2006.

Digital Library

[38]

W3C. Extensible markup language (XML) 1.0, 1999. http://www.w3.org/TR/xml/.

[39]

W3C. XML path language (XPath) 1.0, 1999. http://www.w3.org/TR/xpath.

[40]

W3C. XML query (XQuery), 2007. http://www.w3.org/XML/Query.

[41]

W3C. XQuery update facility 1.0, 2009. http://www.w3.org/TR/xquery-update-10/.

[42]

L. Wang, E. A. Rundensteiner, and M. Mani. Updating XML views published over relational databases: Towards the existence of a correct update mapping. Data and Knowledge Engineering, 58, 2006.

Digital Library

Cited By

Thimma MFang Liu Jingqiang Lin Bo Luo (2015)HyXAC: Hybrid XML Access Control Integrating View-Based and Query-Rewriting ApproachesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2015.240736627:8(2190-2202)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1109/TKDE.2015.2407366
Walkingshaw EOstermann K(2014)Projectional editing of variational softwareACM SIGPLAN Notices10.1145/2775053.265876650:3(29-38)Online publication date: 15-Sep-2014
https://dl.acm.org/doi/10.1145/2775053.2658766
Walkingshaw EOstermann KSchultz UFlatt M(2014)Projectional editing of variational softwareProceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences10.1145/2658761.2658766(29-38)Online publication date: 15-Sep-2014
https://dl.acm.org/doi/10.1145/2658761.2658766
Show More Cited By

Index Terms

View update translation for XML
1. Information systems
  1. Data management systems

Recommendations

Effective and efficient update of xml in RDBMS
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Querying XML effectively and efficiently using declarative languages such as XQuery and XPath has been widely studied in both academic and industrial settings. Most RDBMS vendors now support XML as a native data type with SQL/XML and XQuery support over ...
Update XML data by using graphical languages
ER '07: Tutorials, posters, panels and industrial contributions at the 26th international conference on Conceptual modeling - Volume 83

To be a full-featured data exchange format, XML should support not only queries but also updates on its contents. The new W3C XML update facility has proposed a set of operators (insert, delete, replace and rename) and expressions to modify XML data. ...
A Comparative Study of View Update Problem
DSDE '10: Proceedings of the 2010 International Conference on Data Storage and Data Engineering

XML has become the de facto standard for representing and interchanging data in web-based applications. And XML view, a virtual window for specified users, has been widely applied. In practical system, users encounter the so-called view update problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDT '11: Proceedings of the 14th International Conference on Database Theory

March 2011

285 pages

ISBN:9781450305297

DOI:10.1145/1938551

Program Chair:
Tova Milo
Tel Aviv University, Israel

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 March 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EDBT/ICDT '11

EDBT/ICDT '11: EDBT/ICDT '11 joint conference

March 21 - 24, 2011

Uppsala, Sweden

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
172
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Thimma MFang Liu Jingqiang Lin Bo Luo (2015)HyXAC: Hybrid XML Access Control Integrating View-Based and Query-Rewriting ApproachesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2015.240736627:8(2190-2202)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1109/TKDE.2015.2407366
Walkingshaw EOstermann K(2014)Projectional editing of variational softwareACM SIGPLAN Notices10.1145/2775053.265876650:3(29-38)Online publication date: 15-Sep-2014
https://dl.acm.org/doi/10.1145/2775053.2658766
Walkingshaw EOstermann KSchultz UFlatt M(2014)Projectional editing of variational softwareProceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences10.1145/2658761.2658766(29-38)Online publication date: 15-Sep-2014
https://dl.acm.org/doi/10.1145/2658761.2658766
Peng YChoi BXu JHu HBhowmick S(2014)Side-Effect Estimation: A Filtering Approach to the View Update ProblemIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2013.11526:9(2307-2322)Online publication date: Sep-2014
https://doi.org/10.1109/TKDE.2013.115
Solimando ADelzanno GGuerrini G(2014)Validating XML document adaptations via Hedge Automata transformationsTheoretical Computer Science10.1016/j.tcs.2014.04.023560:P3(251-268)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.1016/j.tcs.2014.04.023
LIU DHU ZTAKEICHI M(2013)An expressive bidirectional transformation language for XQuery view updateProgress in Informatics10.2201/NiiPi.2013.10.6(89)Online publication date: Mar-2013
https://doi.org/10.2201/NiiPi.2013.10.6
Solimando ADelzanno GGuerrini G(2012)Automata-based Static Analysis of XML Document AdaptationElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.96.796(85-98)Online publication date: 7-Oct-2012
https://doi.org/10.4204/EPTCS.96.7
Bravo LCheney JFundulaki ISegovia R(2012)Consistency and repair for XML write-access control policiesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-012-0273-y21:6(843-867)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1007/s00778-012-0273-y
Liu JLiu CHaerder TYu J(2012)Updating typical XML viewsProceedings of the 17th international conference on Database Systems for Advanced Applications - Volume Part I10.1007/978-3-642-29038-1_11(126-140)Online publication date: 15-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29038-1_11

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents