14 ms·

What does First Normal Form mean?

76 points by goto11 5y ago

hobs 5y ago
A clear and concise explanation - well done and rare for the topic.
flint 5y ago
Why does he use the form: "A relation more or less correspond to" and "A relation have"? This doesn't seem to me to be unintended.
- tyingq 5y ago
  He's somewhat consistent with that. "A relation...correspond", "relation refer to the", "an attribute correspond to". But diverges on that pattern for "domain": "a domain...corresponds".
  - whatshisface 5y ago
    Level 0 data science: "We have several datapoints." Level 1 data science: "We have several data." Level 100 data science: "A relation have a fixed number of attributes (columns) and each column have a domain [...]."
  - wcarss 5y ago
    may also be english as a second+ language or just a frequent brainfart around pluralization, see the intro: > This post explains what 1NF actually means and is useful for, and debunk a number of the misunderstandings.
    - ehw3 5y ago
      The Wikipedia entry on First Normal Form also uses this kind of construction, which I suspect means it was written by the same person. I have never seen terms like domain and attribute used as if they were plurals (the way "data" is), but even were that correct, "a domain have" would be contradictory, so I think it is just a linguistic quirk of the writer.
whatshisface 5y ago
I have never understood why RDBs have such general concepts of primary keys, where you can for example let date of birth be a primary key, when in every schema I have ever designed or seen, all rows get unique integer IDs anyway.
- mmcgaha 5y ago
  I completely agree with you, yet I design most of my schemas with integer keys anyway. The only thing I do different than most folks is that I make a unique constraint/index for candidate keys (the proper primary key) because otherwise we have lost the ability to ensure data consistency. As for why I use integer keys, it has always been the convention everywhere I go so I don't want to break convention. Now the only convention that I would rather see would be to use GUIDs instead of integers because I hate that I can join an item table to an employee table and get results back.
- cyberbanjo 5y ago
  What about people with the same birthdays?
  - wfriesen 5y ago
    Business/requirements/users will often tell you that no two users will have the same birthday/SSN/whatever, but so often that eventually proves incorrect. Just using an auto increment ID as the primary key can prevent a lot of pain down the road.
    - lifepillar 5y ago
      So, when someone comes to you and identifies herself by providing her SSN, name, date of birth, how do you know whether she corresponds to the record with id M or to the record with id N? Or, more likely, to one of the N records, with N>2, with that SSN, name, date of birth?
  - jraph 5y ago
    What about them? Do they really exist, practically speaking? At a quick glance on my databases, I see nothing of the sort.
gfody 5y ago
I think he contradicts himself and confuses the data with the information. I don't think delimited values representing a table in a column can be considered normalized. >Make no mistake, encoding multiple values in a single string is generally a bad design. But it has nothing to do with first normal form. First normal form mean a column should not allow relations as values. A comma-separated string is still just a single string from the perspective of the database type system.
- mamcx 5y ago
  No, is not a contradiction. Is like say "Is wrong to store a large json in a cell in an array, that make it not an array". A relation is A VALUE. That is. The atomicity of the data INSIDE each "cell" is orthogonal to the fact the that relation is a relation. This is the point.
  - blacktriangle 5y ago
    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.
    - derefr 5y ago
      Re: DB support for relations as values — while no DB I know of supports full relations (sets of tuples) in values, composite-typed (single-tuple) columns are a thing, e.g. the on_hand example table in https://www.postgresql.org/docs/current/rowtypes.html https://www.postgresql.org/docs/current/rowtypes.html Also, presuming DB support for some format like JSON, you can encode a relation into a JSON value, stick it into a column and then, at query time, use a function like Postgres's json_to_recordset(json) to emit a relation (set of tuples). Postgres doesn't know how to deal with it "as is" (i.e. it forces you to treat the result of a function as a named joined table in your query, rather than treating it as an concrete value) but it does understand where it is in relation (heh) to the rest of the row, since you can unnest() values from this virtual table and get the right results out. As awful as that sounds, we're actually doing that in production to normalize data coming from redis_fdw (which gives you, basically, (key text, value jsonb) rows for Redis hashes) into relational shape.
transitorykris 5y ago
The key, the whole key, and nothing but the key
- jbigelow76 5y ago
  So help me Codd.
derefr 5y ago
> 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!
painchoc 5y ago
What about NULLs ? Is it allowed or not ? I recently discovered on Wikipedia https://en.wikipedia.org/wiki/First_normal_form https://en.wikipedia.org/wiki/First_normal_form that it should not be.
- goto11 5y ago
  They should not be allowed according to C.F.Date, but this is quite a controversial opinion. E.F.Codd who invented the relational model thinks nulls are fine.
crazygringo 5y ago
Sorry but I think this author is being more pedantic rather than helpful, and actually seems to miss the point entirely. The crux here is two things the author claims: > Since SQL does not allow creating or using nested tables, most relational databases will be in first normal form by necessity. > Many explanations (including Wikipedia) uses the example of a comma-separated string with phone numbers as an example of a 1NF violation... Make no mistake, encoding multiple values in a single string is generally a bad design. But it has nothing to do with first normal form. First normal form mean a column should not allow relations as values. A comma-separated string is still just a single string from the perspective of the database type system. I think it's rather obvious that the example here is nothing to do with literal commas. But that storing multiple comma-delimited phone numbers in a single field is precisely creating a nested table in spirit. It has nothing to do with SQL support for nested tables or the database type system -- it's not about formal definitions. It's about whether you're conceptually putting multiple pieces of data into a single field. Which has everything to do with first normal form. Because if you put comma-delimited phone numbers into a field, you lose the ability to relate and join those phone numbers individually to another table. Which is bad, and the whole concept of "1NF" exists to give a name to this badness. And this isn't a minor point. It's actually extremely important, because the common practice of throwing JSON data into a string field destroys the ability to operate relationally on the data within it. Now of course, plenty of databases these days actually do provide ways to index and join on data using a new "JSON" type column -- which is yet another form of the "nested table" the author claims doesn't exist. Which is great for combining ease of use with performance, but certainly isn't 1NF, and basically explodes (or at least dramatically complicates) the fundamental concept of relational databases as tables of rows and columns.
- zozbot234 5y ago
  > Because if you put comma-delimited phone numbers into a field, you lose the ability to relate and join those phone numbers individually to another table. Which is bad It's bad if you expect that ability in the first place! If the data you're storing (e.g. a list of phone numbers) will only ever be treated as a unified blob without any finer senantics, storing it as a single attribute is not a 1NF violation.
pjungwir 5y ago
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 https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf [1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf [2] https://gertjans.home.xs4all.nl/usenet/microsoft.public.sqlserver.programming/codd1979.pdf https://gertjans.home.xs4all.nl/usenet/microsoft.public.sqls... [3] C.J. Date et al, Time and Relational Theory
- 5y ago

76 points by goto11 5y ago

hobs 5y ago

A clear and concise explanation - well done and rare for the topic.

Why does he use the form: "A relation more or less correspond to" and "A relation have"? This doesn't seem to me to be unintended.

tyingq 5y ago
He's somewhat consistent with that. "A relation...correspond", "relation refer to the", "an attribute correspond to". But diverges on that pattern for "domain": "a domain...corresponds".
- whatshisface 5y ago
  Level 0 data science: "We have several datapoints." Level 1 data science: "We have several data." Level 100 data science: "A relation have a fixed number of attributes (columns) and each column have a domain [...]."
- wcarss 5y ago
  may also be english as a second+ language or just a frequent brainfart around pluralization, see the intro: > This post explains what 1NF actually means and is useful for, and debunk a number of the misunderstandings.
  - ehw3 5y ago
    The Wikipedia entry on First Normal Form also uses this kind of construction, which I suspect means it was written by the same person. I have never seen terms like domain and attribute used as if they were plurals (the way "data" is), but even were that correct, "a domain have" would be contradictory, so I think it is just a linguistic quirk of the writer.

whatshisface 5y ago

I have never understood why RDBs have such general concepts of primary keys, where you can for example let date of birth be a primary key, when in every schema I have ever designed or seen, all rows get unique integer IDs anyway.

mmcgaha 5y ago
I completely agree with you, yet I design most of my schemas with integer keys anyway. The only thing I do different than most folks is that I make a unique constraint/index for candidate keys (the proper primary key) because otherwise we have lost the ability to ensure data consistency. As for why I use integer keys, it has always been the convention everywhere I go so I don't want to break convention. Now the only convention that I would rather see would be to use GUIDs instead of integers because I hate that I can join an item table to an employee table and get results back.
cyberbanjo 5y ago
What about people with the same birthdays?
- wfriesen 5y ago
  Business/requirements/users will often tell you that no two users will have the same birthday/SSN/whatever, but so often that eventually proves incorrect. Just using an auto increment ID as the primary key can prevent a lot of pain down the road.
  - lifepillar 5y ago
    So, when someone comes to you and identifies herself by providing her SSN, name, date of birth, how do you know whether she corresponds to the record with id M or to the record with id N? Or, more likely, to one of the N records, with N>2, with that SSN, name, date of birth?
- jraph 5y ago
  What about them? Do they really exist, practically speaking? At a quick glance on my databases, I see nothing of the sort.

gfody 5y ago

I think he contradicts himself and confuses the data with the information. I don't think delimited values representing a table in a column can be considered normalized. >Make no mistake, encoding multiple values in a single string is generally a bad design. But it has nothing to do with first normal form. First normal form mean a column should not allow relations as values. A comma-separated string is still just a single string from the perspective of the database type system.

mamcx 5y ago
No, is not a contradiction. Is like say "Is wrong to store a large json in a cell in an array, that make it not an array". A relation is A VALUE. That is. The atomicity of the data INSIDE each "cell" is orthogonal to the fact the that relation is a relation. This is the point.
- blacktriangle 5y ago
  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.
  - derefr 5y ago
    Re: DB support for relations as values — while no DB I know of supports full relations (sets of tuples) in values, composite-typed (single-tuple) columns are a thing, e.g. the on_hand example table in https://www.postgresql.org/docs/current/rowtypes.html https://www.postgresql.org/docs/current/rowtypes.html Also, presuming DB support for some format like JSON, you can encode a relation into a JSON value, stick it into a column and then, at query time, use a function like Postgres's json_to_recordset(json) to emit a relation (set of tuples). Postgres doesn't know how to deal with it "as is" (i.e. it forces you to treat the result of a function as a named joined table in your query, rather than treating it as an concrete value) but it does understand where it is in relation (heh) to the rest of the row, since you can unnest() values from this virtual table and get the right results out. As awful as that sounds, we're actually doing that in production to normalize data coming from redis_fdw (which gives you, basically, (key text, value jsonb) rows for Redis hashes) into relational shape.

transitorykris 5y ago

The key, the whole key, and nothing but the key

jbigelow76 5y ago
So help me Codd.

derefr 5y ago

> 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!

painchoc 5y ago

What about NULLs ? Is it allowed or not ? I recently discovered on Wikipedia https://en.wikipedia.org/wiki/First_normal_form https://en.wikipedia.org/wiki/First_normal_form that it should not be.

goto11 5y ago
They should not be allowed according to C.F.Date, but this is quite a controversial opinion. E.F.Codd who invented the relational model thinks nulls are fine.

crazygringo 5y ago

Sorry but I think this author is being more pedantic rather than helpful, and actually seems to miss the point entirely. The crux here is two things the author claims: > Since SQL does not allow creating or using nested tables, most relational databases will be in first normal form by necessity. > Many explanations (including Wikipedia) uses the example of a comma-separated string with phone numbers as an example of a 1NF violation... Make no mistake, encoding multiple values in a single string is generally a bad design. But it has nothing to do with first normal form. First normal form mean a column should not allow relations as values. A comma-separated string is still just a single string from the perspective of the database type system. I think it's rather obvious that the example here is nothing to do with literal commas. But that storing multiple comma-delimited phone numbers in a single field is precisely creating a nested table in spirit. It has nothing to do with SQL support for nested tables or the database type system -- it's not about formal definitions. It's about whether you're conceptually putting multiple pieces of data into a single field. Which has everything to do with first normal form. Because if you put comma-delimited phone numbers into a field, you lose the ability to relate and join those phone numbers individually to another table. Which is bad, and the whole concept of "1NF" exists to give a name to this badness. And this isn't a minor point. It's actually extremely important, because the common practice of throwing JSON data into a string field destroys the ability to operate relationally on the data within it. Now of course, plenty of databases these days actually do provide ways to index and join on data using a new "JSON" type column -- which is yet another form of the "nested table" the author claims doesn't exist. Which is great for combining ease of use with performance, but certainly isn't 1NF, and basically explodes (or at least dramatically complicates) the fundamental concept of relational databases as tables of rows and columns.

zozbot234 5y ago
> Because if you put comma-delimited phone numbers into a field, you lose the ability to relate and join those phone numbers individually to another table. Which is bad It's bad if you expect that ability in the first place! If the data you're storing (e.g. a list of phone numbers) will only ever be treated as a unified blob without any finer senantics, storing it as a single attribute is not a 1NF violation.

pjungwir 5y ago

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 https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf [1] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf [2] https://gertjans.home.xs4all.nl/usenet/microsoft.public.sqlserver.programming/codd1979.pdf https://gertjans.home.xs4all.nl/usenet/microsoft.public.sqls... [3] C.J. Date et al, Time and Relational Theory

5y ago