1. A machine-implemented method for generating a type representation of an XMLType instance, comprising the steps of: generating within a volatile or a nonvolatile memory a XMLType type tree of nodes that represents a uniform abstraction of a type structure of the XMLType instance; wherein the XMLType type tree of nodes is generated based on the XMLType instance and a source of data type information about the XMLType instance; wherein the source of data type information is separate from the XMLType instance; determining data type information about said XMLType instance using the XMLType type tree of nodes without using the source of data type information about the XMLType instance; and rewriting a query using the data type information determined about the XMLType instance without using the source of data type information about the XMLType instance; wherein the step of generating a XMLType type tree of nodes includes generating a parent node of one or more children nodes, the parent node corresponding to either, an operator node that indicates how the one or more children nodes are grouped as a sequence, choice, or permutation, or an aggregate node with an aggregate quantifier set to indicate a cardinality restriction on the one or more children nodes; wherein the method is performed by one or more computing devices.