What does First Normal Form mean?

I share the same name and birthdate as another individual. It has actually caused me to be held up at the border before.

What gave proof that you were not this individual in the end?

For even more fun mind bending, there's absolutely nothing that violates the relational model in having relation-valued attributes. SQL doesn't support that, but that doesn't mean its non-relational.

> A relation more or less correspond to a table

"More or less", but mostly less. Views are relations. The rowsets returned by a SELECT query are relations. Etc.

Without going into what relational algebra is about, I find it a lot more helpful to understand a "relation" like this:

A relational database is like a Prolog interpreter: it's a thing that "knows" a bunch of "facts", because someone has "asserted" (declared to be true) those facts to it.

In Prolog, facts look like this:

• red(MyCar).

• father(HarryPotter, JamesPotter).

• succ(1, 2).

Those look like functions, but what they really are, are tuples, and moreover, tuples that are members of a relation. They describe / assert a particular relationship. The "function name" at the beginning of a fact is the label, an identifier for a particular kind of relationship known to the system; it is then followed by an N-tuple of values, describing the details of this particular instance of the relationship.

A mathematical "relation", then, can be understood as an arbitrary set containing facts/relationships of a given type (the "type" being the predicate label, the tuple's arity, and the domain types of the tuple's slots.)

Note that what this definition is defining is, essentially, an ADT. A relation is a container for relationships, that exposes certain operations (relational algebra).

You can think of the set of "asserted" facts/relationships of each kind, as being a special relation. A global data structure.

But remember that Prolog can derive truth from predicate functions (e.g. that 'succ' predicate above can be defined by induction by defining a base-case fact and a function succ(N, N + 1).) So, while the set of asserted facts is a relation declaring which facts/relationships are "true", it's not the only source of truth.

-----

Now, going back to the world of relational databases:

SQL is a language for manipulating relations, just as APL is a language for manipulating arrays.

Database tables are relations! But they're not the only relations in the DB. Any "rowset" (as Postgres terms it) that you create or manipulate is a relation.

Every relation in an RDBMS (table, view, result rowset, etc.) has a type. That type is the kind of its relation, as defined above. It includes the arity and types of the tuple fields, yes, but also the label.

    -- Prolog equivalent relation type: foo(A, B).
    CREATE TABLE foo (a text, b text).

When you're creating an RDBMS table with CREATE TABLE, and giving a structural inline row-type definition, you're implicitly first defining a relation type with the same label as the table's name. The table itself is now just one relation of that type. You can have others! (In fact, queries selecting * from that table, are already other relations of the same type. However, if you're projecting or joining — changing the shape of the result-set — then your result relation is of a new temporary relation type.)

Perhaps surprisingly, you can have two RDBMS tables that have the same relation type, which makes them both sources of truth about the same facts. (Why? Partitions, for one.)

But two RDBMS tables aren't sources of truth about the same facts just because they share a shape. They need to actually be defined as having the same relation type (including the label!), to be considered interchangeable by the DB (for purposes of e.g. defining stored procedures that operate on rows of a given type.)

You can't do this by just creating another table with the same (structural inline) row-type definition. Those tables will have different relation types, because those types are carrying around predicate labels, and those labels are different.

    -- BAD: relation types are fathers_us(text, text) and fathers_eu(text, text). Incompatible!
    CREATE TABLE fathers_us (child text, father text);
    CREATE TABLE fathers_eu (child text, father text);

Instead, you must either explicitly define a relation type using CREATE TYPE; or reuse the type implicitly created from your first CREATE TABLE, to create the second. Only then are the relation labels the same.

    -- Single type: father(A, B).
    CREATE TYPE father AS (child text, father text);

    -- GOOD: same type father(A, B).
    CREATE TABLE fathers_us OF father;
    CREATE TABLE fathers_eu OF father;

Why don't DBMSes use structural typing? Well, because facts can have the same structure but still not be facts about the same thing:

    CREATE TABLE fathers(child text, parent text);
    CREATE TABLE mothers(child text, parent text);

A stored procedure that takes a fathers(text, text) row, shouldn't necessarily be able to accept a mothers(text, text) row!