Overview
An XML tree is the conceptual hierarchical structure that underlies every well-formed XML document. XML documents can be modeled as ordered, labeled trees, with a document node or root element serving as the root of the tree. This tree structure is fundamental to how XML data is parsed, queried, and processed.
Conceptual Foundation
The W3C describes an XML document as "a linearization of a tree structure." At every node in the tree there are several character strings; the tree structure and the character strings together form the information content of an XML document. The main structure of an XML document is tree-like, and most of the lexical structure is devoted to defining that tree.
The XML 1.0 specification (W3C Recommendation) defines that a well-formed XML document must contain exactly one root element (called the document element) that contains all other elements, and that elements must be properly nested. These constraints directly produce a tree structure: there is a single root node, and elements form parent-child relationships with proper nesting.
Node Types
According to the W3C's XML data model, an XML tree can contain several different types of nodes:
- Document node (root): A specialized node representing the document itself. It has a type but no attributes, and optionally a URL.
- Element nodes: Created by start-tag/end-tag pairs or empty-element tags. Each element node has a type (name), an ordered list of children, and a set of attributes (unordered name-value pairs).
- Attribute nodes: Name-value pairs associated with element nodes. Unlike children, attributes have no defined order.
- Text (data) nodes: Character data content within elements.
- Processing instruction nodes: Instructions for applications, always leaf nodes.
- Comment nodes: Explanatory notes for human consumption, always leaf nodes.
Standard Data Models
Two standard terminologies have been released by the W3C for describing XML trees:
XPath Data Model (XDM)
Defined in the XQuery 1.0 and XPath 2.0 Data Model (XDM) specification, this model defines:
- Instance: The data model represented as a sequence.
- Sequence: An ordered collection of zero or more items.
- Node: Any item represented in the XML tree/sequence.
- Root Node: The topmost element of the tree.
- Element: A node within the sequence that may contain children.
- Document order: The order in which nodes appear in a pre-order traversal of the document tree. The root node is first, every node occurs before all its children and descendants, and namespace nodes and attribute nodes immediately follow their associated element node.
XML Information Set (Infoset)
Defined in the W3C Recommendation "XML Information Set (Second Edition)," this describes an abstract data model for XML documents in terms of information items. An information set can contain up to eleven different types of information items:
- 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
- Document Type Declaration Information Item
- Unparsed Entity Information Items
- Notation Information Items
- Namespace Information Items
Key Structural Relationships
As described in the W3C document "The Tree Structure of XML Queries" (1999), the fundamental relationships among nodes in an XML tree are:
- Dominates: Node A dominates node B if node B is found in the subtree of which node A is the root (ancestor/descendant relationship).
- Immediately Dominates: The parent/child relationship.
- Precedes: Node A precedes node B if A occurs before B in document order.
- Immediately Precedes: The direct sibling ordering relationship.
These relationships define two axes: hierarchy (dominance) and sequence (order), which together can locate any node in a document.
Representation as Trees
XML documents can be represented graphically as tree diagrams. For example, the XML document:
<Product>
<Name>Widget</Name>
<Details>
<Description>This Widget is the highest quality widget.</Description>
<Price>5.50</Price>
</Details>
</Product>
Corresponds to the tree:
Product
├─── Name
└─── Details
├─── Description
└─── Price
Programming Interfaces
Document Object Model (DOM)
The DOM Core interfaces provide generic access to document content types. All DOM Core interfaces are derived from the Node interface, which provides a generic set of interfaces for accessing a document or document fragment's structure and content. The generic Node interface captures the minimal set of attributes and methods required to express the tree structure, including pointers to parent nodes, child nodes, and siblings.
libxml2
The libxml2 library (a widely used XML parsing library written in C) defines an XML tree through its xmlNode structure, which includes node type (element, attribute, text, etc.), name, content, children, parent, siblings, and namespace information. The library provides functions to build, modify, query, and serialize XML document trees.
XML Schema and Tree Structure
XML Schema (W3C Recommendation) defines an abstract data model for schemas that operates at the level of information items. Schema components include type definitions, element declarations, attribute declarations, and model groups. The schema-validity assessment process validates element and attribute information items against schema components and produces a post-schema-validation infoset (PSVI) that augments the original infoset with type information.
Links and Graphs
While the main structure of an XML document is tree-like, XML also provides a mechanism (via ID/IDREF attributes and XLink) to make connections between arbitrary nodes in the tree, creating graph-like relationships. For example, an element can have an href attribute pointing to another element with a matching id, creating a reference that is not constrained by the tree hierarchy.
