> **Puzzle 111.** Suppose every person has one best friend. We get a database schema as possible. Start with a graph \\(G\\) having one node \\(\textrm{Person}\\) and one edge \\(\textrm{BestFriend}\\) from that node to itself. This gives a free category \\(\mathcal{C} = \mathbf{Free}(G)\\). Use this as our database schema. How many databases built on this schema are possible if
>
> \[ F(\textrm{Person}) = \lbrace \textrm{Anna}, \textrm{Jordan}, \textrm{Lisa}, \textrm{Ryan} \rbrace ?\]

Apart from Sophie and Jonathan's answer, I can think of a *third* solution.

My answer: assuming the \\(\mathrm{BestFriend}\\) relation can be `NULL`, then there are \\(5^4 = 625\\)

(This is the case where the \\(\mathrm{BestFriend}\\) relation can be a *total* or *partial* function.)

----------------------------

**Background:** [SQL](https://en.wikipedia.org/wiki/SQL) is the *Structured Query Language*. Almost all relational databases in industry are programmed some dialect of this language. SQL is what Spivak and Wisnesky's [AQL](http://categoricaldata.net/aql.html) database language compiles down to. AQL is a real world implementation of FQL, the categorical database language in Chapter 3 of *7 Sketches* we have been talking about.

In SQL, there's basically two ways I could create the `Person` table.

The first reflects Sophie and Jonathan's solution:


CREATE TABLE Person (
Name VARCHAR(128) PRIMARY KEY,
BestFriend VARCHAR(128) NOT NULL REFERENCES Person (Name)
);


Notice that this has the `NOT NULL` constraint on `Person.BestFriend`. This forces the `BestFriend` column to behave like a total function and thus there are \\(4^4 = 256\\) permutations.

(There is a *Wired* story from 2015 about [*John Null*](https://www.wired.com/2015/11/null/). His name is often erroneously forbidden by this sort of database constraint. He has had a lot of difficulty due to widespread bad programming practices.)

At any rate it's plausible that we don't always know everyone's best friend. In this case the table declaration looks like:


CREATE TABLE Person (
Name VARCHAR(128) PRIMARY KEY,
BestFriend VARCHAR(128) REFERENCES Person (Name)
);


Here the `NOT NULL` constraint on `Person.BestFriend` has been dropped.

If `Person` has four rows, then now there's a fifth possible value for the `BestFriend` column: `NULL`.

Hence there are \\(5^4\\) possibilities in this case.

**Puzzle 112** and **Puzzle 113** rule out `NULL` by introducing algebraic constraints.