Skip to content

Flatten Engine

Summary

This chapter covers the flatten engine that transforms hierarchical data into relational tables. You will learn the tree walk algorithm, field extraction, key propagation, synthetic key generation, and column naming conventions (snake case, prefixed names). The chapter then introduces the TreeFlattener class with its flatten and flatten-many methods, and the three child dispatch modes: inline, separate table, and routed dispatch. Null handling strategy is also covered.

Concepts Covered

  • Tree Walk Algorithm
  • Field Extraction
  • Key Propagation
  • Synthetic Key Generation
  • Column Naming Convention
  • Snake Case Naming
  • Prefixed Name Builder
  • Null Handling Strategy
  • TreeFlattener Class
  • Flatten Method
  • Flatten Many Method
  • Inline Child Dispatch
  • Separate Table Dispatch
  • Routed Child Dispatch

Prerequisites

  • Chapter 1: Foundation Concepts (Hierarchical Data, Tree to Table Decomposition, Python Dataclasses, Primary Keys, Foreign Keys)
  • Chapter 2: Spec Model (TreeSpec Dataclass, NodeSpec Dataclass, ChildSpec Dataclass, SettingsConfig, RoutingConfig)

Learning Objectives

After completing this chapter, you will be able to:

  • Trace how the tree walk algorithm visits nodes depth-first
  • Explain how fields are extracted from dataclass instances
  • Describe key propagation and synthetic key generation
  • Apply column naming conventions including snake case and prefixed names
  • Use the TreeFlattener to flatten a single tree or a collection
  • Compare inline, separate table, and routed child dispatch modes
  • Configure null handling for optional fields

Introduction

The flatten engine is the forward half of mountainash-treespec's bidirectional transformation. Given a hierarchical data tree (a nested dataclass, a parsed XML document, a Protocol Buffer message) and a TreeSpec, the engine walks the tree depth-first and produces a dictionary of relational tables. Each table is a list of row dictionaries, ready for conversion to Polars DataFrames, PyArrow Tables, or Parquet files.

This chapter explains the engine from the inside out. We start with the low-level utilities (column naming, field extraction) that handle individual values, then build up to the tree walk algorithm that orchestrates the traversal, and finally cover the three child dispatch modes that determine how nested structures decompose into rows and tables.

Column Naming Convention

Before the flattener can produce table output, it needs a consistent strategy for converting Python field names into column names. The column naming convention, configured in SettingsConfig.column_naming, governs this transformation.

The current implementation supports one convention: "snake_case". This converts CamelCase and mixedCase identifiers into lowercase words separated by underscores. The conversion uses two regular expressions that insert underscores at appropriate boundaries.

The to_snake_case function handles several patterns:

  • PatientName becomes patient_name (standard CamelCase)
  • XMLParser becomes xml_parser (uppercase acronyms)
  • dateOfBirth becomes date_of_birth (mixedCase)
  • already_snake remains already_snake (no-op)

This convention is particularly important for xsdata-generated classes, where XML element names like GivenName or DateOfBirth need to become database-friendly column names.

Snake Case Naming

The snake case naming implementation is a two-pass regex approach. The first regex handles transitions between consecutive uppercase letters and an uppercase-lowercase pair (e.g., XML + Parser). The second regex handles transitions from a lowercase letter or digit to an uppercase letter (e.g., date + Of).

_CAMEL_RE1 = re.compile(r"([A-Z]+)([A-Z][a-z])")
_CAMEL_RE2 = re.compile(r"([a-z\d])([A-Z])")

def to_snake_case(name: str) -> str:
    s = _CAMEL_RE1.sub(r"\1_\2", name)
    s = _CAMEL_RE2.sub(r"\1_\2", s)
    return s.lower()

The two-pass approach is necessary because a single regex cannot correctly handle acronyms adjacent to regular words. Without the first pass, XMLParser would become xmlparser instead of xml_parser.

Prefixed Name Builder

When inline children merge their fields into the parent row, the prefixed name builder prevents column name collisions by prepending a prefix to each child field name. The prefixed_name function joins a prefix and a field name with an underscore separator.

The function handles edge cases cleanly:

  • If the prefix is empty or None, it returns the field name unchanged
  • If the field name is empty, it returns just the prefix
  • Otherwise it returns "{prefix}_{field_name}"
def prefixed_name(prefix: str | None, field_name: str) -> str:
    if not prefix:
        return field_name
    if not field_name:
        return prefix
    return f"{prefix}_{field_name}"

For nested inline children (an inline child that itself has inline children), the prefix composes. If a Patient has an inline Address (prefix addr) that itself has an inline GeoLocation (prefix geo), the GeoLocation's latitude field becomes addr_geo_latitude in the patient row.

Field Extraction

Field extraction is the process of reading scalar values from a tree node and converting them into a flat dictionary of column-name/value pairs. The _extract_fields method on TreeFlattener is the workhorse that handles this for every node visited during the tree walk.

The method supports three extraction strategies, tried in order of priority:

  1. Explicit field mapping -- When NodeSpec.field_mapping is a dictionary, only the listed fields are extracted with their mapped column names
  2. Resolved fields -- When the node has pre-computed resolved_fields (populated by derive_treespec), those fields are extracted by name with their pre-computed column names
  3. Fallback introspection -- For YAML-loaded specs without resolved fields, the method introspects the object directly (dict keys or dataclass fields), applying snake_case naming and skipping nested structures

The fallback strategy demonstrates a design principle: the flattener works even without pre-resolved metadata. It can flatten a plain Python dict against a YAML spec that has no class registry. This flexibility supports use cases where the data arrives as parsed JSON rather than typed dataclasses.

Diagram: Field Extraction Decision Tree

Field Extraction Decision Tree

Type: workflow sim-id: field-extraction-decision
Library: p5.js
Status: Specified

Purpose: Visualize the three-strategy priority chain for field extraction, showing how the flattener decides which extraction path to use based on NodeSpec configuration.

Components:

  • Decision flowchart: "Is field_mapping a dict?" -> "Are resolved_fields populated?" -> "Is node a dict or dataclass?"
  • Each branch shows example input/output
  • Highlighted path changes based on user selection
  • Side panel showing the extracted column-name/value pairs

Interactions: Click to select different NodeSpec configurations and see which extraction path activates. Toggle between dict input and dataclass input in fallback mode. Hover on extracted columns to see their source.

Learning Objective: (Analyze, Bloom Level 4) Students can predict which extraction strategy the flattener will use for a given node configuration.

Key Propagation

Key propagation ensures that parent identifier columns are available on all descendant rows, enabling direct joins between any child table and the root without intermediate hops. The flattener implements key propagation in the _walk method by building a child_parent_keys dictionary that accumulates as the traversal descends.

Two sources contribute propagated keys:

  • Global propagation from TreeSpec.meta.propagate_keys -- applies to all nodes
  • Node-level propagation from NodeSpec.propagate_keys -- applies from that node downward

During the walk, the flattener checks the current row for each propagated key column. If the value exists, it is added to the propagation dictionary passed to children. Child nodes receive these propagated values merged into their rows, ensuring the columns appear in every descendant table.

For example, with propagate_keys: [patient_id] at the meta level, a diagnosis row three levels deep still contains the patient_id value from the root patient. An analyst can join the diagnosis table directly to the patient table without going through the encounter table.

The propagation mechanism also supports the separate-table and routing dispatch paths. When a child is emitted to a separate table, the flattener merges both the FK values (from join_key) and the propagated keys into the child row before walking that child's subtree.

Synthetic Key Generation

When a child spec has no explicit join_key and the parent has no primary_key, the flattener must still link parent and child rows. It does this by generating synthetic integer keys -- monotonically increasing counters scoped to each table.

The synthetic key column name follows the pattern {synthetic_key_prefix}{table_name}_id. With the default prefix "_", a child table named encounters gets a synthetic column _encounters_id.

def _next_synthetic_key(self, table_name: str) -> int:
    val = self._counters.get(table_name, 0)
    self._counters[table_name] = val + 1
    return val

Synthetic keys have an important limitation: they work correctly only for single-document flattening. When batch processing flattens multiple documents, the counter resets per file, producing duplicate synthetic key values across files. This is why BatchBuilder.build_batch() raises a ValueError if any separate-table child relies on synthetic keys -- explicit join_key or primary_key declarations are required for batch mode.

Null Handling Strategy

The null handling strategy determines what happens when a row consists entirely of None values. This situation arises when an optional child exists in the spec but is absent from the source data -- the flattener creates a row with all nulls as a placeholder.

The SettingsConfig.null_handling field currently supports one strategy: "skip_all_none". Under this strategy, the _emit_row method checks whether all values in the row dictionary are None. If they are, the row is silently discarded rather than being added to the output table.

def _emit_row(self, table_name: str, row: dict[str, Any]) -> None:
    if self._spec.settings.null_handling == "skip_all_none":
        if all(v is None for v in row.values()):
            return
    if table_name not in self._tables:
        self._tables[table_name] = []
    self._tables[table_name].append(dict(row))

This behavior prevents phantom rows from appearing in output tables when optional subtrees are absent. However, note that a row with at least one non-None value (such as a foreign key) will be emitted even if all scalar fields are None. This is intentional: the FK value proves the row "exists" in the relational model even if its content fields are empty.

Tree Walk Algorithm

The tree walk algorithm is the core recursive traversal that drives the entire flatten operation. Implemented in the _walk method, it visits each node in the tree depth-first, extracts fields, propagates keys, dispatches children, and emits rows to the appropriate tables.

The algorithm proceeds through five phases for each node:

  1. Null check -- If the node is None, return immediately (base case for optional children)
  2. Field extraction -- Call _extract_fields to get the node's scalar values as a column dictionary
  3. Key merging -- Merge parent FK values and propagated keys into the current row
  4. Child dispatch -- Iterate over the node's children, selecting the appropriate handler (inline, separate table, or routing) based on the ChildSpec configuration
  5. Row emission -- If the NodeSpec has a table, emit the accumulated row to that table

The child dispatch phase checks for condition hooks before processing each child. If a child has a condition attribute, the flattener evaluates the named hook against the current context. If the condition returns False, the child is skipped entirely.

Diagram: Tree Walk Algorithm Execution

Tree Walk Algorithm Execution

Type: microsim sim-id: tree-walk-algorithm
Library: vis-network
Status: Specified

Purpose: Step-by-step animated visualization of the tree walk algorithm processing a sample tree with inline, separate-table, and routed children. Shows the call stack, current row state, and emitted table rows.

Components:

  • Left panel: tree structure with current node highlighted
  • Center panel: current row dictionary showing accumulated columns
  • Right panel: output tables with rows appearing as they are emitted
  • Bottom panel: call stack showing recursive _walk depth
  • Step/Play/Reset controls

Interactions: Step button advances one phase at a time. Play button auto-advances with adjustable speed. Click any tree node to jump to its processing. Hover over emitted rows to see which tree node produced them.

Learning Objective: (Apply, Bloom Level 3) Students can trace the tree walk algorithm's execution through a multi-level tree and predict the output rows.

TreeFlattener Class

The TreeFlattener class is the public API for the flatten engine. It takes a TreeSpec, optional hooks, settings, and a class registry at construction time, then provides flatten and flatten_many methods for performing the transformation.

The constructor initializes several internal data structures. The _tables dictionary accumulates output rows keyed by table name. The _counters dictionary tracks synthetic key generation per table. The _class_registry maps node names to Python classes for type-aware introspection. A TreeContext object carries version and settings information for hook evaluation.

class TreeFlattener:
    def __init__(
        self,
        spec: TreeSpec,
        hooks: Optional[HookRegistry] = None,
        settings: Optional[dict[str, Any]] = None,
        class_registry: Optional[dict[str, type]] = None,
    ):
        self._spec = spec
        self._hooks = hooks or HookRegistry()
        self._tables: dict[str, list[dict[str, Any]]] = {}
        self._counters: dict[str, int] = {}
        self._class_registry: dict[str, type] = class_registry or {}

The flattener is designed to be stateless between calls. Each invocation of flatten or flatten_many resets the internal tables and counters, so a single flattener instance can be reused for multiple transformations.

Flatten Method

The flatten method is the primary entry point for transforming a single tree root into relational tables. It accepts any object (dataclass instance, dict, Protocol Buffer message) and returns a dictionary mapping table names to lists of row dictionaries.

The method is concise because it delegates to _walk:

def flatten(self, tree_root: Any) -> dict[str, list[dict[str, Any]]]:
    self._tables = {}
    self._counters = {}
    root_spec = self._spec.root_node
    root_row: dict[str, Any] = {}
    self._walk(tree_root, root_spec, self._spec.meta.root_element, {}, root_row)
    return self._tables

The return type dict[str, list[dict[str, Any]]] is the canonical table representation throughout the library. Each key is a table name, each value is a list of rows, and each row is a dictionary of column-name to value. This representation is intentionally simple -- it can be trivially converted to any tabular framework.

Flatten Many Method

The flatten_many method extends flatten to process a collection of tree roots, accumulating all output into a single set of tables. This is useful when the input contains multiple root-level records (e.g., multiple patients in a single file).

The method adds error handling around each record. In non-strict mode (the default), records that raise exceptions during flattening are logged and skipped. In strict mode, the first exception propagates immediately.

def flatten_many(
    self, records: Any, *, strict: bool = False
) -> dict[str, list[dict[str, Any]]]:
    self._tables = {}
    self._counters = {}
    root_spec = self._spec.root_node
    for i, record in enumerate(records):
        try:
            root_row: dict[str, Any] = {}
            self._walk(record, root_spec, self._spec.meta.root_element, {}, root_row)
        except Exception:
            if strict:
                raise
            logger.warning("Skipping record %d", i, exc_info=True)
    return self._tables

Synthetic Keys and flatten_many

When using flatten_many, synthetic key counters are shared across all records. This means the first patient's encounters get IDs 0, 1, 2, and the second patient's encounters continue at 3, 4, 5. This is correct behavior -- it ensures unique synthetic keys across the combined output.

Inline Child Dispatch

Inline child dispatch merges a child node's fields directly into the parent's row, prefixed to avoid column name collisions. This is the _handle_inline method, triggered when ChildSpec.is_inline is True.

The inline handler performs several steps:

  1. Look up the child's NodeSpec from the spec
  2. Determine the prefix (from ChildSpec.effective_prefix, which prefers variant over prefix)
  3. If the child value is None, populate all expected columns with None values (maintaining schema consistency)
  4. If positional_fields are declared, convert the list/tuple into a named dict
  5. Extract the child's fields and add them to the parent row with the prefix applied
  6. Recursively process the child's own children (supporting grandchild dispatch)

The None-population step is important for schema stability. Even when an optional inline child is absent, the parent row must contain the prefixed columns (with None values) so that all rows in the table have the same column set. The handler achieves this by consulting the class registry to discover the expected fields.

Inline dispatch supports arbitrary nesting depth. An inline child can itself have inline grandchildren, producing composed prefixes (addr_geo_latitude). It can also have separate-table or routed grandchildren, which create their own output tables linked back to the parent row's keys.

Separate Table Dispatch

Separate table dispatch writes child rows to their own output table, linked to the parent through foreign key columns. This is the _handle_separate_table method, triggered when ChildSpec.is_separate_table is True.

The method resolves the foreign key columns through a priority chain:

  1. Explicit join_key on the ChildSpec
  2. Parent NodeSpec's primary_key (fallback)
  3. Synthetic key generation (last resort)

For each child item, the method creates a new row dictionary, populates it with FK values and propagated keys, and then calls _walk to recursively process the child node. The recursive walk extracts the child's own fields and processes its grandchildren before emitting the child row to its target table.

The wrapper pattern adds a level of indirection. When ChildSpec.wrapper is True, the child value is expected to be a container object with the actual children accessible via ChildSpec.wrapper_attr. The handler unwraps this container before iterating over the items.

Routed Child Dispatch

Routed child dispatch is the most complex dispatch mode. It handles polymorphic children -- items from the same collection that should go to different tables based on a discriminator attribute. The _handle_routing method implements this behavior.

The routing algorithm processes each item in the child collection through three possible paths:

  1. Pivot match -- If the item's discriminator value matches a PivotEntry.key, the item's value is placed directly into the parent row's pivot column. The item does not go to any child table.

  2. Rule match -- If the discriminator value matches a RoutingRule.match value, the item goes to that rule's target table. The route_item helper function (from core.flatten.routing) handles this lookup.

  3. Default/overflow -- If no rule matches, the item goes to the default rule's table (if any) or the overflow_table.

For items routed to tables, the handler creates a child row with FK values and propagated keys, extracts the item's fields, walks the item's subtree, and emits the row to the target table. A subtle detail: if the child NodeSpec already has a table attribute, the _walk call emits the row there, and the routing handler does not double-emit. Only when the NodeSpec has no fixed table does the routing handler emit to the routing target.

Diagram: Three Dispatch Modes Compared

Three Dispatch Modes Compared

Type: microsim sim-id: dispatch-modes-compared
Library: p5.js
Status: Specified

Purpose: Side-by-side comparison showing the same source data processed through inline, separate-table, and routed dispatch, with the resulting table structures for each.

Components:

  • Source tree panel showing a patient with three observations of different types
  • Three output panels, one per dispatch mode
  • Inline panel: single wide table with prefixed columns
  • Separate panel: two tables linked by FK
  • Routed panel: three tables (one per observation type) linked by FK
  • Animated data flow arrows from source to output

Interactions: Click on an observation in the source tree to trace it through each dispatch mode. Toggle observation types on/off to see how each mode handles absent children. Compare column counts across modes.

Learning Objective: (Evaluate, Bloom Level 5) Students can evaluate which dispatch mode best fits a given data modeling requirement by comparing the resulting table structures.

Value Access Pattern

The flattener uses a unified value access pattern through the _get_value helper method. This method abstracts over two common input types:

  • For dict inputs, it calls dict.get(attr_name) to return None for missing keys
  • For object inputs (dataclasses, Protocol Buffers), it calls getattr(node, attr_name, None)

This dual-mode access is what allows the same flattener code to handle both parsed JSON (dict trees) and typed dataclass trees. Protocol Buffer messages receive special treatment: the flattener checks for a HasField method and uses it to distinguish between "field not set" and "field set to default value" -- a distinction that matters for proto3 semantics.

Complete Flatten Example

To see all the pieces working together, consider a small but realistic example. A patient has a name, an inline address, and a list of encounters stored in a separate table.

The spec declares Patient as the root with an inline Address child and a separate-table Encounter child:

from mountainash_treespec.core.flatten.flattener import TreeFlattener
from mountainash_treespec.core.spec.loader import load_spec_from_dict

spec = load_spec_from_dict({
    "meta": {"name": "demo", "root_element": "Patient"},
    "settings": {"column_naming": "snake_case"},
    "nodes": {
        "Patient": {
            "table": "patients",
            "primary_key": ["patient_id"],
            "children": {
                "address": {"node": "Address", "inline": True, "prefix": "addr"},
                "encounters": {
                    "node": "Encounter", "table": "encounters",
                    "cardinality": "many", "join_key": "patient_id",
                },
            },
        },
        "Address": {},
        "Encounter": {"table": "encounters"},
    },
})

flattener = TreeFlattener(spec)
tables = flattener.flatten(patient_tree)
# tables["patients"] -> [{"patient_id": "P1", "name": "Alice", "addr_city": "Melbourne", ...}]
# tables["encounters"] -> [{"patient_id": "P1", "encounter_date": "2024-01-15", ...}, ...]

The output demonstrates inline decomposition (address columns prefixed with addr_ in the patients table) and separate-table decomposition (encounters in their own table with patient_id as the FK).

Key Takeaways

  • The tree walk algorithm visits nodes depth-first, extracting fields, propagating keys, dispatching children, and emitting rows.
  • Field extraction supports three strategies: explicit mapping, resolved fields, and fallback introspection -- enabling both typed and untyped inputs.
  • Key propagation flows parent identifiers to all descendant tables, enabling direct analytical joins.
  • Synthetic key generation provides automatic FK columns when no explicit keys are declared, but is limited to single-document mode.
  • Column naming converts CamelCase to snake_case; prefixed names prevent collisions for inline children.
  • Null handling suppresses all-None rows to prevent phantom records from optional absent children.
  • The TreeFlattener provides flatten (single tree) and flatten_many (collection) entry points.
  • Three dispatch modes handle different child patterns: inline (merge into parent), separate table (own table with FK), and routed (polymorphic dispatch by discriminator).