With the ADS architecture in place, we can now conduct queries on the zkDB. Let’s explore how this is done.

Note that all queries return the count for the number of satisfying users (or number of rows) in the database. This is for privacy reasons, we will not return actual user data.

​

Anatomy of a Query

A query is a request for information from the database. More importantly, we can construct virtually any query we would like from a few basic operations.

• Set membership: $a\in \{b_1, b_2, \ldots, b_n\}$
• Set non-membership: $a\notin \{b_1, b_2, \ldots, b_n\}$
• Intersection: $\{a\}\land \{b\} = \{a_1, a_2, \ldots, a_m\} \cap \{b_1, b_2, \ldots, b_n\}$
• Union/Join: $\{a\}\lor \{b\} = \{a_1, a_2, \ldots, a_m, b_1, b_2, \ldots, b_n\}$
• Sum: $\sum_i a_i$
• Count: $|\{a\}|$
• Min, Max: $\min (\{a\}), \max (\{a\}$)
• Mean, Median: $\text{mean} (\{a\}), \text{median} (\{a\})$

Using these we can conduct any user-data related query we would like. Moreover, we can represent this query in a specific way, namely as $q_1 \lor q_2 \lor \cdots \lor q_m$ where each $q_i$ is of the form $q_i = c_1 \land c_2 \land \cdots \land c_l,$ and each $c_j$ is set (non-)membership.

​

Query Engine

We have to do things in a certain order to ensure it is efficient and flexible.

Verifiers can check the query by checking the proofs in iteration:

1. Check the ADS proof to ensure the database is valid.
2. Check the Merkle proofs to ensure that the accumulators were grabbed correctly.
3. Check the inner union proofs to ensure that the unions were conducted correctly.
4. Check the intersection proofs to ensure that the intersections were conducted correctly.
5. Check the outer union proof to ensure that it was conducted correctly.
6. Finally, check the property proof to ensure that the result is correct.

In the image below is a birdseye view of the process, assuming count as the property check.

​

Query Example

Let’s say we want to find all users with a Masters or PhD who live in London or Istanbul. Our query would be.

To conduct this we would:

1. Grab the accumulators for Masters and PhD, and conduct a union on them.
2. Grab the accumulators for London and Istanbul, and conduct a union on them.
3. Conduct an intersection on the two unions.
4. Conduct the outer union on the intersection (in this case there is only one accumulator, so this step is redundant).
5. Count the number of users that satisfy the query (this is the degree of the accumulator polynomial we just made).

If we wanted to include the outer union necessity, we could instead query for all users with a Masters or PhD who live in London or Istanbul, or users with a Masters in Hong Kong. This would be.