Foundation Concepts

Summary

This chapter introduces the prerequisite knowledge for understanding mountainash-treespec. You will learn about hierarchical and relational data models, how tree structures decompose into tables, the principle of round-trip fidelity, and the Python building blocks (dataclasses, protocols, decorators) that the library relies on. It also covers the tabular frameworks (Polars and PyArrow), relational key concepts, and YAML configuration.

Concepts Covered

• Hierarchical Data
• Relational Tables
• Tree to Table Decomposition
• Round Trip Fidelity
• Python Dataclasses
• Python Protocols
• Polars DataFrames
• PyArrow Tables
• Foreign Keys
• Primary Keys
• YAML Configuration
• Decorator Pattern

Prerequisites

None. This is the introductory chapter.

Learning Objectives

After completing this chapter, you will be able to:

• Distinguish hierarchical data from relational tables
• Explain how tree structures decompose into flat tables
• Describe what round-trip fidelity means for data transformation
• Identify the roles of dataclasses, protocols, and decorators in Python
• Use Polars DataFrames and PyArrow Tables for tabular data
• Explain primary keys and foreign keys in relational models

---

Introduction

Data transformation libraries operate at the boundary between two fundamentally different ways of organizing information. On one side sits hierarchical data -- nested structures where parent records contain their children directly. On the other side sits relational tables -- flat rows and columns where relationships are expressed through shared key values. Mountainash-treespec exists to bridge these two worlds, and understanding both models deeply is the first step toward using the library effectively.

This chapter builds your vocabulary and mental models for the twelve foundation concepts that every subsequent chapter depends on. We begin with the two data models themselves, then explore how one converts into the other, and finish with the Python tools that make the implementation possible.

Hierarchical Data

Hierarchical data organizes information as a tree of nested records. Each node in the tree can contain scalar values (strings, numbers, dates) and child nodes that represent sub-records. The parent-child relationship is expressed structurally: a child record lives physically inside its parent.

Consider a hospital patient record in XML. The patient element contains demographic fields like name and date of birth, and also contains nested elements for encounters, diagnoses, and medications. Each encounter in turn contains its own nested observations and procedures. This nesting can extend to arbitrary depth.

The same hierarchical pattern appears across many formats:

• XML documents -- elements contain sub-elements
• JSON objects -- objects contain nested objects and arrays
• Protocol Buffer messages -- messages contain nested messages
• Python dataclass trees -- dataclass instances hold references to other dataclass instances

The key characteristic of hierarchical data is that traversal follows a single path from root to any leaf. There are no cross-references between siblings, and every child has exactly one parent. This makes hierarchical data natural for document-oriented storage and transmission, but challenging for analytical queries that need to aggregate across different levels of the tree.

Diagram: Hierarchical Data Tree Structure

Hierarchical Data Tree Structure

Type: diagram sim-id: hierarchical-data-tree
Library: vis-network
Status: Specified

Purpose: Visualize a sample hierarchical data tree (patient record with encounters, diagnoses, medications) showing parent-child nesting. Nodes are color-coded by depth level.

Components:

• Root node (Patient) at top, colored dark blue
• Level-1 children (Encounter, Demographics) in medium blue
• Level-2 children (Diagnosis, Procedure, Observation) in light blue
• Level-3 children (Code, Qualifier) in pale blue
• Directed edges from parent to child

Interactions: Click any node to highlight its subtree. Hover to see the node's scalar fields in a tooltip. Drag nodes to rearrange the layout.

Learning Objective: (Understand, Bloom Level 2) Students can identify parent-child relationships in a hierarchical data structure.

Relational Tables

Relational tables organize data as rows and columns in flat, two-dimensional structures. Each table represents a single entity type, and each row represents one instance of that entity. Columns define the attributes that every row shares.

Where hierarchical data embeds relationships through physical nesting, relational tables express relationships through shared column values. A patient table might have one row per patient, while an encounter table has one row per encounter. The encounter table includes a patient_id column whose value matches the corresponding row in the patient table. This indirection is what makes relational data fundamentally different from hierarchical data.

Relational tables excel at analytical queries. Aggregating all diagnoses across all patients requires scanning a single diagnosis table rather than traversing thousands of nested document trees. Joins between tables allow flexible recombination of data that the original hierarchical structure never anticipated.

Property	Hierarchical Data	Relational Tables
Structure	Nested tree of records	Flat rows and columns
Relationships	Physical containment	Shared key values
Query pattern	Traverse from root	Join across tables
Duplication	Minimal (one copy)	Keys repeated per row
Best suited for	Document storage, transmission	Analytics, aggregation

Primary Keys

A primary key is a column (or set of columns) whose values uniquely identify each row in a table. No two rows in the same table may share the same primary key value, and the value must not be null.

In mountainash-treespec, primary keys serve two critical roles. First, they identify which parent row a child row belongs to when rebuilding trees from tables. Second, they anchor the deduplication logic that removes duplicate records during batch processing. A NodeSpec declares its primary key through the primary_key field, which accepts a list of column names.

For example, a patient table might use ["patient_id"] as its primary key, while a compound key like ["patient_id", "encounter_date"] might uniquely identify rows in an encounter table.

Foreign Keys

A foreign key is a column in one table that references the primary key of another table. It encodes the parent-child relationship that was implicit in the hierarchical structure. When mountainash-treespec flattens a tree into tables, the child table acquires a foreign key column containing its parent's primary key value.

Consider the relationship between patients and encounters. After flattening, the encounters table contains a patient_id column. Each value in that column matches exactly one row in the patients table. This allows the build engine to reconstruct which encounters belong to which patient during the inverse operation.

Foreign keys in mountainash-treespec are declared through the join_key attribute on a ChildSpec. When no explicit join key is provided and the parent node has a declared primary_key, the library automatically uses the parent's primary key as the foreign key column on the child table.

Synthetic Keys

When neither join_key nor primary_key is declared, the flattener generates synthetic integer keys (e.g., _encounters_id) to link parent and child rows. These work for single-document flattening but cannot partition children across multiple roots in batch mode.

Tree to Table Decomposition

Tree to table decomposition is the process of transforming a hierarchical data tree into a set of relational tables. This is the central operation that mountainash-treespec performs in its "flatten" direction.

The decomposition follows a systematic algorithm. Starting at the root node, the flattener extracts scalar field values into a row for the root table. When it encounters a child node, it must decide how to represent that child in relational form. The two primary strategies are:

1. Inline decomposition -- The child's fields are merged into the parent's row with a distinguishing prefix. This keeps parent and child data in a single table but widens the row.

2. Separate table decomposition -- The child's fields go into their own table, linked to the parent through a foreign key column. This normalizes the data but requires joins to reassemble.

The choice between these strategies depends on the child's cardinality (one-to-one vs. one-to-many) and the analyst's query patterns. One-to-one children that are always accessed alongside their parent are good candidates for inlining. One-to-many children must use separate tables because a single parent row cannot hold a variable number of child rows.

Diagram: Tree to Table Decomposition Flow

Tree to Table Decomposition Flow

Type: workflow sim-id: tree-to-table-decomposition
Library: vis-network
Status: Specified

Purpose: Animate the step-by-step decomposition of a small tree (Patient > Encounter > Diagnosis) into three relational tables, showing how foreign keys link the tables.

Components:

• Left panel: hierarchical tree with three levels
• Right panel: three relational tables that populate row-by-row
• Arrows showing which tree node produces which table row
• FK columns highlighted in gold

Interactions: Step-through button advances the decomposition one node at a time. Reset button returns to the initial tree. Hover over a table row to highlight the source tree node.

Learning Objective: (Apply, Bloom Level 3) Students can trace how each node in a tree maps to rows and foreign keys in the output tables.

Round Trip Fidelity

Round trip fidelity is the guarantee that data survives a flatten-then-build cycle without loss or distortion. If you flatten a tree into tables and then build those tables back into a tree, the result should be identical to the original.

This property is non-trivial to achieve. During flattening, structural information (which children belong to which parent, the ordering of list elements, the distinction between an absent field and a null field) must be preserved in the relational representation. During building, all of that structural information must be recovered faithfully.

Mountainash-treespec achieves round trip fidelity through several mechanisms:

• Key propagation ensures parent identifiers flow down to all descendant tables
• Column naming conventions preserve the original field names through predictable transformations
• Null handling strategies distinguish between "field not present" and "field present but null"
• Cardinality metadata in the spec tells the builder whether to reconstruct a single child or a list

When round trip fidelity cannot be maintained (for example, when a routing configuration merges multiple source types into a single table), the spec allows marking a child as lossy: true to document the intentional information loss.

Python Dataclasses

Python dataclasses, introduced in Python 3.7 via the dataclasses module, are the primary data structure that mountainash-treespec operates on. A dataclass is a regular Python class with automatically generated __init__, __repr__, and __eq__ methods based on annotated class attributes.

from dataclasses import dataclass, field
from typing import Optional

@dataclass
class Patient:
    patient_id: str
    name: str
    date_of_birth: Optional[str] = None
    encounters: list["Encounter"] = field(default_factory=list)

In the context of mountainash-treespec, dataclasses serve as the typed schema for hierarchical data. Each node in a tree is an instance of a dataclass, and the library introspects field names, types, and annotations to determine how to extract values during flattening and how to reconstruct instances during building.

The library accesses dataclass fields through dataclasses.fields() for iteration and getattr() for value retrieval. Type annotations drive the type system (Chapter 4) to determine the correct PyArrow column types for the output tables.

Python Protocols

Python protocols, defined in typing.Protocol (PEP 544), enable structural subtyping -- a form of duck typing with static type checker support. A class satisfies a protocol if it implements the required methods, without needing to inherit from or explicitly register with the protocol.

Mountainash-treespec uses protocols extensively in its schema handling layer. The SchemaHandler protocol defines the interface that all format-specific handlers must implement. The SchemaFieldInfo protocol defines what information a handler must provide about each field it discovers.

@runtime_checkable
class SchemaHandler(Protocol):
    def can_handle(self, cls: type) -> bool: ...
    def get_fields(self, cls: type) -> list[SchemaFieldInfo]: ...
    def get_source_name(self, cls: type) -> str: ...
    def get_cardinality(self, cls: type, field_name: str) -> tuple[int, int | None]: ...
    def get_choice_groups(self, cls: type) -> list[list[str]]: ...
    def to_fieldspec(self, field_info: SchemaFieldInfo) -> FieldSpec: ...
    def construct(self, cls: type, kwargs: dict[str, Any]) -> Any: ...

The protocol-based design means new data formats (Avro, Protobuf, Pydantic) can be supported by implementing a handler class that satisfies the protocol. No base class inheritance or registration ceremony is required beyond implementing the expected methods.

Decorator Pattern

The decorator pattern in Python uses the @decorator syntax to wrap a function with additional behavior. Mountainash-treespec uses decorators in two key places: the HookRegistry for registering custom hooks, and the SchemaHandlerRegistry for handler registration via entry points.

The hook registry provides four decorator methods that register callback functions by name. Here is how a condition hook is registered:

hooks = HookRegistry()

@hooks.condition("has_encounters")
def check_encounters(ctx: TreeContext) -> bool:
    return len(ctx.row.get("encounters", [])) > 0

The @hooks.condition("has_encounters") line calls the condition method with the hook name, which returns a decorator function. That decorator stores the wrapped function in the registry's internal dictionary and returns it unchanged. Later, when the flattener encounters a condition: has_encounters reference in a spec, it looks up and calls this registered function.

This pattern keeps hook definitions close to their logic while allowing the spec to reference them by name -- a clean separation between configuration (YAML) and behavior (Python).

YAML Configuration

YAML (YAML Ain't Markup Language) is the primary configuration format for mountainash-treespec specifications. A TreeSpec YAML file declares the metadata, settings, node definitions, child relationships, and optional batching configuration that drive the flatten and build engines.

The library's Spec Loader reads YAML files using Python's yaml.safe_load() and transforms the raw dictionary into typed dataclass instances (TreeSpec, NodeSpec, ChildSpec, etc.). Here is a minimal spec:

meta:
  name: patient-spec
  root_element: Patient
  source_format: xml

settings:
  column_naming: snake_case
  null_handling: skip_all_none

nodes:
  Patient:
    table: patients
    primary_key: [patient_id]
    children:
      encounters:
        node: Encounter
        table: encounters
        cardinality: many
        join_key: patient_id

YAML's indentation-based structure maps naturally to the nested configuration that TreeSpec requires. Each level of indentation corresponds to a level in the spec's dataclass hierarchy.

Polars DataFrames

Polars is a high-performance DataFrame library written in Rust with Python bindings. In the mountainash-treespec ecosystem, Polars DataFrames serve as one of the target representations for flattened relational data.

After the flattener produces its output as Python dictionaries (dict[str, list[dict[str, Any]]]), downstream code can convert each table's row list into a Polars DataFrame for efficient columnar operations. Polars provides lazy evaluation, parallel execution, and memory-efficient columnar storage that make it well-suited for large batch processing pipelines.

The relationship between mountainash-treespec and Polars is indirect: the library produces standard Python dictionaries that any tabular framework can consume. Polars is the recommended choice for production workloads due to its performance characteristics.

PyArrow Tables

PyArrow is the Python implementation of Apache Arrow, an in-memory columnar data format. Where Polars focuses on DataFrame operations, PyArrow provides the foundational type system and I/O capabilities that mountainash-treespec uses for schema derivation and Parquet output.

The Arrow Schema Builder in the type system (Chapter 4) converts TreeSpec metadata into PyArrow schemas. Each table in the flattened output receives a schema that maps column names to PyArrow data types. These schemas enable strongly-typed Parquet file output where every column has a precise type rather than defaulting to strings.

Tabular Framework	Role in mountainash-treespec
Polars DataFrames	High-performance analytics on flattened output
PyArrow Tables	Schema derivation, Parquet I/O, type system bridge
Python dicts	Native output format from flatten engine

The derive_arrow_schemas function discovers columns from six sources: dataclass fields, foreign key columns, propagated keys, synthetic keys, pivot columns, and source columns. This comprehensive discovery ensures the Arrow schema covers every column that the flattener might produce.

Diagram: Foundation Concept Dependencies

Foundation Concept Dependencies

Type: graph-model sim-id: foundation-concept-deps
Library: vis-network
Status: Specified

Purpose: Show how the twelve foundation concepts depend on each other, with arrows indicating prerequisite relationships (e.g., Foreign Keys depends on Relational Tables; Tree to Table Decomposition depends on both Hierarchical Data and Relational Tables).

Components:

• 12 nodes, one per foundation concept, color-coded by category (data models in blue, Python tools in green, tabular frameworks in orange, keys in gold)
• Directed edges showing dependency relationships
• Concept nodes sized by number of downstream dependents

Interactions: Click a node to highlight all concepts that depend on it (forward chain). Double-click to highlight all prerequisites (backward chain). Drag to rearrange.

Learning Objective: (Analyze, Bloom Level 4) Students can trace dependency chains between foundation concepts and identify which concepts must be understood before others.

Connecting the Foundation to TreeSpec

These twelve concepts form the vocabulary that every subsequent chapter builds upon. The data model concepts (hierarchical data, relational tables, decomposition, fidelity) define the problem space. The key concepts (primary keys, foreign keys) define how relationships survive the transformation. The Python tools (dataclasses, protocols, decorators) define the implementation mechanisms. And the tabular frameworks (Polars, PyArrow) and configuration format (YAML) define the ecosystem interfaces.

As you proceed through the remaining chapters, you will see each of these concepts reappear in specific technical contexts. The TreeSpec dataclass (Chapter 2) is a Python dataclass configured via YAML. The flatten engine (Chapter 3) implements tree to table decomposition using key propagation and foreign keys. The type system (Chapter 4) bridges Python types to PyArrow types. Understanding the foundation makes every subsequent layer transparent.

Key Takeaways

• Hierarchical data organizes information as nested trees; relational tables organize it as flat rows and columns linked by keys.
• Tree to table decomposition is the core flatten operation, with inline and separate-table strategies for handling children.
• Round trip fidelity guarantees that flatten-then-build produces an identical tree, achieved through key propagation, naming conventions, and null handling.
• Primary keys uniquely identify rows; foreign keys link child rows to their parents across tables.
• Python dataclasses are the typed schema for tree nodes, inspected at runtime for field names and types.
• Python protocols enable structural subtyping, allowing new format handlers without base class inheritance.
• Decorators register hooks and handlers by name, separating YAML configuration from Python behavior.
• YAML is the spec configuration format; Polars and PyArrow are the downstream tabular frameworks.