Sequence Diagrams

The previous lesson measured a notation that deliberately closed off the inside of the system: seven internal steps never appeared in the notation, and 128 distinct systems collapsed into the same diagram. This lesson opens the inside up. The sequence notation lines participants up side by side, writes messages as arrows between them, and orders the arrows from top to bottom. Every message is written together with its sender, receiver, and sequence number.

At first glance this looks like the place where the loss closes up. It does not. The sequence notation closes one loss at the cost of another: while it shows one run of the system in full, it never shows every other run of the system at all. This lesson’s measure is the count of that “other.”

The Traces the System Produces

The repair shop’s flow branches at four points. Allocating stock can succeed, or it can fail and the work is held and retried. A suitable technician can be found, or none is found and the work is queued. A work order can carry one, two, or three line items. Document generation can be requested or not.

Because these four dimensions are independent, the system produces $2 \times 2 \times 3 \times 2 = 24$ distinct traces. A trace is the message sequence of one run from start to finish; their lengths range from six to twelve. A sequence diagram, by definition, draws one of these 24 sequences.

Measuring Coverage

The model below builds the shared reference’s flow and trace definitions exactly as they are, then adds the concept of a fragmented diagram on top (DD5): if a dimension is left “open,” the diagram draws that dimension not as a single fixed value but as an alternative or loop fragment, and covers every value of that dimension. The symbol count is the sum of participants, messages, fragments, and guard conditions.

"""Sequence notation: how many traces a diagram covers, how many it leaves
out. The FLOW and traces() definitions from the shared reference are built
exactly as they are there."""
from itertools import product

FLOW = {
    "start": [("Intake", "WorkOrder", "create"), ("WorkOrder", "Stock", "allocate")],
    "allocation_succeeded": [("WorkOrder", "Workshop", "schedule")],
    "allocation_failed": [("WorkOrder", "Intake", "hold"), ("WorkOrder", "Stock", "allocate")],
    "technician_found": [("Workshop", "Technician", "assign")],
    "no_technician": [("Workshop", "Intake", "queue"), ("Workshop", "Technician", "assign")],
    "each_item": [("Technician", "Item", "process")],
    "document": [("WorkOrder", "Document", "generate")],
    "finish": [("WorkOrder", "Intake", "close")],
}
ITEM_RANGE = (1, 2, 3)


def build_trace(allocation, technician, k, document):
    trace = list(FLOW["start"])
    if allocation == "failed":
        trace += FLOW["allocation_failed"]
    trace += FLOW["allocation_succeeded"]
    trace += FLOW["technician_found"] if technician == "found" else FLOW["no_technician"]
    trace += FLOW["each_item"] * k
    if document:
        trace += FLOW["document"]
    trace += FLOW["finish"]
    return tuple(trace)


def traces(item_range=ITEM_RANGE):
    return [build_trace(a, u, k, b)
            for a in ("succeeded", "failed") for u in ("found", "none")
            for k in item_range for b in (True, False)]


def coverage(diagrams, all_traces):
    covered = {g for g in diagrams if g in all_traces}
    return {"diagrams": len(diagrams), "covered": len(covered),
            "total": len(all_traces), "ratio": round(len(covered) / len(all_traces), 4)}


# ---- DD5: fragmented diagram. An open dimension is drawn with a fragment
# symbol; a closed dimension is fixed to a single value. Symbol count:
# participants + messages + fragments + guards.
PARTICIPANTS = 7   # Intake, WorkOrder, Stock, Workshop, Technician, Item, Document


def fragmented(open_dims, fixed=("succeeded", "found", 3, True), item_max=3):
    allocation, technician, k, document = fixed
    messages = len(FLOW["start"]) + len(FLOW["allocation_succeeded"]) + len(FLOW["finish"])
    fragments = guards = 0
    if "allocation" in open_dims:
        messages += len(FLOW["allocation_failed"]); fragments += 1; guards += 2
    elif allocation == "failed":
        messages += len(FLOW["allocation_failed"])
    if "technician" in open_dims:
        messages += len(FLOW["technician_found"]) + len(FLOW["no_technician"]); fragments += 1; guards += 2
    else:
        messages += len(FLOW["technician_found"] if technician == "found" else FLOW["no_technician"])
    if "item" in open_dims:
        messages += 1; fragments += 1; guards += 1
    else:
        messages += k
    if "document" in open_dims:
        messages += 1; fragments += 1; guards += 1
    elif document:
        messages += 1
    accepted = [build_trace(a, u, kk, b)
                for a in (("succeeded", "failed") if "allocation" in open_dims else (allocation,))
                for u in (("found", "none") if "technician" in open_dims else (technician,))
                for kk in (range(1, item_max + 1) if "item" in open_dims else (k,))
                for b in ((True, False) if "document" in open_dims else (document,))]
    return {"symbols": PARTICIPANTS + messages + fragments + guards, "messages": messages,
            "fragments": fragments, "accepted": accepted}


def flat_symbols(trace):
    """The symbol count of an unfragmented sequence diagram: participants + drawn messages."""
    return PARTICIPANTS + len(trace)


TRACES = traces()
print("SYSTEM  :", len(TRACES), "traces | lengths:", sorted({len(i) for i in TRACES}))
print("NOTATION:", fragmented(())["symbols"], "symbols (unfragmented, single trace)")
print("COST    :", len(TRACES) - 1, "traces never enter the notation")
print()
for n in (1, 2, 3, 4):
    k = coverage([tuple(i) for i in TRACES[:n]], TRACES)
    print(f"  {n} unfragmented diagram(s) -> coverage {k['covered']}/{k['total']}"
          f" = {k['ratio']} | symbols {sum(flat_symbols(i) for i in TRACES[:n])}")
print()
print("as fragments are added")
print(f"{'open dimension':36s} symbols  covered  coverage  symbols/trace")
accumulated = ()
for dim in ("item", "document", "allocation", "technician"):
    accumulated += (dim,)
    p = fragmented(accumulated)
    cov = coverage(p["accepted"], TRACES)
    print(f"{'+'.join(accumulated):36s} {p['symbols']:5d} {cov['covered']:9d}"
          f"  {cov['ratio']:6} {p['symbols'] / cov['covered']:9.2f}")
print()
print("covering all 24 traces unfragmented:", sum(flat_symbols(i) for i in TRACES),
      "symbols | covering with fragments:",
      fragmented(("item", "document", "allocation", "technician"))["symbols"], "symbols")
print()
# DD6: if the loop bound [1..*] is written. Comparison window item <= 6.
open_dims = ("item", "document", "allocation", "technician")
for limit, label in ((3, "loop bound [1..3]"), (6, "loop bound [1..*]")):
    p = fragmented(open_dims, item_max=limit)
    cov = coverage(p["accepted"], TRACES)
    over = [i for i in p["accepted"] if i not in TRACES]
    print(f"{label:22s} accepts {len(p['accepted']):3d} | coverage"
          f" {cov['covered']}/{cov['total']} = {cov['ratio']} | over-approximation {len(over)}")
print()
# DD7: if the TRACE SET grew without the system changing. A workshop with an item range of 1..6.
TRACES6 = traces((1, 2, 3, 4, 5, 6))
single = [build_trace("succeeded", "found", 3, True)]
p3 = fragmented(open_dims, item_max=3)
print("the same two diagrams, if the trace set were", len(TRACES), "instead of", len(TRACES6))
for label, g in (("unfragmented single trace", single), ("four-fragment diagram", p3["accepted"])):
    a, b = coverage(g, TRACES), coverage(g, TRACES6)
    print(f"  {label:22s} coverage {a['covered']}/{a['total']} = {a['ratio']}"
          f"  ->  {b['covered']}/{b['total']} = {b['ratio']}")
print()
# DD8: every message kind is synchronous or asynchronous. How many systems
# collapse if the notation does not write it.
MESSAGE_KINDS = sorted({m[2] for a in FLOW.values() for m in a})
REAL_MODE = {x: ("asynchronous" if x in ("generate", "queue") else "synchronous")
             for x in MESSAGE_KINDS}


def mode_notation(mode, written):
    return tuple(mode[x] if x in written else None for x in MESSAGE_KINDS)


def modes_collapsed(written):
    target = mode_notation(REAL_MODE, written)
    return sum(1 for s in product(("synchronous", "asynchronous"), repeat=len(MESSAGE_KINDS))
               if mode_notation(dict(zip(MESSAGE_KINDS, s)), written) == target)


full = fragmented(open_dims, item_max=3)["symbols"]
print("the diagram with coverage 1.0 has", len(MESSAGE_KINDS), "message kinds")
for label, written in (("mode never written", ()),
                       ("only the two asynchronous modes written", ("generate", "queue")),
                       ("all nine of the nine modes written", tuple(MESSAGE_KINDS))):
    print(f"  {label:34s} symbols {full + len(written):3d}"
          f" | collapse into the same notation {modes_collapsed(written):4d}")

SYSTEM  : 24 traces | lengths: [6, 7, 8, 9, 10, 11, 12]
NOTATION: 16 symbols (unfragmented, single trace)
COST    : 23 traces never enter the notation

  1 unfragmented diagram(s) -> coverage 1/24 = 0.0417 | symbols 14
  2 unfragmented diagram(s) -> coverage 2/24 = 0.0833 | symbols 27
  3 unfragmented diagram(s) -> coverage 3/24 = 0.125 | symbols 42
  4 unfragmented diagram(s) -> coverage 4/24 = 0.1667 | symbols 56

as fragments are added
open dimension                       symbols  covered  coverage  symbols/trace
item                                    16         3   0.125      5.33
item+document                           18         6    0.25      3.00
item+document+allocation                23        12     0.5      1.92
item+document+allocation+technician     28        24     1.0      1.17

covering all 24 traces unfragmented: 384 symbols | covering with fragments: 28 symbols

loop bound [1..3]      accepts  24 | coverage 24/24 = 1.0 | over-approximation 0
loop bound [1..*]      accepts  48 | coverage 24/24 = 1.0 | over-approximation 24

the same two diagrams, if the trace set were 24 instead of 48
  unfragmented single trace coverage 1/24 = 0.0417  ->  1/48 = 0.0208
  four-fragment diagram  coverage 24/24 = 1.0  ->  24/48 = 0.5

the diagram with coverage 1.0 has 9 message kinds
  mode never written                 symbols  28 | collapse into the same notation  512
  only the two asynchronous modes written symbols  30 | collapse into the same notation  128
  all nine of the nine modes written symbols  37 | collapse into the same notation    1

Three numbers: the system has 24 traces, the notation has 16 symbols, the cost is 23 traces that never enter the notation. Coverage is 1/24, that is, 0.0417.

Four Diagrams Are Not Enough

Coverage grows linearly. Two diagrams give 2/24 = 0.0833, three give 3/24 = 0.125, four give 4/24 = 0.1667. Every new diagram adds exactly one trace, because each is a single run and runs do not substitute for one another.

Covering all twenty-four traces with unfragmented diagrams requires 384 symbols. This is the total message count plus the participant list repeated twenty-four times. No one reads a document like that; this is why sequence diagrams stay, in practice, limited to three or five of them, and those three or five mean a coverage of around 0.125.

The sentence that follows is this: a set of sequence diagrams does not show the system, it shows a few examples from the system. Which examples are chosen is a choice, and that choice is not written in the notation — a reader holding four traces cannot read from the diagram which four of the 24 they are.

Fragment Symbols Grow Coverage Per Symbol

The middle table measures another path. When the loop fragment is opened, the item dimension is not fixed to a single value: instead of three messages, one message and one loop fragment are drawn. The symbol count stays at 16 — the same as the unfragmented diagram — but the covered traces rise from 1 to 3.

The next three rows proceed the same way. Once optional document generation is placed in a fragment, 18 symbols cover 6 traces. Once the two branches of allocation are placed in an alternative fragment, 23 symbols cover 12. Once the two branches of finding a technician are added as well, 28 symbols cover all 24 traces. Symbols per trace drop from 5.33 to 1.17; achieving the same coverage unfragmented would need 384 symbols, while the fragmented notation finishes with 28 symbols, roughly fourteen times fewer.

This does not mean the fragmented notation is free. An unfragmented diagram is a single top-to-bottom reading; a fragmented diagram asks the reader to make a choice at each of the four fragments, and the number of readings rises to 24. Coverage was gained, single readability was given up. What the notation states also changed: an unfragmented diagram says “such a run occurred”; a fragmented diagram says “these runs can occur.” The first is an observation, the second a claim, and the claim can be wrong.

Coverage Is Not a Quality Measure

The bottom two blocks give two separate proofs of this.

First: if no upper bound is written on the loop fragment (DD6) — that is, if “one or more items” is stated without an upper bound — coverage stays at 24/24 = 1.0, but the number of sequences the diagram accepts rises from 24 to 48. Twenty-four are real, twenty-four are sequences that do not exist in the system: work orders with four, five, or six items. Over-approximation rose from 0 to 24, and coverage did not change at all. Coverage answers only the question “how many of the real traces were shown”; it does not answer “how many of the shown traces are real,” and a notation is not considered measured until the second question is asked as well.

Second: as the trace set grows, the ratio drops with the notation completely unchanged. In a workshop where the item range is one to six instead of three (DD7), the same system produces 48 traces. The unfragmented single diagram’s coverage drops from 0.0417 to 0.0208, the four-fragment diagram’s coverage from 1.0 to 0.5. Not a single symbol was added to the diagrams, not a single symbol was removed.

For this reason a coverage ratio is never written alone anywhere. “Coverage 0.5” carries no information; “24 of 48 traces” does. The ratio is a number that depends on the size of the denominator, and comparison is impossible when the denominator is not written.

A Covered Trace Can Also Be Written Incompletely

Coverage measures whether a trace was drawn, not how it was drawn. The final block counts this second axis. The sequence notation can write every message with a mode: synchronous if the caller waits for a reply, asynchronous if it does not. This is a binary decision for each of the flow’s nine distinct message kinds, and in the workshop two of them are asynchronous — document generation and queuing (DD8).

The 28-symbol diagram with coverage 1.0 writes none of these nine decisions. The result: 512 distinct systems collapse into the same diagram. The diagram covers every trace and still does not say which system it shows. Once the two asynchronous modes are written, the number drops to 128; once all nine are written, it drops to 1 — the cost is going from 28 symbols to 37.

The two axes are independent, and a notation is not considered measured until both are written separately. The first is the question of which traces, and coverage is its answer. The second is the question of how much of each trace, and the number of systems collapsing into the same notation is its answer. A notation can score perfectly on the first and stay at 512 on the second; the reverse also happens — a diagram that writes a single trace with every one of its fields is 1 on the second axis and 0.0417 on the first.

Summary

• The repair shop’s flow produces 24 traces through four independent branch points; a sequence diagram, by definition, draws one of these traces, giving a coverage of 1/24 = 0.0417 and leaving 23 traces out.
• Coverage grows linearly with the number of unfragmented diagrams: four diagrams give 4/24 = 0.1667 and 56 symbols. Covering all 24 traces unfragmented requires 384 symbols.
• Loop and alternative fragments grow coverage per symbol: 16 symbols for 3 traces, 18 for 6, 23 for 12, 28 for 24. Symbols per trace drop from 5.33 to 1.17.
• The fragmented notation trades away single readability: four fragments ask the reader to make four choices, and the number of possible readings rises to 24. The notation stops being an observation and becomes a claim.
• Coverage of 1.0 is not a measure of success: when the loop bound is left unwritten, coverage stays at 1.0 while over-approximation rises from 0 to 24; when the trace set grows from 24 to 48, the same diagrams’ coverage drops from 0.0417 to 0.0208 and from 1.0 to 0.5.
• Coverage and ambiguity are separate axes: the 28-symbol diagram with coverage 1.0 cannot distinguish 512 systems because it does not write the mode of nine messages; once all nine are written, it drops to 1 with 37 symbols.

Next Step

The sequence notation never asked one question: could these messages have gone in another order. Every diagram writes a single order and shows that order as if it were mandatory. Yet most of the work in the shop does not wait on the rest; there is no priority between informing the customer and computing the cost, and the two can be done in either order.

The next notation writes exactly this: it writes the prerequisites between tasks, not the order. Ten tasks and thirteen prerequisites determine which orders are valid, and the number of such orders is how many distinct outputs the topological sort from the Data Structures course can produce. The number is 168. An activity diagram does not accept a single execution order but all 168 execution orders at once — and unless the number of that looseness is written, the reader mistakes it for certainty.