Repository navigation
Design: expand/restrict diagram-traversal algebra (2.4) - #1524
Closed
dimitri-yatsenko wants to merge 10 commits into
Closed
dimitri-yatsenko wants to merge 10 commits into
dimitri-yatsenko wants to merge 10 commits into
Conversation
Copy link
Copy Markdown
Member
Sorry, something went wrong.
Proposed 2.4 design that collapses Diagram.cascade / Diagram.trace / Diagram.restrict into a small composable algebra, derived from first principles: - One primitive: propagate a restriction across a foreign key by semijoin, either direction. - R1 (edge rule): the semijoin, with identity fast-path for primary, non-renamed FKs; absorbs the former F1-3 / U1-3 rules. - R2 (group rule): a restriction touching any part of a master group brings the whole group (existential lift + re-expand). - Two operations: expand(seed, direction) — additive constructor (cascade=down, trace=up retained as aliases); and diagram.restrict(*conditions, direction) — subtractive progressive carving. They compose freely on one representation (union to grow, intersection to carve), removing the current cascade-vs-restrict mutual exclusivity. Includes derivation, the mouse/method counterexample showing restrict is not reducible to expand, and open follow-ups (restrict direction default, #1481 master->parts trace descent, release scoping).
Align to DataJoint's canonical operator names (& = restriction). These foreign-key-matched narrowings are restrictions, not joins.
Replace primed set-variables and union/intersection symbols with DataJoint expressions (`&`, restrict-by-list for OR, chained `&` for AND).
Adds section 6 deriving how expand(A & r) propagates across renamed foreign keys, distinguishing the dict-key seed (relabel keys through the edge, values unchanged) from the general-condition seed (restrict the neighbor by the renamed projection). Written to stand alone, in DataJoint operators.
…ed FKs Restructure section 6 around the three kinds of seed restriction — materialized (dict / sequence of dicts, e.g. A.keys()), subquery, and string query — and how each crosses a renamed foreign key. Add the traversal rule for materialized keys: relabel the carried attributes and drop any key field the neighbor lacks (which is what makes the upstream walk yield exactly the parent's key). Note the drop is exact for identity fields and, for extra constraints, resolved by materializing first; unify live restrictions to the materialized path via (A & r).keys().
Clarify that expand(A & key) uses the relabel fast-path only when key contains solely primary-key attributes of A. A secondary attribute is referenced by no foreign key, so it cannot propagate — a key mixing one in is really an opaque A & cond (Kind 2/3), reducible to Kind 1 via (A & cond).keys(). Per Dimitri's correction.
…xpand/restrict fallback Replace the PK-only framing with the per-edge principle: an attribute propagates across an edge iff that edge carries it (so a secondary FK attribute propagates along its edge; a data attribute never does). Derive the up/down rule from the FK being a function: down always suffices with a parent key; up needs the parent's full primary key. Add the confirmed additive/subtractive fallback: when the up key is insufficient, expand must materialize (exactness) while restrict may skip (conservative carve). Same fast-path condition; only the fallback differs.
Derive how a materialized key crosses a master<->part boundary: R2 needs no new key machinery. The existential lift (part->master) is relabel-drop, with sibling part keys collapsing onto one master key by dedup; the atomic re-expansion (master->all parts) is a fresh downstream relabel from the recovered master key that widens by dropping the part-specific constraint. The round trip is lossy on the part-specific attribute, and that loss is compositional atomicity in key terms. Corollaries: materialized seeds stay materialized (delete-safe for free); one mechanism serves cascade/trace/restrict.
Copy link
Copy Markdown
Member
Author
|
Closing: the derivation has been relocated to the datajoint-docs specs (folded into diagram.md's 'Traversal algebra' section) — datajoint/datajoint-docs#249 — per the decision that the full derivation and spec live with the other specs, not as a DESIGN-*.md in the code repo. DESIGN-expand-restrict.md was only ever on this branch, so it does not land on master. |
Sorry, something went wrong.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Reviewers
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
What
Proposed 2.4 design (docs-only) deriving a small, composable algebra for diagram traversal that collapses Diagram.cascade / Diagram.trace / Diagram.restrict into two operations. Adds DESIGN-expand-restrict.md; no code changes.
The design
Includes the "all data for mouse_id=5 and method_id=5" counterexample showing restrict is not reducible to combinations of expand.
Scope / relationship to 2.3.3
This is a 2.4 API evolution, not part of the 2.3.3 bug-fix line. The compositional-integrity issues #1496 / #1501 / #1481 fold into this redesign rather than shipping as standalone 2.3.3 patches. (The multi-FK-path walk + alias-docstring scrub already landed separately on the 2.3.3 branch.)
Open for review
Draft — opening for design review before any code or spec refactor.