Histogram representation of a database

Question

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}$?

Answer 1

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}$.