First Normal Form

A relation in the relational model is formally a subset of the Cartesian product of a list of domains $D_1 \times D_2 \times \cdots \times D_n$, where each domain $D_i$ is a set of atomic values. "Atomic" means the values in $D_i$ are treated as indivisible units by the model — you cannot ask the relational algebra to reach inside a domain value and extract part of it. A telephone number `"555-1234"` stored as a single string is atomic in this sense even though it "contains" digits, because the schema treats it as one value; the trouble starts when a single attribute is asked to hold a variable number of values, such as `{"555-1234", "555-9876"}` for a student with two phones.

First Normal Form (1NF) is the constraint that a relation's domains contain only atomic values, equivalently: every attribute of every tuple holds exactly one value, never a set, list, or nested tuple. A schema that permits a repeating group — a set of columns like `phone1, phone2, phone3` meant to hold "however many phones this row has, up to three" — or a multivalued attribute — a single column meant to hold an unbounded collection — is not in 1NF. Neither is a schema with a composite attribute stored as one nested record, e.g., an `Address` column that is itself a struct of `{street, city, zip}`, if the intent is that sub-fields should be independently queryable and constrained. The distinction that matters is between representation and semantics. A `VARCHAR` column holding `"123 Main St, Springfield, 62704"` is technically atomic (one string) but semantically composite, and treating it as opaque prevents the database from enforcing constraints like "zip code determines city" or indexing on zip alone. 1NF violations, therefore, come in two flavors: multi-valued (a cell holds a variable-length collection) and composite/non-atomic (a cell holds a fixed internal structure the application still needs to decompose). Both break the guarantee that selection, projection, and join operate correctly and predictably over single-valued comparisons.

Detecting and fixing a 1NF violation follows a standard recognition-and-decomposition pattern. The core test is: for a given attribute, can a single tuple legitimately need to store more than one value, or a structured value, in that attribute's cell? If yes, the schema is not in 1NF. The two structural symptoms: 1. Repeating groups as columns. `Student(ID, Name, Phone1, Phone2, Phone3)`. This wastes space for students with fewer phones, cannot accommodate a fourth phone, and makes "find all phones for this student" awkward (you must check three columns). 2. Multi-valued single column. `Student(ID, Name, Phones)` where `Phones = "555-1234, 555-9876"`. This makes it impossible to declare a domain, index individual phone numbers, or enforce uniqueness of a phone number across students without string parsing. The standard fix is decomposition into a separate relation connected by the original key, turning the "many values in one cell" problem into "many rows in a child table" — which the relational model handles natively via foreign keys and joins. ``` ALGORITHM DetectAndFix1NF(R, attributes) // R: a relation schema with a candidate/primary key K // attributes: list of (name, domain_description) pairs violations := [] FOR EACH attr IN attributes: IF attr.domain_description indicates "set of values" OR attr.domain_description indicates "variable-length list" OR attr is one of a numbered repeating group {A1, A2, ..., Ak}: violations.append(attr) IF violations is empty: RETURN R // already in 1NF, nothing to do FOR EACH attr IN violations: IF attr is a numbered repeating group {A1, ..., Ak}: // Case 1: fixed repeating group -> flatten to rows newRelation := CREATE RELATION R_attr(K, attr_value) FOR EACH tuple t IN R: FOR i IN 1..k: IF t.A_i IS NOT NULL: INSERT (t.K, t.A_i) INTO R_attr REMOVE columns A1..Ak FROM R ELSE: // Case 2: single multi-valued column -> split values into rows newRelation := CREATE RELATION R_attr(K, attr_value) FOR EACH tuple t IN R: FOR EACH value v IN SPLIT(t.attr, delimiter): INSERT (t.K, v) INTO R_attr REMOVE column attr FROM R RETURN {R (with violations removed), R_attr for each violation} ``` Applied to `Student(ID, Name, Phone1, Phone2, Phone3)`: ``` Student(ID, Name) StudentPhone(ID, Phone) -- one row per (student, phone) pair -- FOREIGN KEY ID REFERENCES Student(ID) ``` The composite-key of `StudentPhone` is `(ID, Phone)`, since a student may have several phones and — in principle — a phone could be shared (though a `UNIQUE` constraint might forbid that depending on business rules). This is the general recipe: whenever an attribute is multi-valued relative to the key, split it into its own relation whose key includes the original key plus the value itself (or a synthetic surrogate). The same reasoning applies to composite attributes that need independent access: `Address` becomes `Street, City, Zip` as three atomic columns directly in the same relation (no new relation needed, since a composite attribute is not multi-valued — it just needs its parts named separately).

Detection complexity. Detecting whether a schema is in 1NF is a syntactic check on the schema definition, not on data: for each attribute, inspect whether its declared domain is atomic (a single scalar type) or structured (an array, set, nested record, or a numbered family of columns). This is $O(k)$ in the number of attributes $k$ in the relation — a linear scan of the schema, no data access required. Detecting accidental non-atomicity in already-atomic-typed columns (e.g., a `VARCHAR` secretly storing a comma-separated list) additionally requires a data scan, $O(n)$ in the number of tuples $n$, to check whether values match a "single item" pattern versus a delimited list — this is a heuristic, not a formal guarantee, since nothing in the schema prevents a legitimate atomic string from containing a comma.

Decomposition complexity. The `DetectAndFix1NF` algorithm above performs one pass over the relation's tuples, and for each tuple, a constant amount of work per repeating-group slot or a split proportional to the number of values in the multi-valued cell. If a relation has $n$ tuples and each tuple's multi-valued attribute contains at most $m$ values, total work is $O(n \cdot m)$ — each value is written exactly once into the new child relation, so this is optimal: you cannot produce the output (one row per value) in less than the size of the output.

Space. The decomposed schema does not necessarily increase total data volume; it trades wasted NULL cells (in the repeating-group version, most rows have unused `Phone2`, `Phone3` slots) for a compact child table with exactly one row per actual value. In the worst case (every student has exactly the maximum number of phones), space is comparable; in the common case (variable number of values), the 1NF decomposition is strictly more space-efficient because it eliminates NULL padding.

Correctness argument. The key claim is that decomposition is lossless — the original relation can be exactly reconstructed by projecting and joining the decomposed pieces. This follows because the child relation retains the parent's key (`ID`) alongside the split-out value, so:

reconstructs the same information via a natural join on `ID` (formally, you would need an outer join if some students have zero phones, to preserve rows with no matching child tuples — a subtlety worth flagging explicitly). This is an instance of the general lossless-join decomposition criterion used throughout normalization theory: a decomposition of $R$ into $R_1, R_2$ is lossless if $R_1 \cap R_2$ is a superkey of at least one of $R_1, R_2$. Here $R_1 \cap R_2 = \{ID\}$, and `ID` is (part of) the key of both — trivially satisfying the criterion for the parent side, and being a foreign key referencing it on the child side.

Why atomicity is necessary, not cosmetic. The relational algebra's selection operator $\sigma_{\theta}(R)$ assumes $\theta$ is a predicate over single values (e.g., `Phone = '555-1234'`); if `Phone` can hold `"555-1234, 555-9876"`, this predicate silently fails to match a tuple that logically does contain that phone number, unless you rewrite every query with substring search — abandoning the declarative guarantees SQL is supposed to provide. Similarly, a `GROUP BY Phone` or `JOIN ON Phone` becomes meaningless across multi-valued cells: two students who share one phone number out of several would not be correctly grouped together by naive equality. 1NF is precisely the condition under which `=` comparison and the standard relational operators behave as the algebra's semantics promise.

Honest tradeoff. Strict 1NF is not free. Splitting one multi-valued attribute into a child relation means every query needing "students and their phones together" must perform a join, adding I/O and CPU cost proportional to the join algorithm used (commonly $O(n \log n)$ for sort-merge join, or $O(n)$ expected for hash join) versus $O(1)$ access to a denormalized array cell. This is exactly why systems like PostgreSQL (array types), MongoDB (embedded documents), and BigQuery (nested/repeated fields) offer controlled, first-class support for non-atomic values — accepting some anomaly risk in exchange for avoiding join overhead in read-heavy, write-rarely workloads.

Consider an unnormalized `CourseEnrollment` table meant to record, for each student, the courses they are taking and the courses' instructors:

The `Courses` attribute is a set of nested pairs — doubly non-atomic: it is multi-valued (a student can take several courses) and each value is itself composite (a course-instructor pair). This is a realistic pattern seen in document stores and JSON columns, and it is the sharpest kind of 1NF violation because naive flattening alone is insufficient — we must both split the set and decompose the pairs.

Step 1 — split the multi-valued attribute into rows, keeping `StudentID` as the linking key:

(Student 103, with an empty set, contributes no rows here — a consequence worth noting: information about "Alan exists but takes nothing" now lives only in the `Student` table, which is correct and expected.)

Step 2 — separate the base relation:

Step 3 — verify atomicity. Every column in both resulting relations now holds exactly one scalar value per row: `StudentID` is an integer, `Course` is a course code string, `Instructor` is a name string. No cell contains a set or a nested structure. Both relations are in 1NF.

Step 4 — verify losslessness. Reconstructing the original requires an outer join of `Student` and `Enrollment` on `StudentID`, then grouping `Enrollment` rows back into a set per student — recovering exactly the original nested structure (including Alan's empty set, thanks to the outer join). No information was discarded; only its physical shape changed. Notice a side effect: this decomposition has silently also produced a table, `Enrollment(StudentID, Course, Instructor)`, that is ripe for a different kind of anomaly — if `Hopper` is misspelled in one row and not another, we get an inconsistency, because `Instructor` depends only on `Course`, not on the full key `(StudentID, Course)`. This is a partial dependency, and it is exactly the problem Second Normal Form is designed to catch; 1NF's job ends at making the attributes atomic, not at eliminating every anomaly.

The relational model, and with it the first formal statement of normal forms, originates with Edgar F. Codd's foundational 1970 paper proposing that data be represented purely as relations over atomic domains — a radical simplification compared to the hierarchical and network database systems of the era, which natively supported nested and repeating structures. Codd's insistence on atomic domains was not incidental; it was the precondition that made relational algebra a clean, closed algebraic system in the first place. Without atomicity, operators like selection and join lose their precise mathematical meaning, and the whole appeal of a declarative query language built on set theory collapses.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — enforces 1NF by construction in its base table storage model: a column is declared with a single scalar type, and standard `CREATE TABLE` syntax has no way to express "a variable number of values" without an explicit array or JSON type. Schema designers doing entity-relationship modeling for e-commerce (order line items), healthcare (patient medications), and finance (transaction tags) routinely hit the "one-to-many attribute" problem this article addresses, and the standard fix — a child table with a foreign key — is the single most common pattern in relational schema design. The tension between strict 1NF and practical convenience shows up directly in modern engines: PostgreSQL's array and `hstore` types, SQL Server's XML columns, and nearly every NoSQL document store (MongoDB, Couchbase) allow developers to deliberately store non-atomic values for performance, at the cost of reintroducing the very anomalies normalization guards against — inconsistent duplicated data, awkward uniqueness constraints, and query complexity. Data warehouse systems like BigQuery and Snowflake explicitly support nested/repeated (`STRUCT`, `ARRAY`) columns because analytical workloads often favor denormalized, pre-joined data for read performance, showing that 1NF is best understood as a design default to deviate from consciously, not an inviolable law. Understanding 1NF precisely is what lets an engineer recognize the difference between a deliberate denormalization decision and an accidental design flaw.

Ask the tutor: How does the choice between a strict 1NF design and a denormalized JSON/array column affect join cost versus anomaly risk in a real read-heavy analytics workload?