Conceptual, Logical, and Physical Model

The previous lesson kept the conceptual model at a single level and counted what that level did not state: twenty-six facts were written, but because participation and attribute requiredness were not written, more than a million systems fell onto the same notation. This lesson changes the level.

Its question is this: when the same twenty-six facts are converted into a relational structure, how much carries over as is, how much drops, and how much appears that never was written in the model. Three numbers will again stand side by side, but this time the cost has two separate components: the dropped constraint and the invented field. They are counted separately, because one is a loss and the other an addition.

Three Levels

The conceptual model carries the domain’s facts and contains no storage decision: entity, attribute, relationship, constraint. The logical model converts these facts into the structures of a particular data model; here that structure is relational, meaning table, field, key, and foreign key. The physical model makes the same structure storable: type, length, nullability, index. None of the three levels contains a product name; even the physical level carries kinds of decision, not a product.

• VM8 — The three levels sit on top of one another, and the number of decisions grows as you go down. Everything a level does not state is either derived or invented at the level below.
• VM9 — The conceptual-to-logical rule is fixed: every entity converts to a table, every N:M relationship opens into a junction table, every N:1 and 1:N relationship becomes a foreign key field placed on the many side, and every table gets a primary key field added.
• VM10 — A constraint carries over if it can be written with one of the relational structure’s tools — key, uniqueness, or foreign key; it drops if it cannot.

Key types, foreign-key delete and update actions, integrity constraints, and normalization are not taught in this lesson; all of them were established in the Databases curriculum’s Data Modeling and Relational Theory course. Here those tools are used only as carriers, and the only question asked is which fact carries over and which does not.

"""M01/K06 common definition (excerpt): the conceptual-to-logical transition and its balance sheet."""
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 logical(conceptual):
    """N:M relationships open into a junction table; constraints are split by transportability."""
    tables = {}
    for e in conceptual["entities"]:
        tables[e] = ["key"] + list(conceptual["attributes"][e])
    junction = []
    for s, t, card in conceptual["relationships"]:
        if card == "N:M":
            name = f"{s}_{t}"
            tables[name] = ["key", f"{s}_key", f"{t}_key"]
            junction.append(name)
        elif card == "N:1":
            tables[s].append(f"{t}_key")
        else:
            tables[t].append(f"{s}_key")
    carried = [k for k in conceptual["constraints"] if k["tool"]]
    dropped = [k for k in conceptual["constraints"] if not k["tool"]]
    return {"tables": tables, "junction_tables": junction, "carried": carried, "dropped": dropped}


L = logical(CONCEPTUAL)
print("table           fields  field names")
for name, fields in L["tables"].items():
    print(f"{name:20s}  {len(fields):4d}  {', '.join(fields)}")
print()
field = sum(len(v) for v in L["tables"].values())
attribute = sum(len(a) for a in CONCEPTUAL["attributes"].values())
key = sum(v.count("key") for v in L["tables"].values())
foreign = sum(1 for v in L["tables"].values() for a in v if a.endswith("_key"))
print("entity", len(CONCEPTUAL["entities"]), "-> table", len(L["tables"]),
      "( junction table:", ", ".join(L["junction_tables"]), ")")
print("attribute", attribute, "-> field", field,
      "| field never named in the conceptual model:", field - attribute)
print("  ", key, "primary key +", foreign, "foreign key =", key + foreign)
print("constraint", len(CONSTRAINTS), "-> carried", len(L["carried"]), "| dropped", len(L["dropped"]))
for k in L["dropped"]:
    print("   DROPPED:", k["text"])

table           fields  field names
WorkOrder                5  key, number, opened, status, Technician_key
Technician               3  key, name, specialty
Part                     4  key, code, name, unit
Machine                  3  key, code, type
Document                 4  key, type, date, WorkOrder_key
WorkOrder_Part           3  key, WorkOrder_key, Part_key
Technician_Machine       3  key, Technician_key, Machine_key

entity 5 -> table 7 ( junction table: WorkOrder_Part, Technician_Machine )
attribute 12 -> field 25 | field never named in the conceptual model: 13
   7 primary key + 6 foreign key = 13
constraint 5 -> carried 3 | dropped 2
   DROPPED: a work order requires at least one part
   DROPPED: a technician is at only one machine at a time

System: 26 facts. Notation: 7 tables and 25 fields. Cost: 2 dropped constraints and 13 invented fields. The third number gets the least attention but is the most revealing: the logical model carries thirteen fields whose name the conceptual model never mentions. Seven are the tables’ primary keys, six are the foreign keys that establish the relationships. None of these is a fact of the domain — nobody in the shop talks about a work order’s “key.” These are the relational structure’s own record-keeping apparatus, and they come from the level, not from the model.

The table count rising from 5 to 7 comes from the same place. A relational structure cannot hold an N:M relationship directly; it requires a junction table carrying the keys of both sides. Because there are two N:M relationships, two junction tables are born, and the field count rises by six. This is not a design preference; it is the direct consequence of the relational structure’s expressive limit.

Why the Two Dropped Constraints Drop

Three of the five constraints carry over: “every work order has a single technician” can be written with a foreign key, “part code is unique” with a uniqueness constraint, “a document belongs only to its own work order” again with a foreign key. The remaining two drop, and the reason for dropping is not forgetfulness but the type of the predicate.

The key, uniqueness, and foreign-key tools all have the same shape: they either look at a single row, or they compare the equality of specific fields across two rows. The two dropped constraints fall outside these two shapes. “A work order requires at least one part” cannot be answered by looking at a single row; it looks at the number of rows attached to a work order and needs a lower bound on that number. “A technician is at only one machine at a time” asks whether two rows’ time intervals intersect, whereas uniqueness sees only equality.

• VM11 — The over-acceptance count uses two work orders, two parts, two technicians, and two machines. The sample space is every subset of rows the junction table could take; the count is exhaustive.
• VM12 — The instances show a state at a single instant; the table has no time field.

"""Why the two dropped constraints drop: which predicate the relational tool cannot write."""
from itertools import combinations, product

WORK_ORDER, PART = ("o1", "o2"), ("p1", "p2")
TECHNICIAN, MACHINE = ("u1", "u2"), ("t1", "t2")


def all_instances(left, right):
    """All values the junction table could take: every subset of the row set."""
    rows = list(product(left, right))
    return [frozenset(k) for n in range(len(rows) + 1) for k in combinations(rows, n)]


def tool_accepts(instance, left, right):
    """Cuts out composite-key row repetition and foreign-key dangling references.
    Both are predicates that look at a SINGLE ROW."""
    return all(a in left and b in right for a, b in instance)


def at_least_one_part(instance, left):
    """A predicate that looks at group SIZE: every work order must have at least one row."""
    return all(any(source == x for source, _ in instance) for x in left)


def single_machine(instance):
    """Group size again: a technician must appear in at most one row."""
    used = [a for a, _ in instance]
    return len(used) == len(set(used))


total_accepted, total_correct = 1, 1
for name, left, right, correct in (("WorkOrder_Part", WORK_ORDER, PART,
                                    lambda o: at_least_one_part(o, WORK_ORDER)),
                                   ("Technician_Machine", TECHNICIAN, MACHINE, single_machine)):
    instances = all_instances(left, right)
    accepted = [o for o in instances if tool_accepts(o, left, right)]
    correct_ones = [o for o in accepted if correct(o)]
    total_accepted *= len(accepted)
    total_correct *= len(correct_ones)
    print(f"{name:19s} possible instances {len(instances):3d} | tool accepts {len(accepted):3d}"
          f" | correct in the system {len(correct_ones):3d} | over-acceptance {len(accepted) - len(correct_ones):3d}")
    print(f"{'':19s} smallest over-acceptance: "
          f"{sorted(sorted(o) for o in accepted if not correct(o))[0]}")
print()
print("both junction tables together: tool accepts", total_accepted, "| correct in the system", total_correct,
      "| over-acceptance", total_accepted - total_correct)
print()


def overlaps(x, y):
    return x[1] < y[2] and y[1] < x[2]


ROWS = [("u1", 0, 4), ("u1", 2, 6)]
print("even with a time field added:")
print("  the two rows have different values -> uniqueness passes:", len(set(ROWS)) == len(ROWS))
print("  the intervals overlap -> constraint violated:", overlaps(ROWS[0], ROWS[1]))

WorkOrder_Part      possible instances  16 | tool accepts  16 | correct in the system   9 | over-acceptance   7
                    smallest over-acceptance: []
Technician_Machine  possible instances  16 | tool accepts  16 | correct in the system   9 | over-acceptance   7
                    smallest over-acceptance: [('u1', 't1'), ('u1', 't2')]

both junction tables together: tool accepts 256 | correct in the system 81 | over-acceptance 175

even with a time field added:
  the two rows have different values -> uniqueness passes: True
  the intervals overlap -> constraint violated: True

For both junction tables, the tools accept 16 of 16 instances, whereas only 9 are correct in the system. Seven instances each are states the schema accepts but that should never exist in the domain — in the course’s term, over-acceptance. Taken together, the two tables give a schema that accepts 256 states, of which 81 are correct in the system, a difference of 175.

The smallest counterexamples show the type of each constraint in its bare form. The smallest violation of the “at least one part” constraint is an empty table: with no rows at all, no key and no foreign key is violated, yet every work order is left without a part. Writing a lower-bound constraint with a tool that operates at the row level is structurally impossible, because the violation lies not in a row that exists, but in a row that does not. The smallest violation of the second constraint is two rows: ('u1','t1') and ('u1','t2'). The composite key counts these two rows as separate, because they genuinely are different; the question being asked is not equality, but how many times the same technician appears.

The last two rows show why the attempt to rescue the constraint by adding a time field is not enough. ('u1', 0, 4) and ('u1', 2, 6) are different values, so they pass every uniqueness constraint; but their intervals overlap and the constraint is violated. Equality and intersection are separate predicates, and one cannot express the other.

Second Configuration

A measurement is understood only when it is tested by varying something. Two changes are tried: varying the cardinalities and adding a new field to the model.

• VM13 — The time field has two slots (0 and 1); the time field is a field not present in the conceptual model, added at the logical level.

"""Second configuration: two ways to carry the dropped constraint, and the cost of each."""
from itertools import combinations, product

TECHNICIAN, MACHINE, TIME = ("u1", "u2"), ("t1", "t2"), (0, 1)


def subsets(rows):
    return [frozenset(k) for n in range(len(rows) + 1) for k in combinations(rows, n)]


def schema(relationships, entity_count=5, attribute_count=12):
    table = entity_count + sum(1 for _, c in relationships if c == "N:M")
    field = table + attribute_count + sum(2 if c == "N:M" else 1 for _, c in relationships)
    return table, field


print("WorkOrder-Part  Technician-Machine  table  field  invented field")
for c1, c2 in product(("N:M", "N:1"), repeat=2):
    t, f = schema([("WorkOrder-Technician", "N:1"), ("WorkOrder-Part", c1),
                   ("Technician-Machine", c2), ("WorkOrder-Document", "1:N")])
    print(f"{c1:^12s}  {c2:^11s}  {t:5d}  {f:4d}  {f - 12:14d}")
print()
rows_timeless = list(product(TECHNICIAN, MACHINE))
rows_timed = list(product(TECHNICIAN, MACHINE, TIME))


def correct_timeless(instance):
    keys = [u for u, _ in instance]
    return len(keys) == len(set(keys))


def correct_timed(instance):
    keys = [(u, z) for u, _, z in instance]
    return len(keys) == len(set(keys))


for name, rows, correct, unique in (
        ("no time field  ", rows_timeless, correct_timeless, None),
        ("time field     ", rows_timed, correct_timed, None),
        ("time + unique  ", rows_timed, correct_timed, correct_timed)):
    instances = subsets(rows)
    accepted = [o for o in instances if unique is None or unique(o)]
    correct_ones = [o for o in accepted if correct(o)]
    print(f"{name}: tool accepts {len(accepted):4d} | correct in the system {len(correct_ones):3d}"
          f" | over-acceptance {len(accepted) - len(correct_ones):4d}")

WorkOrder-Part  Technician-Machine  table  field  invented field
    N:M           N:M          7    25              13
    N:M           N:1          6    23              11
    N:1           N:M          6    23              11
    N:1           N:1          5    21               9

no time field  : tool accepts   16 | correct in the system   9 | over-acceptance    7
time field     : tool accepts  256 | correct in the system  81 | over-acceptance  175
time + unique  : tool accepts   81 | correct in the system  81 | over-acceptance    0

The first table shows that the junction table is not a matter of preference: every N:M relationship adds exactly one table and two fields, and in the fourth row, once no N:M relationship remains, the table count drops to the entity count, that is, 5. The invented field count also drops from 13 to 9 — because a key per table and at least one foreign key per relationship are required in every case.

The second table is more interesting. Once the time field is added, the number of correct instances the table can carry rises from 9 to 81: the seventy-two states in which the same technician works at different machines in different time slots could not be written at all in the timeless form. Moreover, a uniqueness constraint placed on (technician, time) carries the dropped constraint exactly: over-acceptance drops from 175 to 0.

This result shows a way to bring back the dropped constraints, but it also shows their cost. The constraint could only be written after adding a field not present at all in the conceptual model. That is, the way to rescue the dropped constraint runs through putting something the model does not state into the schema — and no fact in the conceptual model states why that field is there. This is the first example of the next lesson’s subject: the logical and physical levels do not only lose, they also invent.

Summary

• The conceptual level carries the domain’s facts, the logical level their relational-structure counterpart, the physical level storage decisions; the number of decisions grows going down.
• 26 facts convert at the logical level into 7 tables and 25 fields. Two N:M relationships give rise to two junction tables and raise the table count from 5 to 7.
• The name of 13 of the 25 fields never appears in the conceptual model: 7 primary keys and 6 foreign keys. These are not facts of the domain but the relational structure’s record-keeping apparatus.
• 3 of the 5 constraints carry over, 2 drop. The reason for dropping is the type of predicate: one puts a lower bound on row count, the other asks about the intersection of time intervals; key and uniqueness, in contrast, look at a single row or compare equality.
• The cost of the dropped constraints was counted: across the two junction tables the schema accepts 256 instances while 81 are correct in the system, that is, 175 over-acceptances. The smallest violations are an empty table and two rows of the same technician.
• The constraint can be carried over exactly by adding a time field not present in the conceptual model (over-acceptance from 175 to 0), and the number of correct instances that can be carried rises from 9 to 81; the cost is putting a field the model does not state into the schema.

Next Step

This lesson showed that a field can appear without ever being named in the model, and counted thirteen of them. The next lesson carries this count to the physical level, where the situation changes radically: seven tables with twenty-five fields demand a hundred field decisions and fourteen table decisions. How many times the total of one hundred fourteen decisions is the twenty-six facts the conceptual model states, who makes these decisions, and how it can be told that a decision made is wrong.