XML tree

XML documents have a hierarchical structure and can conceptually be interpreted as a tree structure, called an XML tree.

XML documents must contain a root element (one that is the parent of all other elements). All elements in an XML document can contain sub elements, text and attributes. The tree represented by an XML document starts at the root element and branches to the lowest level of elements. Although there is no consensus on the terminology used on XML Trees, at least two standard terminologies have been released by the W3C:

• The terminology used in the XPath Data Model
• The terminology used in the XML Information Set.

XPath defines a syntax named XPath expressions that identifies one or more internal components (elements, attributes, etc.) of an XML document. XPath is widely used to accesses XML-encoded data.

The XML Information Set, or XML infoset, describes an abstract data model for XML documents in terms of information items. It is often used in the specifications of XML languages, for its convenience in describing constraints on constructs those languages allow.

Representation as trees

In mathematics, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. Any connected graph without simple cycles is a tree. A tree data structure simulates a hierarchical tree structure with a set of linked nodes. A hierarchy consists of a preorder defined on a set. The term hierarchy is used to stress a hierarchical relation among the elements.

The XML specification defines an XML document as a well-formed text if it satisfies a list of syntax rules defined in the specification. This specification is long, however 2 key points relating to the tree structure of an XML document are:

• The begin, end, and empty-element tags that delimit the elements are correctly nested, with none missing and none overlapping
• A single "root" element contains all the other elements

These features resemble those of trees, in that there is a single root node, and an order to the elements. XML has appeared as a first-class data type in other languages. The JavaScript (E4X) extension explicitly defines two specific objects (XML and XMLList), which support XML document nodes and XML node lists as distinct objects and use a dot-notation specifying parent-child relationships. ^[1] These data structures represent XML documents as a tree structure.

XPath Data Model

XPath, the XML Path Language, is a query language for selecting nodes from an XML document. XPath defines a syntax named XPath expressions that can query an XML document for one or more internal components (elements, attributes, etc.). XPath is widely used in other core-XML specifications and in programming libraries for accessing XML-encoded data. ^[2]

XPath Data Model terminology

The XPath Data Model is a long specification, and goes into many features unrelated to XML trees. Listed below are key excerpts relating to XML tree terminology: "

• [Definition: Every instance of the data model is a sequence.]
• [Definition: A sequence is an ordered collection of zero or more items.] A sequence cannot be a member of a sequence. A single item appearing on its own is modeled as a sequence containing one item.
• [Definition: An item is either a node or an atomic value]
• [Definition: The topmost node of a tree is called the root node.]
• [Definition: A tree whose root node is a Document Node is referred to as a document.]
• [Definition: A tree whose root node is not a Document Node is referred to as a fragment.]
• [Definition: An atomic value is a value in the value space of an atomic type and is labeled with the name of that atomic type.]
• [Definition: An atomic type is a primitive simple type or a type derived by restriction from another atomic type.]
• [Definition: An expanded-QName is a set of three values consisting of a possibly empty prefix, a possibly empty namespace URI, and a local name.]

A document order is defined among all the nodes accessible during a given query or transformation. Document order is a total ordering. Informally, document order is the order in which nodes appear in the XML serialization of a document. Within a tree, document order satisfies the following constraints:

• The root node is the first node.
• Every node occurs before all of its children and descendants.
• Namespace Nodes immediately follow the Element Node with which they are associated. The relative order of Namespace Nodes is stable but implementation-dependent.
• Attribute Nodes immediately follow the Namespace Nodes of the element with which they are associated. If there are no Namespace Nodes associated with a given element, then the Attribute Nodes associated with that element immediately follow the element. The relative order of Attribute Nodes is stable but implementation-dependent.
• The relative order of siblings is the order in which they occur in the children property of their parent node.
• Children and descendants occur before following siblings."^[3]

XML Information Set

XML Information Set (XML Infoset) describes an abstract data model of an XML document in terms of a set of information items. The definitions in the XML Information Set specification are meant to be used in other specifications that need to refer to the information in a well-formed XML document. The infoset makes it convenient to describe constraints on the XML constructs other XML languages allow. An XML document has an information set if it is well-formed and satisfies the namespace constraints. An information set can contain up to eleven different types of information items:

• The Document Information Item (always present)
• Element Information Items
• Attribute Information Items
• Processing Instruction Information Items
• Unexpanded Entity Reference Information Items
• Character Information Items
• Comment Information Items
• The Document Type Declaration Information Item
• Unparsed Entity Information Items
• Notation Information Items
• Namespace Information Items ^[4]

XML Information Set terminology

The XML Information Set is a long specification, and goes into many features unrelated to XML trees. Listed below are the most important terms relating to XML tree terminology:

"There is exactly one document information item in the information set, and all other information items are accessible from the properties of the document information item, either directly or indirectly through the properties of other information items. The document information item has the following properties:

• [children]
• [document element]
• [notations]
• [unparsed entities]
• [base URI]
• [character encoding scheme]
• [standalone]
• [version]
• [all declarations processed]

There is an element information item for each element appearing in the XML document. One of the element information items is the value of the [document element] property of the document information item, corresponding to the root of the element tree, and all other element information items are accessible by recursively following its [children] property. An element information item has the following properties:

• [namespace name]
• [local name]
• [prefix]
• [children]
• [attributes]
• [namespace attributes]
• [in-scope namespaces]
• [base URI]
• [parent]

There is an attribute information item for each attribute (specified or defaulted) of each element in the document, including namespace declarations. The latter however appear as members of an element's [namespace attributes] property rather than its [attributes] property. Attributes declared in the DTD with no default value and not specified in the element's start tag are not represented by attribute information items. An attribute information item has the following properties:

• [namespace name]
• [local name]
• [prefix]
• [normalized value]
• [specified]
• [attribute type]
• [references]
• [owner element]^[5]

Notes