التفاصيل البيبلوغرافية
| العنوان: |
Efficient Constraint Validation for Updated XML Databases. |
| المؤلفون: |
Bouchou, Béatrice, Cheriat, Ahmed, Ferrari, Mírian Halfeld, Laurent, Dominique, Lima, Maria Adriana, Musicante, Martin A. |
| المصدر: |
Informatica (03505596); Oct2007, Vol. 31 Issue 3, p285-309, 25p, 12 Diagrams, 7 Charts, 5 Graphs |
| مصطلحات موضوعية: |
XML (Extensible Markup Language), CONSTRAINT satisfaction, MACHINE theory, ALGORITHMS, DOCUMENT markup languages |
| مستخلص: |
XML constraints are either schema constraints representing rules about document structure (e.g. a DTD, an XML Schema definition or a specification in Relax-NG), or integrity constraints , which are rules about the values contained in documents (e.g. primary keys, foreign keys, etc.). We address the problem of incrementally verifying these constraints when documents are modified by updates. The structure of an XML document is a tree, whose nodes are element (or attribute) names and whose leaves are associated to values contained in the document. Considered updates are insertion, deletion or replacement of any subtree in the XML tree. Schema constraints are represented by tree automata and tree grammars. Key and foreign key constraints are represented by attribute grammars, adding semantic rules to schema grammars, to carry key and foreign key values (to verify their properties). Our incremental validation tests both schema and integrity constraints while treating the sequence of updates, in only one pass over the document. Only nodes involved in updates trigger validation tests. An analysis of complexity shows that worst cases are determined by the shape of the XML tree being processed (asymptotic upper bounds are presented). Experimental results show that our algorithms behave efficiently in practice. [ABSTRACT FROM AUTHOR] |
|
Copyright of Informatica (03505596) is the property of Slovene Society Informatika and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Supplemental Index |
Full Text Finder