Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
396599 | Information Systems | 2009 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Dario Colazzo, Giorgio Ghelli, Carlo Sartiani,