Efficient inclusion for a class of XML types with interleaving and counting |
| |
Authors: | Dario Colazzo Giorgio Ghelli Carlo Sartiani |
| |
Affiliation: | 1. UMR CNRS 8623, Université Paris Sud, Orsay F-91405, France;2. Dipartimento di Informatica, Università di Pisa, Italy |
| |
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. |
| |
Keywords: | XML Regular expressions Subtyping XML Schema |
本文献已被 ScienceDirect 等数据库收录! |