What does First Normal Form mean?

Codd's paper is not that hard. [0] is a PDF copy. One of the pros to reading primary sources is you then know "the whole story": what if anything is missing from popular explanations, and what is changed.

A striking bit of trivia (but OT to SQL) is that in Turing's "On Computable Numbers" [1] he treats a Turing Machine that halts as having a problem, whereas in basically every popular treatment a machine that halts is one that gives you an answer, and a machine that doesn't halt is one with a bug, like it entered an infinite loop. But his paper is the opposite (and doesn't use the word "halt" at all!):

    If a computing machine never writes down more than a finite number of symbols
    of the first kind it will be called circular. Otherwise it is said to be circle-free.

    A machine will be circular if it reaches a configuration from which there is no possible
    move, or if it goes on moving, and possibly printing symbols of the second kind,
    but cannot print any more symbols of the first kind.

More relevantly, Codd's paper from ten years later [2] is even more interesting than the first one. Everyone focuses on the first half (discussing NULLs and outer joins) but the second half is way more interesting, and has never been implemented anywhere AFAIK. It sounds a lot like graph databases and queries that dynamically change structure based on querying the data catalog.

Re relations containing relations, I was very surprised that C.J. Date is apparently okay with them. He is a perfect example of the disciple who is more zealous than the master, and has spent his career trying to remove NULLs and non-unique rows. But in page 17-18 of [3] he writes:

    To repeat, any type whatsoever---apart from the two exceptions noted in the
    section "Types" earlier---can be used as the basis for defining attributes of
    relations. In particular, relation types can be used for this purpose. (So too can
    tuple types.) Thus, attributes can be *relation valued*, meaning we can have relations
    with attributes whose values are relations in turn.

Wow! Part of me wonders if he is really just compromising because relations-inside-relations is so useful for his goals in that book. I had to re-read that passage over and over to convince myself I wasn't misunderstanding.

[0] https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

[1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[2] https://gertjans.home.xs4all.nl/usenet/microsoft.public.sqls...

[3] C.J. Date et al, Time and Relational Theory

Synthetic primary keys like a unique integer ID assigned to a row are worse in theory - the id column isn't real data. They exist as a very common practical compromise for good reasons, but you should be aware you're compromising theory for practice.

What you're talking about is a natural key[1], which can be contrasted with a surrogate key[2]. (Surrogate keys are also called "synthetic keys" or "factless keys".)

So the question is whether natural keys are ever useful.

I think the answer is yes, they are useful if the real world already imposes a key on the stuff you are modeling in the database. In that case, it is already unique (as it needs to be), and generating your own key doesn't accomplish anything (but is redundant).

For example, suppose I'm creating a history database of who owned what internet domain names at which times. If my table is one-to-one with domains, I can use the domain name itself as the primary key.

If not, I can perhaps use the domain name plus some other column as a composite key. For a table of ownership intervals, my primary key could be this: domain name + start date + end date.

---

[1] https://en.wikipedia.org/wiki/Natural_key

[2] https://en.wikipedia.org/wiki/Surrogate_key

Among the principal tenets of Codd's database model (which is not intended to be a generalized model of relations) are that the database scheme should not introduce either accidental relationships or accidental constraints.

If we represent a one-to-many relationship by making a CSV of the elements of the "many" side, then, for a given X standing in this relationship to A, B and C:

1) We have introduced an ordering that may not be relevant - is "A,B,C" the same as "B,A,C"?

2) We cannot find out whether X has this relationship to B without parsing the CSV, or which entities B stands in this relationship to.

3) We cannot add or remove instances of this relationship to X without updating the whole relationship.

...and so on.

All these are accidental features of the data representation that are not inherent to the semantic domain.

So, when you write "It's bad if you expect that ability in the first place!", you are essentially saying "if we put aside the principles of Codd's model and accept the very problems it was expressly intended to mitigate..."

You can certainly use a relational database to store information in ways that preserve the sorts of problems they were intended to solve - and there will be cases where it does not matter. The normal forms are guidelines for using relational databases as intended, to minimize these problems, when it might matter.

>For example, suppose I'm creating a history database of who owned what internet domain names at which times. If my table is one-to-one with domains, I can use the domain name itself as the primary key.

In your example, wouldn't that not work, because the same domain would be in the table twice with two different owners?