Über das Produkt
This is the first book to provide a solid theoretical account of the foundation of the popular data format XML. Exercises and examples of code fragments are included throughout to enhance understanding. This book is ideal for both students and researchers.
Kurzbeschreibung
This is the first book that provides a solid theoretical account of the foundation of the popular data format XML. Part I establishes basic concepts, starting with schemas, tree automata and pattern matching, and concluding with static typechecking for XML as a highlight of the book. In Part II, the author turns his attention to more advanced topics, including efficient 'on-the-fly' tree automata algorithms, path- and logic-based queries, tree transformation, and exact typechecking. The author provides many examples of code fragments to illustrate features, and exercises to enhance understanding. Thus the book will be ideal for students and researchers whether just beginning, or experienced in XML research.
Author(s): Haruo Hosoya
Publisher: Cambridge University Press
Year: 2010
Language: English
Pages: 240
Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 13
1.1 Documents, schemas, and schema languages......Page 15
1.2 Brief history......Page 16
1.3.1 Topics......Page 17
1.3.2 Organization......Page 20
2.1 Regular expressions......Page 23
2.2 String automata......Page 26
I Basic topics......Page 31
3.1 Data model......Page 33
3.2 Schema model......Page 36
3.3 Classes of schemas......Page 41
3.4 Bibliographic notes......Page 43
4.1.1 Trees......Page 44
4.1.2 Tree automata......Page 46
4.1.3 Tree automata with epsilon-transitions......Page 49
4.2 Relationship with the schema model......Page 50
4.3 Determinism......Page 53
4.3.1 Top-down determinism......Page 54
4.3.2 Bottom-up determinism......Page 55
4.4.1 Union, intersection, and complementation......Page 57
4.4.2 Emptiness test......Page 59
4.4.3 Applications......Page 60
4.4.4 Useless-state elimination......Page 61
4.5 Bibliographic notes......Page 62
5.1 From schemas to patterns......Page 63
5.2 Ambiguity......Page 64
5.2.1 All-matches semantics......Page 65
5.2.2 Single-match semantics......Page 67
5.3 Linearity......Page 68
5.4 Formalization......Page 70
5.4.1 Simple semantics......Page 71
5.4.2 Greedy-match semantics......Page 73
5.5 Bibliographic notes......Page 75
6.1 Definitions......Page 77
6.2 Construction......Page 80
6.3 Sequence-marking tree automata......Page 83
6.4 Bibliographic notes......Page 84
7.1 Compact taxonomy......Page 85
7.1.2 Approximate typechecking......Page 86
7.2 Case study: muXDuce type system......Page 87
7.2.1 Syntax and semantics......Page 88
7.2.2 Typing rules......Page 90
7.2.3 Correctness......Page 94
7.3.1 Algorithm......Page 96
7.3.2 Non-tail variables......Page 102
7.4 Bibliographic notes......Page 104
II Advanced topics......Page 105
8.1 Membership algorithms......Page 107
8.1.1 Top-down algorithm......Page 108
8.1.2 Bottom-up algorithm......Page 109
8.1.3 Bottom-up algorithm with top-down filtering......Page 111
8.2.1 Top-down algorithm......Page 113
8.2.2 Bottom-up algorithm......Page 115
8.3.1 Bottom-up algorithm......Page 122
8.3.2 Top-down algorithm......Page 123
8.4 Bibliographic notes......Page 130
9.1 Definitions......Page 131
9.2.1 Conversion to nondeterministic tree automata......Page 134
9.2.2 Conversion to bottom-up deterministic tree automata......Page 135
9.3 Basic set operations......Page 136
9.3.1 Membership......Page 137
9.3.2 Complementation......Page 138
9.3.3 Emptiness test......Page 139
9.4 Bibliographic notes......Page 140
10.1 Top-down tree transducers......Page 141
10.2 Height property......Page 144
10.3 Macro tree transducers......Page 145
10.4 Bibliographic notes......Page 149
11.1 Motivation......Page 152
11.2 Forward type inference: limitation......Page 154
11.3 Backward type inference......Page 155
11.4 Bibliographic notes......Page 161
12.1 Path expressions......Page 162
12.1.1 XPath......Page 163
12.1.2 Caterpillar expressions......Page 164
12.2.1 Definitions......Page 166
12.2.2 Expressiveness......Page 167
12.2.3 Variations......Page 173
12.3 Bibliographic notes......Page 174
13.1 First-order logic......Page 175
13.2 Monadic second-order logic......Page 179
13.3.1 Canonicalization......Page 182
13.3.2 Automata construction......Page 184
13.4 Bibliographic notes......Page 188
14.1.1 Definitions......Page 190
14.1.2 Glushkov automata and star normal form......Page 193
14.1.3 Ambiguity checking for automata......Page 198
14.2.1 Definitions......Page 200
14.2.2 Algorithm for checking marking ambiguity......Page 201
14.3 Bibliographic notes......Page 202
15.1 Attributes......Page 204
15.2 Shuffle expressions......Page 208
15.3 Algorithmic techniques......Page 210
15.4 Bibliographic notes......Page 211
Appendix: Solutions to selected exercises......Page 213
References......Page 232
Index......Page 237
