Stacked on #1621 (the reference model). This PR adds the planner behind Diagram.expand, the classmethod itself, and tests that compare the planner with the reference model. cascade(), trace() and Table.delete() are unchanged; they move onto the planner in later PRs.

The normative definitions are the "Traversal specification" section of diagram.md and the Traversal Shape Catalog in datajoint/datajoint-docs#249.

What it adds

src/datajoint/expand.py works in three steps, as the specification's "Computation" section describes them.

1. A schema description, TraversalSchema. It is plain data: tables with their primary keys, attributes and nullable attributes, foreign keys with their attr_map, and each master's owned parts with their owning attributes (A1). TraversalSchema.from_dependencies builds it from connection.dependencies and the table headings, which give nullability and attribute order. The tests build it by hand from the reference model.
2. The planner, plan_expand(schema, seed, direction). It builds a Plan, an intermediate form whose nodes are Seed, Literal, Restrict, Lift, Reexpand and Or. A node names the restrictions it uses by a handle, the index of another node. The planner reads no rows.
3. Two evaluators. QueryCompiler and compile_plan turn a plan into one restricted FreeTable per table. RowEvaluator evaluates a plan on rows held in memory, in the reference model's format.

Diagram.expand(seed, direction="down") returns a diagram whose nodes are the seed's table-level reach. On it, d[T] returns table T restricted to its rows (by class, instance, full table name or class name), counts() counts the rows, and iteration yields each node's restricted table in the plan's topological order. The rest of the expanded-diagram contract comes later: copying, +, the operators that raise, and prune().

How it maps to the specification

Tests

tests/unit/test_expand_plan.py, with no database:

• The schema description agrees with the reference model on random schemas: owned parts, owning attributes, groups that iterate, the copy and relabel rules, the table-level reach, and the order and cycles of Q. The same holds when the description is built from a Dependencies graph, with either quoting.
• On random schemas, databases and seeds, the plan evaluated in memory selects exactly the model's D(S), U(S) and U(D(S)). Every seed kind is drawn: a condition, literal key dicts, keys read from the seed table, and no restriction. Copies are evaluated as copies, by applying the copied condition to the child's rows, so the copy rule is tested and not assumed. The seed kinds give the same rows (K3).
• Plan structure for S1–S5, S7, G1–G7, K1, K4 and K5: where a condition is copied and where it is restricted, the lifts and their attribute maps, and which groups iterate. For G4, the master keys grow as {1}, {1, 2}, {1, 2, 3}.
• A delete simulation runs a down plan as a cascade would: leaves first, each table's restriction evaluated on the database as it is at that moment, and ON DELETE RESTRICT emulated. It leaves DB − D(S) in two cases: when no lift is evaluated at delete time, and when the nodes that "Materialization happens only at delete time" names are materialized first (every lift, and the seed unless it is literal keys). With the plan's own materialization flags, which a later PR adds, the delete property is a strict xfail. The xfail pins G1, G7 and a K1 seed that reads its descendant (Cascade delete: a restriction referencing an earlier-deleted (downstream) table is silently invalidated by reverse-topological delete order — materialize (independent of MySQL 1093) #1496).
• A test that datajoint.dependencies.owned_parts (fix(declare): refuse a part reference that closes a master-part group cycle #1620) finds the same owned parts. It is skipped until fix(declare): refuse a part reference that closes a master-part group cycle #1620 merges, so the two PRs can merge in either order.

tests/integration/test_expand_planner.py, on MySQL and PostgreSQL: S1, S3, S7, G1, G4, G7 and K1, K3–K6 return the rows the catalog states in every table, in each direction the catalog lists. Refused seeds and unknown directions raise. The full catalog, the differential tests on random schemas and the delete tests follow.

Harness strength. Each of these planner mutations fails between 4 and 13 tests in test_expand_plan.py (ci profile):

• dropping the lift;
• keeping one term per table (AND instead of OR for parallel foreign keys);
• swapping the rename direction;
• stopping a group that iterates after one round;
• copying whenever a condition's attributes are in the child's primary key;
• copying upward.

Questions for the specification

For datajoint/datajoint-docs#249:

1. A QueryExpression keeps only compiled conditions. The copy rule is stated for conditions (a dict's keys, a query expression's heading). This PR reads a seed's attributes from restriction_attributes and never copies a condition that contains a subquery. For the same reason, K6's warning cannot be raised: restrict() drops a dict that names no attribute before the seed is seen.
2. The node list has no copy node, and the plan "never copies compiled SQL". Here a copy is Restrict(copy=True), and a copied seed condition is the seed's compiled SQL applied to the child. Is that the intended reading?
3. The tie-break "the first owning reference in its definition" refers to an order the database does not record. Should it be the heading order?
4. R1 upward and the lift, written as .proj(...), keep the source's primary key. Should the text say "projected onto the foreign key's attributes" (or "onto the owning attributes")?
5. A dj.Top seed is read before delete time, like the keys of a group that iterates. Should "Materialization happens only at delete time" name it too?

Next

• cascade() and trace() become expand() with their part_integrity modes, and the old propagation code is removed.
• Delete-time materialization, and enforce as a row-level check before deleting (Cascade delete: a restriction referencing an earlier-deleted (downstream) table is silently invalidated by reverse-topological delete order — materialize (independent of MySQL 1093) #1496).
• trace() as expand(..., "up"), and self.upstream built from the parents of the row a make() will insert (Diagram.trace: descend through master-part boundaries (Merge-table upstream tracing) #1481).
• The expanded-diagram contract (copying, +, operators that raise, prune()), and the deprecation of restrict() (Diagram.restrict: apply Part conditions through the Master to preserve master-part compositional integrity #1501).