Name
Abstract | ||
|---|---|---|
Inclusion between XML types is important but expensive, and is much more expensive when unordered types are considered. We prove here that inclusion for XML types with interleaving and counting can be decided in polynomial time in the presence of two important restrictions: no element appears twice in the same content model, and Kleene star is only applied to disjunctions of single elements. Our approach is based on the transformation of each such content model into a set of constraints that completely characterizes the generated language. We then reduce inclusion checking to constraint implication. We exhibit a quadratic algorithm to perform inclusion checking on a RAM machine. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.is.2008.10.001 | Inf. Syst. |
Keywords | Field | DocType |
important restriction,constraint implication,content model,polynomial time,kleene star,single element,xml type,inclusion checking,quadratic algorithm,efficient inclusion,ram machine,regular expressions,xml schema,regular expression,xml,subtyping | Regular expression,Kleene star,XML,Computer science,Empty string,XML validation,Theoretical computer science,XML schema,Time complexity,Database,Interleaving | Journal |
Volume | Issue | ISSN |
34 | 7 | Information Systems |
Citations | PageRank | References |
19 | 0.78 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dario Colazzo | 1 | 283 | 34.21 |
| Giorgio Ghelli | 2 | 1300 | 255.19 |
| Carlo Sartiani | 3 | 240 | 28.54 |