What does the join of two permission sets in a lattice give you that a plain partial order cannot?
answer
- combining two levels needs one answer
- least upper bound, not just any bound
- both directions, join and meet
- two minimal upper bounds means no join
- union and intersection as the model pair
basics
~20 sThe join is the least upper bound: the smallest level that dominates both, unique whenever it exists. A plain partial order may offer several incomparable upper bounds, or none at all, so 'combine these two' has no canonical answer there.
solid answer
~50 sIn a poset, an **upper bound** of `x` and `y` is anything above both. The **join** `x ∨ y` is the *least* such element: above both, and below every other upper bound. The **meet** `x ∧ y` is the mirror image, the greatest lower bound. A **lattice** is a poset where every pair has both, and that guarantee is the whole payoff — combining two grants becomes a function rather than a policy argument. Ordered by inclusion, sets of permissions form a lattice with join as union and meet as intersection. A hand-built role hierarchy usually does not: two roles can have two minimal common super-roles that are incomparable, so there is no least upper bound and no defensible answer to "what does holding both give?" A top element does not save you — it is an upper bound, just not a least one.
go deeper
Hold on to the model: with sets ordered by inclusion, join is union and meet is intersection. Least upper bound means smallest thing above both, not just anything above both.
Explain why a join is unique when it exists, and show a four-element order with two minimal upper bounds where it does not — that is the whole distinction between a poset and a lattice.
Demonstrate the operational payoff: commutative, associative, idempotent joins make independently combined results agree without coordination, which is why the structure is chosen deliberately.
Decide whether to force the model into a lattice or to accept policy-defined combination. The first constrains how roles may be added forever; the second leaves a judgment call in every merge.
## Upper bounds, and the least one Fix a partial order. For two elements `x` and `y`: - an **upper bound** is any `u` with `x <= u` and `y <= u`; - the **join**, written `x ∨ y`, is an upper bound that is below every other upper bound — the *least* upper bound; - the **lower bound** and the **meet** `x ∧ y` (greatest lower bound) are the same notions upside down. A join, if it exists, is unique: two least upper bounds would each be below the other, and antisymmetry collapses them into one element. That uniqueness is what makes "combine these two" answerable at all. ## What a lattice guarantees A **lattice** is a poset in which *every* pair has a join and a meet. From that single guarantee a small algebra follows, and each law has an operational reading: | Law | Statement | Why it matters | |---|---|---| | Idempotence | `x ∨ x = x` | Applying the same grant twice changes nothing | | Commutativity | `x ∨ y = y ∨ x` | The order the two inputs arrive in is irrelevant | | Associativity | `(x ∨ y) ∨ z = x ∨ (y ∨ z)` | Grouping is irrelevant; partial merges are safe | | Absorption | `x ∨ (x ∧ y) = x` | Intersecting then re-joining adds nothing new | Together, idempotence, commutativity and associativity say that the result of merging a collection depends only on the *set* of things merged — not on order, not on grouping, not on repetition. That is exactly the property independent parties need to reach the same answer without coordinating. A finite non-empty lattice also has a maximum and a minimum: join everything together and you get a top element, meet everything and you get a bottom. In a permission reading, those are "all rights" and "no rights". ## The concrete model Order sets of permissions by inclusion — `P <= Q` when `Q` contains every entry of `P`. Then: - `P ∨ Q` is the **union**: the smallest set containing both, which is exactly the effective grant of holding both. - `P ∧ Q` is the **intersection**: the largest set inside both, which is what two parties can *jointly* certify, and the right operation when downgrading a session to what both a token and a role permit. Note how the two answer different questions. Join answers "what does holding both amount to?"; meet answers "what do both agree on?" Reaching for one where the other belongs either over-grants or over-restricts. ## When a partial order is not a lattice Take four roles: `reader` and `auditor` are incomparable, and two further roles, `support` and `analyst`, each sit above both — but `support` and `analyst` are themselves incomparable. Upper bounds of `{reader, auditor}` exist; there are two of them, and neither is below the other. So there is no *least* one, no join, and no lattice. What breaks is not the mathematics but the product question. "A user holds reader and auditor — what may they do?" has two defensible answers and no way to choose between them from the hierarchy alone. Three ways out: 1. **Add the missing element** — introduce a role that is precisely the least upper bound, converting the order into a lattice. 2. **Change the representation** — order by sets of primitive permissions rather than by named roles, which is a lattice by construction. 3. **Declare a policy** — pick one answer and document that it is a decision, not a derivation. Only the first two make the combination a function of the inputs. ## Weaker structures in between The two halves are independent. A poset where every pair has a join but not always a meet is a **join-semilattice**; the dual is a meet-semilattice. Plenty of real hierarchies are one-sided like this, and the distinction is worth naming, because a system that only ever merges upwards needs joins and never touches meets. Finally, a maximum element is not a substitute for joins. "All rights" is an upper bound of every pair, so upper bounds always exist — but a least one need not. Having a top is a much weaker property than being a lattice, and assuming otherwise is how role hierarchies acquire merge rules nobody can justify.
- A role hierarchy has two roles whose only common super-roles are incomparable. What does that cost?There is no join, so "what does holding both grant?" has no derived answer. You must either add a role that is exactly the least upper bound, switch to ordering by primitive permission sets, or write down a policy and accept that it is a choice the hierarchy does not justify.
- Why does join being commutative and associative matter when parties merge independently?Because the merged result then depends only on which values were merged, not on the order or grouping. Parties that combine the same set of updates in different sequences reach the same value, and idempotence means re-applying an update already incorporated changes nothing.
- Is every finite partial order with a maximum element a lattice?No. A maximum guarantees that every pair has *an* upper bound, not a *least* one. Two elements can have several minimal upper bounds below that maximum, none comparable to the others, and then no join exists. The same argument applies downward for meets.
saying these in an interview costs you the question
- Calls any upper bound the join of two elements
- Assumes a hierarchy with a top element is automatically a lattice
- Says the join must be one of the two inputs
- Uses the meet to combine grants, silently restricting instead of combining
- Treats join as 'take the higher one' when neither dominates