# Histogram representation of a database

I'm reading though The Algorithmic Foundations of Differential Privacy and the authors define a database in a mathematically convenient way. Unfortunately I'm a little confused about what the definition actually means in practice.

From page 17 of the pdf:

We will think of databases $$x$$ as being collections of records from a universe $$\mathcal{X}$$. It will often be convenient to represent databases by their histograms: $$x \in \mathbb{N}^{\lvert\mathcal{X}\rvert}$$, in which each entry $$x_i$$ represents the number of elements in the database $$x$$ of type $$i \in \mathcal{X}$$ (we abuse notation slightly, letting the symbol $$\mathbb{N}$$ denote the set of all non-negative integers, including zero).

Suppose we have a sample database that looks like this:

Row Name Age
1 Tom 19
2 Ray 22
3 Sue 42
4 Bob 42

I'm pretty sure each $$x$$ is just some combination of all rows of the database (say rows 1,3, and 4 or only row 1). I'm not at all clear what "type $$i$$" means. Is each type a row so that a database of rows 1, 3, and 4 would be $$x = \{1, 0, 1, 1\}$$? Or is type a level in the database; e.g. type $$1$$ is "Age 19", type $$2$$ is "Age 22", type $$3$$ is "Age 42", type 4 is "Tom", type 5 is "Ray", type 6 is "Sue", type 7 is "Bob". Thus the histogram representation is $$x = \{1, 0, 2, 1, 0, 1, 1\}$$?

To summarize my questions: What would the histogram representation $$x$$ be for a database with rows 1, 3, and 4? What are the possible values of $$i$$ in this $$\mathcal{X}$$?

No, you went wrong right from the start. $$x$$ is the database. In this case, if the database is shown in that table, $$x$$ is the set of all rows shown in the table above. If $$x$$ is a database with just rows 1, 3, and 4, then $$x$$ would be those set of three rows.
Now they recommend representing a set as a histogram. To do that, we need to have a "universe" $$\mathcal{X}$$ of all possible rows that could ever occur (including both rows that do occur in the database as well as rows that don't occur in the database but could have). Then, $$x$$ is a vector that records a count of how many times each of those possible rows actually occurs in the database. If the possible row doesn't occur in the database, its count is 0; if it occurs once, its count is 1; and so on. You then put those counts into a vector.
The possible values of $$i$$ are all possible rows in the universe $$\mathcal{X}$$.
• Okay excellent, so a database with rows 1, 3, and 4 would have histogram vector $[1, 0, 1, 1]$ and a database with rows 1, 3, 3, 3, 4, 4 would have histogram vector $[1, 0, 3, 2]$? Could we say $x=[1, 0, 3,3]$ or is that bad database notation? Nov 23 at 12:15
• @robtimus_prime, yes, if by rows 1,3,4 you mean the 1st, 3rd, and 4th possibilities in the universe. $x=[1,0,3,3]$ corresponds to a database with rows 1,3,3,3,4,4,4.