Regardless of whether Trees are managed by ATG services, application Trees generally have three common representations, and these representations conform directly to specific tables in the underlying database schema of the application:
Parent-Child–The normalized, canonical representation of a Tree, as a directed graph of nodes, where each node represents some value of the underlying data source. A node may have multiple child nodes (unless it is a leaf node) and usually at most one parent node (unless it happens to be the root node). Nodes may be labeled by depth or by level, generally supporting the specification of value-based or level-based hierarchies, respectively. In the application database schema, a parent-child table, or node table, directly stores this canonical representation of the Tree. An example of a parent-child representation of a tree is the following hierarchy: Corporation , Sales Division, Region.
Row-Flattened–A physically optimized but semantically equivalent transformation of the parent-child structure into a tabular form, where each row represents a node, along with precisely one descendant of that node. One such row exists for each unique node-descendant pair, and a Tree of any arbitrary depth can always be accommodated by adding more rows. Row-flattened representation optimizes certain kinds of searches–for example, retrieving the entire subtree rooted at some specified node. In the underlying application database schema, a row-flattened table stores the row-flattened equivalent of the parent-child table content. Usually, some asynchronous process is relied upon to read the content of a parent-child table and transform and load it into a corresponding row-flattened table. A row-flattened representation of the previous parent-child tree would consist of the following rows with child and ancestor columns:
Sales Division, Corporation
Region, Sales Division
Region, Corporation
Column-Flattened–A physically optimized but semantically equivalent transformation of the parent-child structure into a tabular form, where each row represents a node, along with all ancestors of that node, up to and including the root node of the Tree. One such row exists for each node of the Tree, and the table requires a unique column corresponding to each depth (or level) of the Tree. A Tree of any arbitrary depth can always be accommodated by adding more columns (however, for obvious practical reasons, the number of columns is usually specified and fixed by the table definition). Column-flattened representation optimizes certain kinds of searches–for example, determining the complete rollup structure for some specified node. In the underlying application database schema, a column-flattened table stores the column-flattened equivalent of the parent-child table content. And as with row-flattened representations, some asynchronous process is likewise usually employed to transform the content of a parent-child table and load it into a corresponding column-flattened table. A column-flattened representation of the previous parent-child tree would consist of the following rows with a column for each distinct level of the tree:
Corporation, Corporation, Corporation
Sales Division, Sales Division, Corporation
Region, Sales Division, Corporation