> **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.