Relations / Databases And State
Least You Need to Know: Relations in Databases and State Machines
Relations are not only abstract sets of ordered pairs. They appear in foreign-key links, join tables, dependency graphs, and state-transition systems used all over software engineering.
The least you need to know
- A relation may connect one record to many others, many to one, or many to many.
- A function is a special kind of relation where each input has exactly one output.
- Many-to-many database relationships are often implemented with a join table.
- A deterministic state machine can be modeled as a function from `(state, input)` to the next state.
- State-transition graphs are relation-based models of possible execution steps.
Key notation
R ⊆ A × B
a relation from A to B
(state, input) ↦ next_state
deterministic transition function
join table
table storing many-to-many links
Tiny worked example
- Many orders can belong to one customer, so the order-to-customer link is many-to-one.
- A course-enrollment table can connect many students to many courses, which is many-to-many.
- A state machine transition relation records which next states are allowed from each current state and input.
Common mistakes
- Students often assume every relation is automatically a function.
- Students often confuse many-to-one with one-to-many because they read the direction backward.
- Students often miss that a deterministic state machine is function-like once the current state and input are fixed.
How to recognize this kind of problem
- Ask which direction the ordered pair is read.
- If one side can connect to several matches, the relation is not a function in that direction.
- For databases, think concretely in terms of records and foreign-key links.
Next recommended lesson
Continue through this topic with Least You Need to Know: Equivalence Relations.
Least You Need to Know: Equivalence RelationsRelated lessons
Keep going with nearby lessons in the same topic.