Incremental validation of XML documents
Authors:
Open Access
- 12 December 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 29 (4) , 710-751
Abstract
We investigate the incremental validation of XML documents with respect to DTDs, specialized DTDs, and XML Schemas, under updates consisting of element tag renamings, insertions, and deletions. DTDs are modeled as extended context-free grammars. "Specialized DTDs" allow the decoupling of element types from element tags. XML Schemas are abstracted as specialized DTDs with limitations on the type assignment. For DTDs and XML Schemas, we exhibit an O ( m log n ) incremental validation algorithm using an auxiliary structure of size O ( n ), where n is the size of the document and m the number of updates. The algorithm does not handle the incremental validation of XML Schema wrt renaming of internal nodes, which is handled by the specialized DTDs incremental validation algorithm. For specialized DTDs, we provide an O ( m log 2 n ) incremental algorithm, again using an auxiliary structure of size O ( n ). This is a significant improvement over brute-force re-validation from scratch.We exhibit a restricted class of DTDs called local that arise commonly in practice and for which incremental validation can be done in practically constant time by maintaining only a list of counters. We present implementations of both general incremental validation and local validation on an XML database built on top of a relational database.Our experimentation includes a study of the applicability of local validation in practice, results on the calibration of parameters of the auxiliary data structure, and results on the performance comparison between the general incremental validation technique, the local validation technique, and brute-force validation from scratch.Keywords
This publication has 14 references indexed in Scilit:
- Storing and querying XML data using denormalized relational databasesThe VLDB Journal, 2005
- DTD inference for views of XML data2000
- Efficient and flexible incremental parsingACM Transactions on Programming Languages and Systems, 1998
- Your mediators need data conversion!ACM SIGMOD Record, 1998
- One-Unambiguous Regular LanguagesInformation and Computation, 1998
- Dyn-FO: A Parallel, Dynamic Complexity ClassJournal of Computer and System Sciences, 1997
- Complexity models for incremental computationTheoretical Computer Science, 1994
- Incremental recursive descent parsingComputer Languages, 1990
- Building friendly parsers1982
- Augmenting Parsers to Support IncrementalityJournal of the ACM, 1980