Notation Family and Loss

The Operating System Concepts course counted a machine’s abstractions across fifteen lessons: the cost each abstraction imposed was measured, and no unfavorable result was hidden. What those measurements had in common was this — every one of them was the output of an executable text, and the run itself carried its correctness. Describing a system to someone else is not that. Describing means showing the system with less information; if the representation were the whole system, it would be a copy, not a description.

Showing with less information has a cost, and this course counts it. The maintenance workshop model has five associations and thirty-one facts; a structural representation that writes twenty of these becomes indistinguishable from 2047 other systems that produce the same drawing. The diagram is not wrong; it is incomplete, and the incompleteness does not show on the diagram itself.

The System Is Data; the Representation Is Its Projection

A single fictional domain is used throughout the course: a maintenance workshop. A work order is opened, split into line items, the line items require parts, a technician is assigned, the technician uses a machine, and the work order produces a document. This domain itself is not a diagram, it is data: associations, flows, prerequisites, states, and entities are each a Python structure. The representation is a projection of that data, and every projection discards information.

The projection measured in this lesson is the narrowest one: a structural representation that writes only an association’s source, target, direction, and multiplicity.

• SD1 — The system consists of five associations, and each association carries seven fields. Four show up in the representation (source, target, direction, multiplicity), three do not (lifecycle, ordered, unique).
• SD2 — On the side whose multiplicity is one, ordering and uniqueness are undefined. An N:1 association has one hidden field; 1:N and N:M associations have three; eleven in total across five associations.
• SD3 — Every hidden field takes a binary value: lifecycle is independent or dependent, ordered and unique are true or false.
• SD4 — The count is an exhaustive count. Every combination of hidden fields is generated, and the ones whose representation stays unchanged are counted; there is no estimate, sample, or randomness.

"""M01/K06 shared definition (excerpt): the system IS DATA, the representation is a
projection of that data. The fictional domain is a maintenance workshop. Every
association carries fields that SHOW UP and DO NOT SHOW UP in the representation."""
from itertools import product

ASSOCIATIONS = [
    {"name": "a1", "source": "WorkOrder", "target": "Technician", "direction": "one-way", "multiplicity": "N:1",
     "lifecycle": "independent", "ordered": False, "unique": True},
    {"name": "a2", "source": "WorkOrder", "target": "LineItem", "direction": "one-way", "multiplicity": "1:N",
     "lifecycle": "dependent",  "ordered": True,  "unique": False},
    {"name": "a3", "source": "LineItem",  "target": "Part", "direction": "one-way", "multiplicity": "N:1",
     "lifecycle": "independent", "ordered": False, "unique": True},
    {"name": "a4", "source": "Technician",   "target": "Machine", "direction": "two-way", "multiplicity": "N:M",
     "lifecycle": "independent", "ordered": False, "unique": True},
    {"name": "a5", "source": "WorkOrder", "target": "Document", "direction": "one-way", "multiplicity": "1:N",
     "lifecycle": "dependent",  "ordered": True,  "unique": True},
]


def hidden_fields(association):
    """On the side whose multiplicity is 1, ordering and uniqueness do not exist."""
    fields = ["lifecycle"]
    if association["multiplicity"] in ("1:N", "N:M"):
        fields += ["ordered", "unique"]
    return fields


def structural_view(associations, detail=0):
    """detail 0: source, target, direction, multiplicity. 1: + lifecycle. 2: + ordered and unique."""
    symbols = []
    for assoc in associations:
        s = {"source": assoc["source"], "target": assoc["target"], "direction": assoc["direction"], "multiplicity": assoc["multiplicity"]}
        if detail >= 1:
            s["lifecycle"] = assoc["lifecycle"]
        if detail >= 2:
            for field in hidden_fields(assoc):
                s[field] = assoc[field]
        symbols.append(s)
    return symbols


def symbol_count(view):
    return sum(len(s) for s in view)


def same_view_count(associations, detail=0):
    """How many distinct systems produce the same representation. The count is exhaustive."""
    options = {"lifecycle": ("independent", "dependent"), "ordered": (False, True),
               "unique": (False, True)}
    goal_view = structural_view(associations, detail)
    spaces = []
    for assoc in associations:
        fields = hidden_fields(assoc)
        spaces.append([dict(zip(fields, d)) for d in product(*[options[f] for f in fields])])
    count = 0
    for choice in product(*spaces):
        candidate = [dict(assoc, **c) for assoc, c in zip(associations, choice)]
        if structural_view(candidate, detail) == goal_view:
            count += 1
    return count


V = structural_view(ASSOCIATIONS, 0)
hidden = sum(len(hidden_fields(a)) for a in ASSOCIATIONS)
print("system :", "associations", len(ASSOCIATIONS), "| visible fields", symbol_count(V),
      "| hidden fields", hidden, "| total facts", symbol_count(V) + hidden)
print("view   :", symbol_count(V), "symbols")
print("cost   :", same_view_count(ASSOCIATIONS, 0), "systems collapse onto the same view")
print()
print("lines written:")
for s in V:
    print("  ", s["source"], s["direction"], s["target"], s["multiplicity"])
print()
print("a2 (WorkOrder -> LineItem), every option for the fields left unwritten:")
for lifecycle in ("independent", "dependent"):
    for ordered in (False, True):
        for unique in (False, True):
            candidate = [dict(a) for a in ASSOCIATIONS]
            candidate[1].update(lifecycle=lifecycle, ordered=ordered, unique=unique)
            print(f"   lifecycle={lifecycle:12s} ordered={str(ordered):5s} unique={str(unique):5s}"
                  f"  same view: {structural_view(candidate, 0) == V}")

system : associations 5 | visible fields 20 | hidden fields 11 | total facts 31
view   : 20 symbols
cost   : 2048 systems collapse onto the same view

lines written:
   WorkOrder one-way Technician N:1
   WorkOrder one-way LineItem 1:N
   LineItem one-way Part N:1
   Technician two-way Machine N:M
   WorkOrder one-way Document 1:N

a2 (WorkOrder -> LineItem), every option for the fields left unwritten:
   lifecycle=independent  ordered=False unique=False  same view: True
   lifecycle=independent  ordered=False unique=True   same view: True
   lifecycle=independent  ordered=True  unique=False  same view: True
   lifecycle=independent  ordered=True  unique=True   same view: True
   lifecycle=dependent    ordered=False unique=False  same view: True
   lifecycle=dependent    ordered=False unique=True   same view: True
   lifecycle=dependent    ordered=True  unique=False  same view: True
   lifecycle=dependent    ordered=True  unique=True   same view: True

Three numbers sit side by side here, and they will sit side by side in every lesson from here on. System: five associations, thirty-one facts. Representation: twenty symbols. Cost: 2048 systems collapsing onto the same representation — that is, the diagram that gets written is the shared picture of 2048 genuinely different systems.

An Unwritten Field Cannot Be Recovered

The output’s final block shows the cost on a single association. The a2 association carries a work order’s line items and sits in the representation as a single line: one-way from work order to line item, multiplicity 1:N. This line has three things it does not say. Do the line items live and die with the work order, or do they persist after the work order closes. Do the line items have an order, or are they a set. Can the same line item appear twice.

Three binary questions make eight options, and all eight produce exactly the same representation. Someone looking at the diagram cannot answer these three questions; the only place they can ask is the system itself. Taken together, the eleven hidden fields across the five associations give $2^{11} = 2048$.

The real point is not the size of the number but its direction. The projection is one-way: there is a single path from the system to the representation, and there are 2048 paths back from the representation to a system. Whoever reads the diagram has to pick one of these 2048 systems, and does not notice which one they picked, because the diagram does not say that a choice was made. This is the most expensive part of the loss: the loss itself is invisible on the representation.

The Notation Family: Structure, Behavior, Data

The notation family used in these lessons is defined in a specification, and its name is UML (Unified Modeling Language). The specification is the definition of a notation, not a tool: it fixes which element carries which meaning. The subject of this course is not the specification itself, but how much information the projections it permits discard.

The family splits into three groups, and all three are separate projections of the same system. Structural representations carry the system’s static relationships: which type relates to what, how many there are, in which runtime unit. Behavioral representations carry the system’s operation over time: messages, sequences, states, transitions. Data representations carry the stored facts: entities, attributes, relationships, constraints.

The table below places the loss of the three groups side by side. The structure row was measured in this lesson; the other two rows are among the shared definition’s verified readings and will be measured in detail in their respective topics.

Family	Facts in the system	What the representation carries	What cannot be recovered
Structure	5 associations, 31 fields	20 symbols	11 fields; 2048 systems collapse onto one diagram
Behavior	24 traces	one sequence diagram: 1 trace	23 traces; coverage 0.0417
Data	26 facts (5 entities, 12 attributes, 4 relationships, 5 constraints)	3 constraints carried into the relational structure	2 constraints are dropped, 114 decisions are not written in the model

None of the three rows covers the others, and combining all three still does not bring the system back. The family is not made of parts of a whole; it is three separate losses of the same whole.

The Architectural Decisions and Documentation course in the Software Architecture curriculum measured these types along a different axis: it mapped eighteen questions onto four types, and counted the information element the wrong type leaves out and the maintenance cost of each type. That course’s question was which type to choose. This course’s question is different, and it starts after the type has been chosen: how many systems the chosen type fails to distinguish from one another. The question-to-type mapping is not rebuilt here.

The Representation Grows Linearly, the Ambiguity Grows Exponentially

Per the shared definition’s resolution rule, every lesson tests its count with a second configuration. The test here is this: when a sixth association is added to the system, do the representation and the ambiguity grow at the same rate.

• SD5 — The added association adds four symbols to the representation; this is independent of its multiplicity.
• SD6 — The number of hidden fields for the added association depends on its multiplicity: one if N:1, three if 1:N or N:M.

"""Second configuration: adding one association, the representation and the ambiguity
do not grow at the same rate. The hidden field rule is from the shared definition:
lifecycle, ordered and unique if multiplicity is 1:N or N:M, otherwise only lifecycle.
Because the visible fields are fixed, the count of systems collapsing onto the same
view is the exhaustive count of the hidden field options."""
from itertools import product


def hidden_fields(multiplicity):
    return ["lifecycle", "ordered", "unique"] if multiplicity in ("1:N", "N:M") else ["lifecycle"]


def exhaustive_count(multiplicities):
    spaces = [list(product(*[(False, True)] * len(hidden_fields(m)))) for m in multiplicities]
    return sum(1 for _ in product(*spaces))


BASE = ["N:1", "1:N", "N:1", "N:M", "1:N"]
CONFIGURATIONS = [("five associations (base)", BASE),
                   ("+ Technician-Document   N:1", BASE + ["N:1"]),
                   ("+ Machine-Part          1:N", BASE + ["1:N"]),
                   ("+ LineItem-Machine      N:M", BASE + ["N:M"])]

print("configuration                assoc  symbols  hidden fields  same view")
for label, mults in CONFIGURATIONS:
    print(f"{label:28s}{len(mults):5d}{4 * len(mults):9d}"
          f"{sum(len(hidden_fields(m)) for m in mults):15d}{exhaustive_count(mults):11d}")
print()
base = exhaustive_count(BASE)
for label, mults in CONFIGURATIONS[1:]:
    print(f"{label:28s} symbols x{4 * len(mults) / 20:.2f}   ambiguity x{exhaustive_count(mults) // base}")

configuration                assoc  symbols  hidden fields  same view
five associations (base)        5       20             11       2048
+ Technician-Document   N:1     6       24             12       4096
+ Machine-Part          1:N     6       24             14      16384
+ LineItem-Machine      N:M     6       24             14      16384

+ Technician-Document   N:1  symbols x1.20   ambiguity x2
+ Machine-Part          1:N  symbols x1.20   ambiguity x8
+ LineItem-Machine      N:M  symbols x1.20   ambiguity x8

All three additions put the same number of symbols into the representation: four. The diagram grows by twenty percent in every case. The ambiguity, however, multiplies by two, eight, and eight. The same drawing effort turns 2048 into either 4096 or 16384, depending on which association was added.

The source of the difference is multiplicity. On the opposite side of an N:1 association, a single object sits; ordering and uniqueness cannot be asked there, so the only thing stored is the lifecycle field. On the opposite side of a 1:N or N:M association, a collection sits, and whether the collection has an order and whether it accepts repeats are two separate facts. The multiplicity symbol is therefore the most loaded symbol on the diagram: while it states one fact, it also announces that two more facts exist, and it does not write those two facts.

The representation grows linearly, with a fixed number of symbols per association; the ambiguity grows as the exponent of the hidden field count. That the share of the story the diagram tells shrinks as the system grows is not carelessness — it is the consequence of the gap between two growth rates.

The Cost of Removing a Symbol

The same measure works in reverse too. A twenty-symbol representation can be reduced to a fifteen-symbol one that does not write multiplicity; which associations connect to whom stays, how many of each drops.

• SD7 — When multiplicity is not written, an association’s multiplicity could be any of four options: 1:1, N:1, 1:N, or N:M. Because multiplicity is unknown, how many hidden fields depend on it is also unknown.

"""A narrower representation: what happens if the multiplicity symbol is never written.
Once multiplicity is unwritten, both the multiplicity itself and the hidden fields that
depend on it become unknown; the number of valid systems for one association is the sum,
over the four multiplicities, of their hidden field options."""
from itertools import product

MULTIPLICITIES = ("1:1", "N:1", "1:N", "N:M")


def hidden_fields(multiplicity):
    return ["lifecycle", "ordered", "unique"] if multiplicity in ("1:N", "N:M") else ["lifecycle"]


def association_options(multiplicity_written, multiplicity):
    """The number of systems that leave the representation unchanged for one association; exhaustive count."""
    count = 0
    for m in ([multiplicity] if multiplicity_written else list(MULTIPLICITIES)):
        for _ in product(*[(False, True)] * len(hidden_fields(m))):
            count += 1
    return count


BASE = ["N:1", "1:N", "N:1", "N:M", "1:N"]
results = {}
for written, symbols_per_assoc in ((True, 4), (False, 3)):
    total = 1
    for m in BASE:
        total *= association_options(written, m)
    results[written] = total
    print(f"multiplicity written {str(written):5s} | symbols {symbols_per_assoc * len(BASE):3d}"
          f" | same view count {total:9d}")
print("cost of removing 5 symbols: x", results[False] / results[True], sep="")

multiplicity written True  | symbols  20 | same view count      2048
multiplicity written False | symbols  15 | same view count   3200000
cost of removing 5 symbols: x1562.5

Five symbols are removed, and the ambiguity rises to 1562.5 times. The ratio means more than two bits per removed symbol; yet since every hidden field is binary, at most one bit per symbol would have been expected. The difference comes from multiplicity not being binary: leaving a field that can take four values unwritten costs two bits, and on top of that, because that field determines whether other fields exist at all, it also makes the structure itself ambiguous.

Removing a symbol from a representation can make it more readable, but readability is not a measured gain; 1562.5, on the other hand, is a measured cost. Until the two are written into the same table, simplification cannot be counted as an improvement.

The Course’s Rule

This lesson establishes the course’s measure: a representation’s count is not the symbols it carries, but the number of systems that collapse onto the same representation. A representation for which how many systems it fails to distinguish is not written counts as unmeasured. Twenty symbols is a diagram’s size; 2048 is its cost, and until the two are written together, nothing has actually been said about the diagram.

The measure’s resolution is also fixed here. The count is exhaustive, not a sample: there is no margin of error around 2048, and when comparing two representations, even a difference of one system is meaningful.

Summary

• A representation is an information-discarding projection of a system; there is a single path from the system to the representation and many paths back, and the loss itself is invisible on the representation.
• The maintenance workshop’s five associations carry 31 facts. The twenty-symbol, low-detail structural representation writes 20 of these, discards 11, and collapses $2^{11} = 2048$ distinct systems onto a single diagram.
• A single association’s three unwritten fields produce eight options, and all eight have exactly the same representation; whoever reads the diagram must make a choice and does not notice that they made one.
• The three groups of the notation family are three separate losses of the same system: structure discards 11 fields, behavior discards 23 of 24 traces, the data level discards 2 of 5 constraints, and combining all three still does not bring the system back.
• Adding a sixth association grows the representation by 4 symbols in every case, but multiplies the ambiguity by 2 or 8 depending on multiplicity: the representation grows linearly, the ambiguity grows exponentially.
• If multiplicity is never written, the representation drops from 20 symbols to 15, and the number of systems collapsing onto the same representation rises from 2048 to 3,200,000: 1562.5 times. Simplification’s gain is unmeasured; its cost is measured.

Next Step

Only the narrowest projection was measured in this lesson, and the number 2048 stands alone. Adding symbols to the diagram lowers this number — but by how much has not been measured. Does a symbol halve the ambiguity, take more than that, or are there symbols that take none at all.

The next lesson takes up the class diagram and counts it symbol by symbol: when the lifecycle symbol is added, 20 symbols become 25 — to what does 2048 drop, and how many systems remain once ordering and uniqueness notes are also written. The same lesson will measure which fact the distinction between composition and aggregation carries: what determines how many objects go away when a work order is deleted is a single symbol on the diagram.