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


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

  • $\begingroup$ 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? $\endgroup$ Commented Nov 23, 2021 at 12:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Nov 23, 2021 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.