Self-referential many-to-many: acyclicity and a materialized transitive closure #151
Loading…
Add table
Add a link
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
K1 — Self-referential many-to-many: acyclicity and a materialized transitive closure
Status: draft, ready to file on PerishLab/keel. Unblocks Phase 1 of the
codehull identity seam. Two clauses, nothing else — this is the third
version of this issue; the two earlier ones were wrong in ways recorded at the
bottom, and both went wrong by widening.
Motivation
Ensign is about to model organisations as a single self-referential
many-to-many on
Actor: an org's members may themselves be orgs. Teams stopbeing their own unit and become nested orgs. A token then carries the closure
of the orgs its subject belongs to, and the consuming forge evaluates ordinary
grants against that claim.
Two engine properties are missing for that to be sound.
1. An acyclicity invariant on a self-referential many-to-many
A tie that would close a cycle must be refused at write time.
This has to be the engine's, not the caller's. An invariant that arrives later
can only reject new cycles; it cannot repair the ones already stored. A
ceremony-level check in one caller is also not the same guarantee: any other
writer through any other Face bypasses it.
2. A materialized transitive closure
A declared self-referential many-to-many gains an engine-owned closure
relation, refreshed as part of the same write that changes a tie. Grants then
read it as an ordinary
predover a normal relation — no new scope grammar,no new capability verb.
It must be maintained inside the write transaction, and must not be a
trigger consumer.
docs/run/trigger.mdis post-commit and observe-only andforbids consumer participation in the write path — correctly. But a grant that
evaluates against an asynchronously refreshed closure makes authorization
eventually consistent: a revoked membership stays effective for the length of
the delivery lag. Consistency here is not a performance preference.
This would be the engine's first push-side derived structure. Today the engine
is pull-only and depth-1: bond bags are the live closure of the current root
bag, forward bonds only, and deep graphs are explicitly told to use another
top-level query (
docs/model/edge.md).Explicitly not asked for
per request is exactly why nested-group ACLs in LDAP are famously slow. The
closure is a table to be read, not a traversal to be run.
it out of this one is deliberate.
Two earlier versions of this issue, both wrong
discloseon its operands." This patchedpermissions onto the wrong operation. The answer was a consent model in the
product, not a widening in the engine.
birthtargeted at a named subject." Already solved:run/face/grant.rsmint()grants authority to the creating operator in the same transaction.Recording these so a fourth version does not rediscover them.