Expressiveness and Complexity of XML Schema

Martens, Neven, Schwentick, Bex

@article{martens:tods-2006,
  title={Expressiveness and Complexity of XML Schema},
  author={Martens, W. and Neven, F. and Schwentick, T. and Bex, G.J.},
  journal={{ACM} Transactions on Database Systems ({TODS})},
  volume={31},
  number={3},
  pages={813},
  year={2006},
  publisher={ACM}
}

DTDs correlates to local tree languages

XML Scheme, like Relax NG, adds a type language

• Including different types to the same element name

Relax NG correlates to unranked regular tree languages

XML Schema Element Declarations Consistent (EDC) constraint

• Prohibits two different types associated with some element name in same content model

XML Schema between DTDs and general tree automata

• Probably closer to DTDs

Very few practical schemas actually utilize expressiveness going beyond DTDs

• Only 15% do so
• Of that 15%, vast majority use simplest form of typing, based solely on parent context

XML Schema language is too complex for users to get more out of it?

Goal: 1-pass preorder typing---determine type of an element when opening tag is met

• XML Schema EDC and unique particular attribution constraints ensure this, but are not minimal necessary conditions

Regular expression associated with element name is its content model