Name
Abstract | ||
|---|---|---|
We discuss incremental validation of XML documentswith respect to DTDs and XML Schema definitions. We considerinsertions and deletions of subtrees, as opposed to leafnodes only, and we also consider the validation of ID andIDREF attributes. For arbitrary schemas, we give a worst-casen log n time and linear space algorithm, and showthat it often is far superior to revalidation from scratch. Wepresent two classes of schemas, which capture most real-lifeDTDs, and show that they admit a logarithmic timeincremental validation algorithm that, in many cases, requiresonly constant auxiliary space. We then discuss animplementation of these algorithms that is independent of,and can be customized for different storage mechanismsfor XML. Finally, we present extensive experimental resultsshowing that our approach is highly efficient and scalable. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/ICDE.2004.1320036 | ICDE |
Keywords | Field | DocType |
XML,computational complexity,formal specification,formal verification,tree data structures,ID attribute,IDREF attribute,XML schema definition,arbitrary schema,constant auxiliary space,incremental XML document validation,leaf node,linear space algorithm,logarithmic time incremental validation algorithm,storage mechanism,subtree | Data mining,Efficient XML Interchange,Streaming XML,Computer science,XML validation,Document Structure Description,XML database,Theoretical computer science,RELAX NG,XML schema,Database,XML Schema Editor | Conference |
ISSN | ISBN | Citations |
1063-6382 | 0-7695-2065-0 | 41 |
PageRank | References | Authors |
1.79 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Denilson Barbosa | 1 | 610 | 43.52 |
| Alberto O. Mendelzon | 2 | 4848 | 1394.98 |
| Leonid Libkin | 3 | 3446 | 764.02 |
| Laurent Mignet | 4 | 345 | 29.41 |
| Marcelo Arenas | 5 | 2618 | 193.91 |