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