Build Engine¶

Summary¶

This chapter covers the build engine that reconstructs hierarchical data from flat relational tables -- the inverse of the flatten engine. You will learn about FK pre-indexing for efficient lookups, the inverse walk algorithm, the TreeBuilder class with its build and build-many methods, node construction via handler-based construct and class registry lookup, and child reassembly through inline and separate table rebuild strategies.

Concepts Covered¶

FK Pre Indexing
Inverse Walk Algorithm
TreeBuilder Class
Build Method
Build Many Method
Node Construction
Handler Based Construct
Class Registry Lookup
Child Reassembly
Inline Child Rebuild
Separate Table Rebuild

Prerequisites¶

Chapter 1: Foundation Concepts (Relational Tables, Foreign Keys, Hierarchical Data, Python Dataclasses)
Chapter 2: Spec Model (TreeSpec Dataclass, NodeSpec Dataclass, ChildSpec Dataclass)
Chapter 3: Flatten Engine (Tree Walk Algorithm, Inline Child Dispatch, Separate Table Dispatch)
Chapter 5: Schema Handling (SchemaHandler Protocol, SchemaHandlerRegistry)

Learning Objectives¶

After completing this chapter, you will be able to:

Explain how FK pre-indexing accelerates table-to-tree reconstruction
Trace the inverse walk algorithm as it rebuilds a tree from tables
Use the TreeBuilder to build a single tree or a collection
Describe handler-based construct and class registry lookup
Compare inline and separate table rebuild strategies

Introduction¶

The build engine is the inverse half of mountainash-treespec's bidirectional transformation. Where the flatten engine decomposes a tree into tables, the build engine reconstructs a tree from tables. This symmetry is what makes round-trip fidelity possible: flatten a tree, then build the tables back, and you should get the original tree.

Building is fundamentally more complex than flattening. During flattening, the tree structure guides traversal -- you simply follow the parent-child relationships that exist in the data. During building, those relationships exist only as column values in flat tables. The build engine must rediscover the tree structure by interpreting foreign key values, matching child rows to parent rows, and reconstructing typed dataclass instances from flat dictionaries.

This chapter covers the build engine from the ground up: pre-indexing for efficient FK lookups, the inverse walk algorithm, the TreeBuilder class and its entry points, construction strategies for turning row dictionaries into typed objects, and the two child reassembly modes.

FK Pre Indexing¶

Foreign key pre-indexing is an optimization that transforms the child row lookup from \( O(n) \) table scans to \( O(1) \) dictionary lookups. Before the build algorithm begins walking the tree, the pre_index_tables function groups rows in each child table by their FK column values.

The function accepts two inputs: the raw tables dictionary and an FK map that describes which column(s) link each child table to its parent. For each child table, it builds a dictionary keyed by FK value (or tuple of values for composite keys) with lists of matching rows as values.

def pre_index_tables(
    tables: dict[str, list[dict[str, Any]]],
    fk_map: dict[str, Union[str, list[str]]],
) -> dict[str, dict[Any, list[dict[str, Any]]]]:
    indexed = {}
    for table_name, join_key in fk_map.items():
        rows = tables.get(table_name, [])
        groups = defaultdict(list)
        if isinstance(join_key, list):
            for row in rows:
                key = tuple(row.get(k) for k in join_key)
                groups[key].append(row)
        else:
            for row in rows:
                groups[row.get(join_key)].append(row)
        indexed[table_name] = dict(groups)
    return indexed

The FK map itself is collected by TreeBuilder._collect_fk_map, which walks the spec to find all parent-child table relationships. The resolution order for each child is: explicit join_key on the ChildSpec, then the parent's primary_key as a fallback.

Without pre-indexing, finding the encounters for patient "P001" would require scanning every row in the encounters table. With pre-indexing, the lookup is indexed["encounters"]["P001"] -- a single dictionary access regardless of table size.

Operation	Without pre-indexing	With pre-indexing
Find children for one parent	\( O(n) \) table scan	\( O(1) \) dict lookup
Build 100 parents with 10 children each	\( O(100 \times 1000) \)	\( O(100) \)
Memory overhead	None	One dict per child table

Class Registry Lookup¶

The class registry is a dictionary mapping node names (strings matching the keys in TreeSpec.nodes) to Python class objects. The build engine uses this registry to determine which class to instantiate for each node it encounters during the inverse walk.

class_registry = {
    "Patient": Patient,
    "Encounter": Encounter,
    "Diagnosis": Diagnosis,
}

The registry is required for building (unlike flattening, where it is optional). Without it, the builder has no way to know what type of object to create from a row dictionary. The _build_node method raises a ValueError if a node name has no registered class.

The registry lookup is simple by design. The builder calls self._class_registry.get(node_name) and expects to receive a type object. This type object is then passed to the construction logic (handler-based construct or direct instantiation).

Handler Based Construct¶

Handler-based construction delegates object creation to the registered SchemaHandler rather than calling the class constructor directly. This indirection is necessary because different data formats have different construction requirements.

The _construct method on TreeBuilder implements this delegation:

def _construct(self, cls: type, kwargs: dict[str, Any]) -> Any:
    try:
        handler = self._handler_registry.get_handler(cls)
        return handler.construct(cls, kwargs)
    except Exception:
        return cls(**kwargs)

The method first tries to find a handler for the class and use its construct method. If no handler is available or construction fails, it falls back to direct cls(**kwargs) instantiation.

This fallback behavior is important for robustness. Handler-based construction can fail for various reasons: the handler might not support certain keyword combinations, the class might have non-standard constructor behavior, or the handler might not be installed. The direct fallback ensures that standard dataclasses always work even without a handler.

Different handlers implement construct differently:

DataclassSchemaHandler calls cls(**kwargs) directly
PydanticSchemaHandler uses Pydantic's model construction with validation
ProtobufSchemaHandler creates a Message instance and sets fields individually (protobuf constructors differ from Python kwargs conventions)
XsdataSchemaHandler handles xsdata-specific initialization patterns

Diagram: Build Engine Data Flow¶

Build Engine Data Flow

Type: workflow sim-id: build-engine-data-flow
Library: vis-network
Status: Specified

Purpose: Visualize the complete data flow through the build engine: tables enter, FK pre-indexing groups rows, the inverse walk assembles nodes bottom-up, and typed objects emerge.

Components:

Input: flat tables (patients, encounters, diagnoses) as table visualizations
Pre-indexing stage: tables reorganized into FK-grouped dictionaries
Inverse walk: tree being assembled node-by-node from leaf to root
Output: complete tree of typed dataclass instances
Arrows showing data flow between stages

Interactions: Step through the build process one node at a time. Click any table row to see which tree node it becomes. Toggle between "table view" and "index view" to see the pre-indexing transformation.

Learning Objective: (Apply, Bloom Level 3) Students can trace how flat table rows are assembled into a typed tree through the build engine's pipeline.

Node Construction¶

Node construction is the process of converting a flat row dictionary into a typed object with correctly populated fields and children. The _build_node method orchestrates this for each node in the tree.

The construction process has five phases:

Class lookup -- Retrieve the Python class from the registry
Own field extraction -- Extract scalar field values from the row (the inverse of the flattener's field extraction)
Null suppression check -- If all scalar fields are None and no children exist, return None instead of creating an empty object
Child reassembly -- For each child in the NodeSpec, rebuild the child using the appropriate strategy (inline, separate table, or routing)
Object construction -- Pass the assembled field dictionary to the handler-based construct method

The own-field extraction (_extract_own_fields) reverses the flattener's field mapping. For explicit field mappings, it inverts the {src: col} dictionary to {col: src} and reads values from the row using column names but stores them using field names. For auto-mapped fields, it reads from the row using the snake_case column name and stores using the original field name.

The null suppression check prevents phantom objects. When an optional child was absent during flattening, its table may contain a row with all-None values (if the flattener did not skip it). Without null suppression, the builder would create an empty object with all-None fields. The check catches this case and returns None instead, restoring the original absent-child semantics.

Inverse Walk Algorithm¶

The inverse walk algorithm is the recursive core of the build engine. Unlike the flatten engine's depth-first tree walk (which follows the existing tree structure), the inverse walk constructs the tree structure by reading from pre-indexed tables and the spec.

The algorithm's recursion follows the spec's node hierarchy. Starting from the root node's first row, it extracts scalar fields, then for each declared child relationship, it looks up matching rows in the child table (using the pre-indexed FK groups) and recursively builds child objects. The children are attached to the parent's field dictionary before construction.

The inverse walk handles the same three dispatch modes as the flatten engine:

Inline rebuild -- Reads prefixed columns from the parent row and constructs the child object from them
Separate table rebuild -- Looks up child rows by FK value in the pre-indexed tables
Routing rebuild -- Looks up rows from multiple target tables and pivot columns, merging them into a single child list

The key difference from the forward walk is directionality. The flatten walk starts at the root and pushes data down into tables. The inverse walk starts at the root row and pulls data up from child tables, constructing the tree bottom-up despite traversing top-down.

TreeBuilder Class¶

The TreeBuilder class is the public API for the build engine. It mirrors the TreeFlattener interface: construct with a spec, class registry, and optional hooks/settings, then call build or build_batch to perform the transformation.

class TreeBuilder:
    def __init__(
        self,
        spec: TreeSpec,
        hooks: Optional[HookRegistry] = None,
        settings: Optional[dict[str, Any]] = None,
        class_registry: Optional[dict[str, type]] = None,
        handler_registry: Optional[SchemaHandlerRegistry] = None,
    ):

The constructor accepts a handler_registry parameter that the TreeFlattener does not. This is because the builder uses handler-based construction to create typed objects, which requires access to the registry to find the appropriate handler for each class.

Internal state includes the pre-indexed tables (_indexed), the raw tables (_tables), and the FK map. These are populated at the start of each build or build_batch call and reset between calls.

Build Method¶

The build method reconstructs a single root object from a set of flat tables. It is the inverse of TreeFlattener.flatten.

def build(self, tables: dict[str, list[dict[str, Any]]]) -> Any:
    root_spec = self._spec.root_node
    if root_spec.table is None:
        raise ValueError("Root node must have a table")
    root_rows = tables.get(root_spec.table, [])
    if not root_rows:
        return None

    fk_map = self._collect_fk_map(self._spec)
    self._tables = tables
    self._indexed = pre_index_tables(tables, fk_map)

    return self._build_node(
        self._spec.meta.root_element,
        root_spec,
        root_rows[0],
        parent_key_value=None,
    )

The method takes the first row from the root table and builds a complete tree from it. If the root table is empty, it returns None. If the root table has multiple rows, only the first is used -- for multi-root building, use build_batch.

Build Many Method¶

The build_batch method (named to avoid confusion with flatten_many) reconstructs multiple root objects, one per row in the root table. This is the inverse of flatten_many.

Build batch adds an important safety check: if there are multiple root rows and any separate-table child relies on synthetic keys (no explicit join_key or primary_key), it raises a ValueError. Synthetic keys cannot partition children across multiple roots because the integer counter has no inherent association with any particular root.

def build_batch(self, tables: dict[str, list[dict[str, Any]]]) -> list[Any]:
    root_spec = self._spec.root_node
    root_rows = tables.get(root_spec.table, [])
    if len(root_rows) > 1:
        self._check_batch_join_keys()  # Raises if synthetic keys detected
    ...

The check iterates through all separate-table and routed children in the spec. Any child without either an explicit join_key or a parent primary_key triggers the error with a helpful message explaining the requirement.

Child Reassembly¶

Child reassembly is the umbrella term for the three strategies the builder uses to reconstruct child objects from flat table data. Each strategy mirrors one of the flattener's dispatch modes.

The builder selects the strategy based on the same ChildSpec flags:

child_spec.is_inline -> Inline Child Rebuild
child_spec.is_separate_table -> Separate Table Rebuild
child_spec.routing -> Routing Rebuild (combines separate table and pivot)

For each child in a NodeSpec's children dictionary, the builder evaluates condition hooks (if present), then delegates to the appropriate rebuild method. The rebuilt child (or list of children) is stored in the parent's field dictionary before the parent object is constructed.

Diagram: Child Reassembly Decision Flow¶

Child Reassembly Decision Flow

Type: microsim sim-id: child-reassembly-flow
Library: p5.js
Status: Specified

Purpose: Step-through animation showing how the builder reassembles children using each of the three strategies, with a side-by-side comparison of the flat table input and the reconstructed tree output.

Components:

Left: flat tables with highlighted rows showing which rows become which children
Center: decision flowchart showing inline/separate/routing selection
Right: tree being assembled with children attaching to parents
Controls: step forward, step back, reset, auto-play

Interactions: Click a table row to see where it ends up in the tree. Toggle between strategies to compare how the same data is processed differently. Adjust the tree depth to see deeper nesting.

Learning Objective: (Apply, Bloom Level 3) Students can trace how each child reassembly strategy reconstructs children from flat table rows.

Inline Child Rebuild¶

Inline child rebuild reconstructs a child object from prefixed columns in the parent row. This is the inverse of the flattener's inline dispatch, which merged the child's fields into the parent row with a prefix.

The _build_inline method works as follows:

Look up the child class from the registry
Determine the prefix from ChildSpec.effective_prefix
For each field on the child class (from resolved_fields or dataclass introspection), read the value from the parent row using prefixed_name(prefix, field_col)
Recursively rebuild the child's own children (supporting nested inline and mixed inline/separate grandchildren)
Check if all extracted values are None -- if so, return None (the child was absent)
Construct the child object using handler-based construct

The method creates a "virtual row" for the inline child by combining the extracted child fields with the parent row's remaining columns. This virtual row enables grandchild FK lookups when an inline child has separate-table grandchildren -- the grandchild's FK might reference a column that exists at the parent level rather than the child level.

child_virtual_row = dict(child_fields)
for k, v in row.items():
    if k not in child_virtual_row:
        child_virtual_row[k] = v

This virtual row merging is a subtle but critical detail for correct reconstruction of trees with mixed inline and separate-table nesting.

Separate Table Rebuild¶

Separate table rebuild reconstructs children by looking up matching rows in the child's dedicated table using FK values. The _build_separate method handles this for both explicit FK-based lookup and synthetic key fallback.

The lookup priority chain:

Explicit join_key on the ChildSpec -- used for FK lookup in the pre-indexed tables
Parent primary_key as fallback FK -- used when no explicit join_key is declared
No FK available (synthetic keys) -- falls back to taking all rows from the child table

For each matching child row, the builder recursively calls _build_node to construct the child object, which in turn rebuilds that child's own children. The results are collected into a list.

The method then applies cardinality semantics:

For cardinality: "one" -- returns the first child object (or None if empty)
For cardinality: "many" -- returns the full list

The wrapper pattern adds an additional layer. When ChildSpec.wrapper is True, the builder creates an instance of the wrapper class (which must be default-constructible) and sets the wrapper_attr to the list of children. This reconstructs container patterns where an intermediate object wraps the actual child list.

Complete Build Example¶

To illustrate the full build pipeline, consider reconstructing a patient tree from flattened tables:

from mountainash_treespec.core.build.builder import TreeBuilder
from mountainash_treespec.core.spec.loader import load_spec_from_dict

tables = {
    "patients": [
        {"patient_id": "P001", "name": "Alice", "addr_city": "Melbourne"}
    ],
    "encounters": [
        {"patient_id": "P001", "encounter_date": "2024-01-15", "type": "outpatient"},
        {"patient_id": "P001", "encounter_date": "2024-03-22", "type": "inpatient"},
    ],
}

builder = TreeBuilder(spec, class_registry=class_registry)
patient = builder.build(tables)
# patient.name == "Alice"
# patient.address.city == "Melbourne"  (rebuilt from inline addr_ columns)
# len(patient.encounters) == 2  (rebuilt from FK lookup)

The builder reads the single patient row, extracts scalar fields, rebuilds the inline address from addr_-prefixed columns, looks up encounters by patient_id in the pre-indexed encounters table, constructs each encounter, and finally constructs the patient with all fields and children populated.

Key Takeaways¶

FK pre-indexing transforms child row lookup from \( O(n) \) scans to \( O(1) \) dictionary lookups, essential for performance on large datasets.
The inverse walk algorithm constructs the tree top-down by pulling data from pre-indexed child tables, the mirror of the flatten engine's depth-first push.
The TreeBuilder provides build (single root) and build_batch (multi-root) entry points, with build_batch requiring explicit join keys.
Class registry lookup maps node names to Python types; the registry is required for building.
Handler-based construct delegates object creation to format-specific handlers, with a direct cls(**kwargs) fallback for standard dataclasses.
Node construction extracts own fields, suppresses all-None phantom nodes, assembles children, and constructs the typed object.
Inline child rebuild reads prefixed columns from the parent row and creates a virtual row for grandchild lookups.
Separate table rebuild uses pre-indexed FK lookups to find matching child rows, with cardinality-based result shaping.