Loading...
Please wait, while we are loading the content...
Similar Documents
Streaming XML Schema Validation for Relational Tree Encodings
| Content Provider | Semantic Scholar |
|---|---|
| Author | Klinger, Stefan |
| Copyright Year | 2004 |
| Abstract | This diploma thesis, as well as the implementation of the proposed algorithm on the enclosed CD, are available online through the Konstanzer Online-Publikations-System (KOPS), following the permanent direct URL Urhebervermerk Ich versichere, daß ich die vorliegende Arbeit selbständig angefertigt habe und nur die angegebenen Hilfsmittel und Quellen verwendet wurden. Preface This diploma thesis introduces a new way of validating relationally encoded XML documents against XML Schema descriptions. Validation is the process of verifying whether the given document respects a certain structure, and, given that, annotating each document node with the name of its type. An enumeration of the nodes of the XML document tree is used as relational tree encoding. More precisely, during a left-to-right depth-first traversal of the tree, the nodes are annotated with the according pre order and post order indices. This pre/post enumeration was introduced by [5]. An XML Schema [15] description is considered to define a context free grammar. Since not all aspects of XML Schema can be expressed by a context free grammar, this thesis' focus is on the according XML Schema subset. The proposed algorithm is based on the concept of deriving a regular expression, which was introduced by [1]. Hence, it is neither necessary to reconstruct the XML tree from its encoding, nor to build a finite state automaton from the XML Schema description. Moreover, the encoded tree is read as a stream, i.e., exactly once, sequentially in document order. This thesis introduces guards, an amelioration of regular expressions which integrates information about the hierarchical structure of trees. The concept of derivation is augmented to make use of the pre/post enumeration and the enriched regular expressions. For one-unambiguous grammars possessing the star normal form, this leads to an algorithm with linear time and space requirements. All grammars induced by XML Schema descriptions are one-unambiguous. However , if star normal form cannot be guaranteed, its absence may lead to exponential time and space requirements in the worst case. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://kops.uni-konstanz.de/bitstream/handle/123456789/6349/text.pdf?isAllowed=y&sequence=2 |
| Alternate Webpage(s) | https://kops.uni-konstanz.de/bitstream/handle/123456789/6349/text.pdf?isAllowed=y&sequence=2 |
| Alternate Webpage(s) | http://www-db.informatik.uni-tuebingen.de/files/research/pathfinder/publications/streaming-schema-validation.pdf |
| Alternate Webpage(s) | http://www.stefan-klinger.de/files/da2004.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
