# Differential privacy basics: Universe \mathcal{X} and database $x$

The "Algorithmic Foundations of Differential Privacy" book (DOI: 10.1561/0400000042) introduces formally the "universe" and "database" on page 17 roughly as:

• $$\mathcal{X}$$ is a universe
• databases $$x$$ are collections of records from the universe
• For convenience, we use histogram of types from the universe $$\mathcal{X}$$ to represent $$x$$, such that: $$x \in \mathbb{N}^{|\mathcal{X}|}$$ where each entry $$x_i$$ represents the number of elements in the database $$x$$ of type $$i \in \mathcal{X}$$

If you take the example from Wikipedia

• The universe $$\mathcal{X}$$ is a set $$\{0, 1\}$$?
• The database $$x$$ is
• a vector [3, 3] (assuming the universe is ordered)?
• or a map {0:3, 1:3}?

My two questions are:

• Is my understanding correct?
• Why is it "convenient" to do so? What would be the non-convenient alternatives?

I am a little late. Your understanding seems correct. $$\mathcal{X}=Names \times \{0,1\}$$ Where $$Names$$ are all the possible names that could exist and $$x \in \mathbb{N}^{2}$$ (Because of $$|\mathcal{X}|=2$$).
Then you can choose one column and select the histogram of the type you want. Then you can express $$x=(x_0,x_1)=(3,3)$$ or $$x=(x_{ross},...,x_{Rachel})=(1,..,1)$$. A you see the first one is more convenient.