The Entity–Relationship Model

The previous lesson represented a work order’s behavior over time with four states and six transitions. The measure was the gap between the language the machine accepts and the system’s real traces: two sequences were rejected, two sequences absent from the system were accepted, and when two transitions were added, rejection dropped to zero while over-acceptance rose from 2 to 26. That representation described what the system does.

This topic takes up the representation that describes what the system holds. Its question has the same shape: writing the domain’s data structure in terms of entities, attributes, and relationships states how many facts, and leaves how many unstated. The relational model, key types, integrity constraints, and normalization are not taught here; they were established in the Data Modeling and Relational Theory course of the Databases curriculum and are not repeated. The only task here is counting the facts that a change of level drops and invents.

Entity, Attribute, Relationship

An entity is a concept in the domain that has an identity of its own: a work order, a technician, a part. An attribute is a single-valued fact carried by an entity: a work order’s opening date, a technician’s specialty. A relationship is a link between two entities and carries a cardinality — a label stating which side is one and which side is many.

The term entity here names a carrier of identity; the entity object used in the Databases curriculum, by contrast, is a programming object in the domain layer and is a separate concept.

• VM1 — The modeled domain is a maintenance shop, and the system is data. No modeling tool, drawing product, or data storage product is invoked; what is measured is the data itself.
• VM2 — The conceptual model’s fact count is the sum of the counts of entities, attributes, relationships, and constraints. Every fact is counted once.

"""M01/K06 common definition (excerpt): the conceptual entity-relationship model and fact counting."""
CONSTRAINTS = [
    {"text": "every work order has a single technician",      "tool": "foreign key"},
    {"text": "part code is unique",                            "tool": "uniqueness"},
    {"text": "a document belongs only to its own work order",  "tool": "foreign key"},
    {"text": "a work order requires at least one part",        "tool": None},
    {"text": "a technician is at only one machine at a time",  "tool": None},
]
CONCEPTUAL = {
    "entities": ["WorkOrder", "Technician", "Part", "Machine", "Document"],
    "attributes": {"WorkOrder": ["number", "opened", "status"], "Technician": ["name", "specialty"],
                   "Part": ["code", "name", "unit"], "Machine": ["code", "type"],
                   "Document": ["type", "date"]},
    "relationships": [("WorkOrder", "Technician", "N:1"), ("WorkOrder", "Part", "N:M"),
                       ("Technician", "Machine", "N:M"), ("WorkOrder", "Document", "1:N")],
    "constraints": CONSTRAINTS,
}


def facts(model):
    e = len(model["entities"])
    attr = sum(len(v) for v in model["attributes"].values())
    r = len(model["relationships"])
    c = len(model["constraints"])
    return {"entity": e, "attribute": attr, "relationship": r, "constraint": c, "total": e + attr + r + c}


print("conceptual model:", facts(CONCEPTUAL))
print()
print("entity      attributes  relationships involved")
for name in CONCEPTUAL["entities"]:
    links = [f"{a}-{b} {c}" for a, b, c in CONCEPTUAL["relationships"] if name in (a, b)]
    print(f"{name:10s}  {len(CONCEPTUAL['attributes'][name]):9d}  {', '.join(links)}")

conceptual model: {'entity': 5, 'attribute': 12, 'relationship': 4, 'constraint': 5, 'total': 26}

entity      attributes  relationships involved
WorkOrder           3  WorkOrder-Technician N:1, WorkOrder-Part N:M, WorkOrder-Document 1:N
Technician          2  WorkOrder-Technician N:1, Technician-Machine N:M
Part                3  WorkOrder-Part N:M
Machine             2  Technician-Machine N:M
Document            2  WorkOrder-Document 1:N

System: the maintenance shop’s conceptual model states 26 facts. Notation: the same 26 items are written into the diagram — five entity boxes, twelve attributes, four relationship lines, and five constraint notes. It looks like a one-to-one match. The cost is what falls outside this match, and it will be counted in the next section.

What Cardinality States, What Multiplicity Adds

In this course, two separate terms carry two separate pieces of information, and confusing them corrupts the measurement. Cardinality is the label of the entity–relationship notation and is written on the relationship as a whole: N:1, 1:N, N:M. What it states is the upper bound at each end — which side can have at most one, which side can have an unbounded number. Multiplicity, on the other hand, is the label of the structural notation and is written separately on each end of the relationship; its form is a lower..upper range.

The difference is exactly this: cardinality states the upper bounds, multiplicity adds the lower bound alongside the upper bound. The lower bound is whether that end’s participation is mandatory or optional. The N:1 label states that a work order has at most one technician; it does not state whether a work order can be opened without a technician.

• VM3 — Every relationship has two ends, and each end participates mandatorily or optionally, independently. Cardinality carries only the upper bounds.
• VM4 — Every attribute is independently mandatory or optional. The participation space and the requiredness space are independent of each other; the total count is their product.
• VM5 — The count is exhaustive, not a sample; even a difference of one system is meaningful.

"""What cardinality writes, what multiplicity adds: how many systems fall onto the same notation."""
from itertools import product

RELATIONSHIPS = [("WorkOrder", "Technician", "N:1"), ("WorkOrder", "Part", "N:M"),
                  ("Technician", "Machine", "N:M"), ("WorkOrder", "Document", "1:N")]
UPPER = {"N:1": ("*", "1"), "1:N": ("1", "*"), "N:M": ("*", "*"), "1:1": ("1", "1")}
ATTRIBUTES = 12          # the conceptual model's 12 attributes


def er_notation(system, multiplicity=False):
    """system: a list of (source, target, cardinality, lower_source, lower_target)."""
    written = []
    for source, target, card, lower_s, lower_t in system:
        entry = {"source": source, "target": target, "cardinality": card}
        if multiplicity:
            upper_s, upper_t = UPPER[card]
            entry["multiplicity_source"] = f"{lower_s}..{upper_s}"
            entry["multiplicity_target"] = f"{lower_t}..{upper_t}"
        written.append(entry)
    return written


def same_notation_count(system, multiplicity=False):
    """Exhaustive count: how many separate participation choices produce the same notation."""
    target_notation = er_notation(system, multiplicity)
    count = 0
    for choice in product((0, 1), repeat=2 * len(system)):
        candidate = [(s, t, c, choice[2 * i], choice[2 * i + 1])
                     for i, (s, t, c, _, _) in enumerate(system)]
        if er_notation(candidate, multiplicity) == target_notation:
            count += 1
    return count


SYSTEM = [(s, t, c, 1, 1) for s, t, c in RELATIONSHIPS]
print("relationship ends:", 2 * len(SYSTEM), "| unwritten participation bits:", 2 * len(SYSTEM))
print("cardinality written, multiplicity not written ->",
      same_notation_count(SYSTEM, multiplicity=False), "systems")
print("multiplicity written                          ->",
      same_notation_count(SYSTEM, multiplicity=True), "systems")
print()
attribute_space = sum(1 for _ in product((0, 1), repeat=ATTRIBUTES))
print("attribute requiredness not written ->", attribute_space, "systems")
print("the two spaces are independent, product ->",
      same_notation_count(SYSTEM) * attribute_space, "systems")
print()
print("written items  what was added                    falls onto same notation")
print(f"           26  entity+attribute+relationship+constraint  "
      f"{same_notation_count(SYSTEM) * attribute_space:20d}")
print(f"           34  + 8 participation marks                   "
      f"{same_notation_count(SYSTEM, True) * attribute_space:20d}")
print(f"           46  + 12 requiredness marks                   {1:20d}")

relationship ends: 8 | unwritten participation bits: 8
cardinality written, multiplicity not written -> 256 systems
multiplicity written                          -> 1 systems

attribute requiredness not written -> 4096 systems
the two spaces are independent, product -> 1048576 systems

written items  what was added                    falls onto same notation
           26  entity+attribute+relationship+constraint               1048576
           34  + 8 participation marks                                   4096
           46  + 12 requiredness marks                                      1

This is the cost. A conceptual model written with twenty-six facts cannot be distinguished from 1,048,576 other systems that resemble it. This number comes from two independent sources: the participation information at the eight ends of the four relationships (256), and the requiredness information of the twelve attributes (4096). Neither is written in the notation, but both are determinate in the system.

The “every symbol is a bit” relationship measured in the Structural Diagrams topic holds here too; it is not repeated. What this lesson adds is which bits are dropped, and this choice is not random: the entity–relationship notation was historically designed to carry cardinality, not to carry participation. The twenty dropped bits do not vanish — as will soon be seen, at the logical and physical levels they turn into a decision someone else will make. Whether an attribute is mandatory will reappear at the physical level under the name “nullability,” and giving an answer at that level will be mandatory.

Entity or Attribute

The most frequently made decision in the model is whether a fact will be its own entity or an attribute of another entity. This decision is not a matter of style; it changes, together, the number of facts the model can state and the number of states it can represent.

• VM6 — The pool of documents that can be attached to a work order has four candidates. The entity form can represent any subset of this pool; the attribute form carries a single value, that is, at most one item.
• VM7 — When the unit attribute is promoted to its own entity, the value set closes, and the constraint “unit only from the defined set” becomes statable.

"""Same domain, two separate entity-attribute decisions: how many facts change, how many states are lost."""
from itertools import combinations

CONCEPTUAL = {
    "entities": ["WorkOrder", "Technician", "Part", "Machine", "Document"],
    "attributes": {"WorkOrder": ["number", "opened", "status"], "Technician": ["name", "specialty"],
                   "Part": ["code", "name", "unit"], "Machine": ["code", "type"],
                   "Document": ["type", "date"]},
    "relationships": [("WorkOrder", "Technician", "N:1"), ("WorkOrder", "Part", "N:M"),
                       ("Technician", "Machine", "N:M"), ("WorkOrder", "Document", "1:N")],
    "constraints": 5,
}
DEMOTED = {                          # Document steps down from entity to attribute
    "entities": ["WorkOrder", "Technician", "Part", "Machine"],
    "attributes": {"WorkOrder": ["number", "opened", "status", "document"], "Technician": ["name", "specialty"],
                   "Part": ["code", "name", "unit"], "Machine": ["code", "type"]},
    "relationships": [("WorkOrder", "Technician", "N:1"), ("WorkOrder", "Part", "N:M"),
                       ("Technician", "Machine", "N:M")],
    "constraints": 4,                # "a document belongs only to its own work order" cannot be stated
}
PROMOTED = {                         # unit steps up from attribute to entity
    "entities": ["WorkOrder", "Technician", "Part", "Machine", "Document", "Unit"],
    "attributes": {"WorkOrder": ["number", "opened", "status"], "Technician": ["name", "specialty"],
                   "Part": ["code", "name"], "Machine": ["code", "type"],
                   "Document": ["type", "date"], "Unit": ["name"]},
    "relationships": [("WorkOrder", "Technician", "N:1"), ("WorkOrder", "Part", "N:M"),
                       ("Technician", "Machine", "N:M"), ("WorkOrder", "Document", "1:N"),
                       ("Part", "Unit", "N:1")],
    "constraints": 6,                # "unit only from the defined set" can now be stated
}


def facts(model):
    return (len(model["entities"]) + sum(len(a) for a in model["attributes"].values())
            + len(model["relationships"]) + model["constraints"])


print("decision            entity  attribute  relationship  constraint  facts")
for name, m in (("common definition", CONCEPTUAL), ("Document to attribute", DEMOTED),
                ("unit to entity", PROMOTED)):
    print(f"{name:22s}  {len(m['entities']):6d}  "
          f"{sum(len(a) for a in m['attributes'].values()):9d}  "
          f"{len(m['relationships']):12d}  {m['constraints']:10d}  {facts(m):5d}")
print()
CANDIDATE = ("acceptance form", "fault report", "test record", "delivery report")
all_states = [k for n in range(len(CANDIDATE) + 1) for k in combinations(CANDIDATE, n)]
single_valued = [d for d in all_states if len(d) <= 1]
print("a work order's document state -> total", len(all_states),
      "| entity form shows:", len(all_states),
      "| attribute form:", len(single_valued))
print("states that become unrepresentable:", len(all_states) - len(single_valued))

decision            entity  attribute  relationship  constraint  facts
common definition            5         12             4           5     26
Document to attribute        4         11             3           4     22
unit to entity               6         12             5           6     29

a work order's document state -> total 16 | entity form shows: 16 | attribute form: 5
states that become unrepresentable: 11

Demoting the document to an attribute drops the model from 26 facts to 22 facts: one entity, one attribute, one relationship, and one constraint disappear. The constraint that disappears is “a document belongs only to its own work order,” and the reason is structural — since the document is no longer a separate thing, the question of whose it is can no longer be asked. The heavier consequence is in the second row: of the 16 possible states for a work order’s document status, 11 can no longer be represented, because a single-valued attribute can only stay empty or carry a single document.

The opposite direction is not free either. Promoting the unit attribute to its own entity raises the fact count from 26 to 29: one entity, one relationship, and one constraint are added. The payoff is concrete — the set of unit values closes, meaning a unit not defined in the model cannot be written. The cost of promotion is three facts’ worth of extra maintenance load; the cost of demotion is four facts’ worth of loss and eleven unrepresentable states. Neither is free, and both are countable.

A decision criterion follows from this, and the criterion is not a matter of taste but the answer to three questions. Whether a fact deserves to be its own entity is judged by: does it have its own attributes, does it need to be referred to on its own, and can it connect to a parent entity more than once. Document answers yes to all three — it has a type and a date, the work order it belongs to can be asked, and a work order carries more than one document. unit, however, answers no on the third: a part has a single unit. This is why promoting unit does not change the number of representable states at all; it only gains a constraint and adds three facts. The decision is a comparison between the constraint gained and the fact added.

Constraints Are Facts Too

Five of the twenty-six facts are constraints, and they live not in the diagram’s lines but in notes written beside it. This distinction is the notation’s weakest point: the box and the arrow are part of a formal visual language and are processed mechanically, while the note is free text. Three of the five constraints can be written with the relational structure’s tools, two cannot — which is which, and the structural reason for the inability, is the subject of the next lesson.

Looking at the shape of two constraints already hints at where the difference comes from. “Part code is unique” looks at a single column and compares two rows. “A work order requires at least one part,” however, cannot be answered by looking at a single row; it asks about the number of rows attached to a work order. The third is further still: “a technician is at only one machine at a time” asks whether two rows’ time intervals intersect, and the conceptual model has no attribute called time. The three constraints are three separate kinds of predicate; that one can be written does not mean the other can be too.

What must be noted for now is this: a constraint, as long as it is a note in the notation, is a fact of the model; but if it cannot be converted into a transportable structure on the way down from the notation to the schema, it disappears without anyone deleting it.

Summary

• The conceptual model states 26 facts for the maintenance shop: 5 entities, 12 attributes, 4 relationships, 5 constraints. Fact counting is this topic’s unit of measure.
• Cardinality is written on the relationship as a whole and states only the upper bounds; multiplicity is written separately on each end and also carries the lower bound, that is, participation. The difference is two bits per relationship.
• When cardinality is written but participation and attribute requiredness are not, 1,048,576 systems fall onto the same notation: the product of 256 participation choices and 4096 requiredness choices. Adding eight participation marks leaves 4096; adding all twelve requiredness marks as well leaves 1.
• Modeling a fact as an attribute instead of an entity reduces the model from 26 facts to 22 and makes 11 of a work order’s 16 document states unrepresentable; promoting in the opposite direction raises the fact count to 29 and makes a constraint statable.
• Constraints are facts of the model too, but because they stand as notes in the diagram, whether they carry over depends not on the formal visual language but on the tools of the next level.

Next Step

This lesson kept the model at a single level and counted what that level does not state. The next lesson changes the level: as the same 26 facts are converted into a relational structure, two N:M relationships open into a junction table, the table count rises from 5 to 7, and two of the five constraints drop. Why the two dropped constraints drop is not guessed at; which tool cannot write which predicate is shown by exhaustive count.