Article

Reasoning about XML update constraints

Authors:

Serge Abiteboul,

Tova MiloAuthors Info & Claims

PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 195 - 204

https://doi.org/10.1145/1265530.1265558

Published: 11 June 2007 Publication History

Abstract

We introduce in this paper a class of constraints for describing howan XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying expressive power. Besides classical constraint implication, we also consider an instance-based approach. More precisely, we study implication with respect to a current tree instance, resulting from a series of unknown updates. The main motivation of our work is reasoning about data integrity under update restrictions in contexts where owners may lose control over their data, such as in publishing or exchange.

References

[1]

S. Abiteboul, B. Cautis, A. Fiat, and T. Milo. Digital signatures for modifiable collections. In ARES, 2006.

Digital Library

[2]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[3]

S. Abiteboul, L. Segoufin, and V. Vianu. Representing and querying XML with incomplete information. In PODS, 2001.

Digital Library

[4]

S. Abiteboul and V. Vianu. Regular path queries with constraints. J. Comput. Syst. Sci., 58(3), 1999.

Digital Library

[5]

M. Arenas. Design principles for XML data. PhD thesis, 2005.

Digital Library

[6]

M. Arenas and L. Libkin. XML data exchange: consistency and query answering. In PODS, 2005.

Digital Library

[7]

M. Arenas, W. Fan, and L. Libkin. Consistency of XML specifications. In Inconsistency Tolerance, 2005.

Digital Library

[8]

M. Bellare, O. Goldreich, and S. Goldwasser. Incremental cryptography: The case of hashing and signing. Lecture Notes in Computer Science, 1994.

Digital Library

[9]

M. Benedikt and C. Koch. XPath leashed. Technical report, 2006.

[10]

M. Bojanczyk, C. David, A. Muscholl, T. Schwentick, and L. Segoufin. Two-variable logic on data trees and XML reasoning. In PODS, 2006.

Digital Library

[11]

P. Buneman, S. Davidson, W. Fan, C. Hara, and W. C. Tan. Reasoning about keys for XML. Inf. Syst., 28(8), 2003.

Digital Library

[12]

B. Cautis, S. Abiteboul, and T. Milo. Reasoning about XML update constraints. In BDA, 2006.

[13]

C. Y. Chan, W. Fan, P. Felber, M. N. Garofalakis, and R. Rastogi. Tree pattern aggregation for scalable XML data dissemination. In VLDB, 2002.

Digital Library

[14]

A. Deutsch and V. Tannen. XML queries and constraints, containment and reformulation. Theor. Comput. Sci., 336(1), 2005.

Digital Library

[15]

P. Devanbu, M. Gertz, C. Martel, and S. Stubblebine. Authentic third-party data publication. In IFIP Workshop on Database Security, 2000.

Digital Library

[16]

W. Fan. XML constraints: Specification, analysis, and applications. In DEXA Workshops, 2005.

[17]

W. Fan and L. Libkin. On XML integrity constraints in the presence of DTDs. J. ACM, 2002.

Digital Library

[18]

W. Fan and J. Siméon. Integrity constraints for XML. J. Comput. Syst. Sci., 66(1), 2003.

Digital Library

[19]

G. Gottlob, C. Koch, R. Pichler, and L. Segoufin. The complexity of XPath query evaluation and xml typing. J. ACM, 52(2), 2005.

Digital Library

[20]

T. J. Green, G. Miklau, M. Onizuka, and D. Suciu. Processing XML streams with deterministic automata. In ICDT, 2003.

Digital Library

[21]

R. Johnson, D. Molnar, D. Song, and D. Wagner. Homomorphic signature schemes. In CT-RSA, 2002.

Digital Library

[22]

G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. In Proc. of ACM PODS, 2002.

Digital Library

[23]

G. Miklau and D. Suciu. Modeling integrity in data exchange. In SDM, 2004.

[24]

F. Neven and T. Schwentick. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods in Computer Science, 2 (3:1), 2006.

[25]

Y. Papakonstantinou and V. Vianu. DTD inference for views of XML data. In PODS, 2000.

Digital Library

[26]

R. L. Rivest. Two signature schemes., 2000. Manuscript.

[27]

T. Schwentick. XPath query containment. SIGMOD Record, 33 (1), 2004.

Digital Library

[28]

I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S. Weld. Updating XML. In SIGMOD, 2001.

Digital Library

[29]

P. Wadler. A formal semantics of patterns in XSLT, 1999.

[30]

Extensible Markup Language 1.0 (2nd Edition). http://www.w3.org/TR/REC-xml.

[31]

The XML Schema specification. http://www.w3.org/TR/XML/Schema.

Cited By

David CGheerbrant ALibkin LMartens W(2013)Containment of pattern-based queries over data treesProceedings of the 16th International Conference on Database Theory10.1145/2448496.2448521(201-212)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2448496.2448521
Yan LMa ZZhang FYan LMa ZZhang F(2013)Fuzzy XML ReasoningFuzzy XML Data Management10.1007/978-3-642-44899-7_7(169-208)Online publication date: 26-Nov-2013
https://doi.org/10.1007/978-3-642-44899-7_7
Gheerbrant ALibkin LSirangelo C(2013)Reasoning about pattern-based XML queriesProceedings of the 7th international conference on Web Reasoning and Rule Systems10.1007/978-3-642-39666-3_2(4-18)Online publication date: 27-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39666-3_2
Show More Cited By

Index Terms

Reasoning about XML update constraints

Recommendations

Reasoning about XML update constraints

We introduce in this paper a class of constraints for describing how an XML document can evolve, namely XML update constraints. For these constraints, we study the implication problem, giving algorithms and complexity results for constraints of varying ...
On XML integrity constraints in the presence of DTDs

The article investigates XML document specifications with DTDs and integrity constraints, such as keys and foreign keys. We study the consistency problem of checking whether a given specification is meaningful: that is, whether there exists an XML ...
The implication problem for 'closest node' functional dependencies in complete XML documents

With the growing use of XML as a format for the permanent storage of data, the study of functional dependencies in XML (XFDs) is of fundamental importance in a number of areas such as understanding how to effectively design XML databases without ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2007

328 pages

ISBN:9781595936851

DOI:10.1145/1265530

General Chair:
Phokion Kolaitis
IBM Almaden
,
Program Chair:
Leonid Libkin
University of Edinburgh

Copyright © 2007 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS07

Sponsor:

SIGMOD/PODS07: International Conference on Management of Data

June 11 - 13, 2007

Beijing, China

Acceptance Rates

PODS '07 Paper Acceptance Rate 28 of 187 submissions, 15%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
327
Total Downloads

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

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

David CGheerbrant ALibkin LMartens W(2013)Containment of pattern-based queries over data treesProceedings of the 16th International Conference on Database Theory10.1145/2448496.2448521(201-212)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2448496.2448521
Yan LMa ZZhang FYan LMa ZZhang F(2013)Fuzzy XML ReasoningFuzzy XML Data Management10.1007/978-3-642-44899-7_7(169-208)Online publication date: 26-Nov-2013
https://doi.org/10.1007/978-3-642-44899-7_7
Gheerbrant ALibkin LSirangelo C(2013)Reasoning about pattern-based XML queriesProceedings of the 7th international conference on Web Reasoning and Rule Systems10.1007/978-3-642-39666-3_2(4-18)Online publication date: 27-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39666-3_2
Moore N(2011)Computational complexity of the problem of tree generation under fine-grained access control policiesInformation and Computation10.1016/j.ic.2010.11.019209:3(548-567)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.ic.2010.11.019
Fan WGao HJia XLi JMa S(2011)Dynamic constraints for record matchingThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-010-0206-620:4(495-520)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1007/s00778-010-0206-6
Cautis BAbiteboul SMilo T(2009)Reasoning about XML update constraintsJournal of Computer and System Sciences10.1016/j.jcss.2009.02.00175:6(336-358)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.jcss.2009.02.001
Moore N(2009)The Halting Problem and Undecidability of Document Generation under Access Control for Tree UpdatesProceedings of the 3rd International Conference on Language and Automata Theory and Applications10.1007/978-3-642-00982-2_51(601-613)Online publication date: 31-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-00982-2_51
Bravo LCheney JFundulaki I(2007)Repairing inconsistent XML write-access control policiesProceedings of the 11th international conference on Database programming languages10.5555/1783534.1783545(97-111)Online publication date: 23-Sep-2007
https://dl.acm.org/doi/10.5555/1783534.1783545
Bravo LCheney JFundulaki I(2007)Repairing Inconsistent XML Write-Access Control PoliciesDatabase Programming Languages10.1007/978-3-540-75987-4_7(97-111)Online publication date: 2007
https://doi.org/10.1007/978-3-540-75987-4_7

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