Context

Join Queries: $Q(x_1, \dots, x_n) = \bigwedge_{i=1}^k R_i(\vec{z_i})$

where $\vec{z_i}$ tuple over $X = \{x_1,\dots,x_n\}$

Example: $Q(city, country, name, id) = People(id, name, city) \wedge Capital(city, country)$

Direct Access

Given $Q(\vec{x})$ and $\mathbb{D}$, simulate array access to $Q(\mathbb{D})$ where $Q(\mathbb{D})[k]$ is the $k^{th}$ element of $Q(\mathbb{D})$ by lexicographical order.

Tractable Join Queries and Direct Access

• Result generalizes to computing $\#Q(\mathbb{D})$…
• And to direct access
• HoF: Bagan, Durand, Olive, Grandjean, Carmeli, Tziavelis, Gatterbauer, Kimelfeld, Riedewald, Bringmann, Mengel, Schweikardt, Zeevi, Berkholz.

Acyclic queries

Central class of join queries because of their tractability.

$$R_1(x,y,z) \wedge R_2(x,z,u) \wedge R_3(x,y,t) \wedge R_4(y,t) \wedge R_5(y,v)$$

Yannakakis Algorithm

Twisting Yannakakis for Counting

Direct Access on Acyclic Queries

Acyclicity and elimination order

An $\alpha$-leaf in a hypergraph $H=(V,E)$ is $x \in V$ such that there is $e \in E$, $N(x) \subseteq e$.

Direct Access on Acyclic Queries

Algorithm schema:

1. Construct a join tree “compatible” with the $\alpha$-elimination order
2. Load data in the join tree, anontate tuples with number of extension.
3. Use top-down induction on the annotated join tree to answer DA query $Q(\mathbb{D})[k]$.

Yannakakis and circuits

Factorised DB POV: the trace of Yannakakis Algorithm is roughly a decision-DNNF of size linear.

Ordered decision circuit

Exhaustive DPLL, Join Queries and Circuit: Yannakakis Upside-down

Let $Q$ be a JQ and $x_n, \dots, x_1$ an $\alpha$-elimination order of $Q$.

• $Q(\mathbb{D}) = \biguplus_{d \in D} Q[x_1 = d](\mathbb{D})$
• If $Q = Q_1 \wedge Q_2$ and $var(Q_1) \cap var(Q_2) = \emptyset$ then $Q(\mathbb{D}) = Q_1(\mathbb{D}) \times Q_2(\mathbb{D})$
• Implement this rules recursively + cache already computed queries $Q'$

Solving Direct Access on Circuits: Precomputation

Precomputation: Compute for each decision gate $v$ on $x$ and value $d$, how many solutions of $v$ we can build by setting $x$ to $d' \leq d$.

Solving Direct Access on Circuits: Access

Find the $7^{th}$ solution.

Access: construct the $k^{th}$ solution one variable at a time.

Solving Direct Access on Circuits: Access

Find the $13^{th}$ solution.

Access: construct the $k^{th}$ solution one variable at a time.

Direct Access for JQs from Circuits

Algorithm schema:

Differences between both approaches

Negative Join queries

Negative Join Queries (NJQ): $Q(x_1, \dots, x_n) = \bigwedge_{i=1}^k \neg R_i(\vec{z_i})$

• Big difference:
  • positively encoding $\neg R(\vec{z})$ on domain $D$ need $(D^{|\vec{z}|}-\#R)$ tuples.
  • if $Q$ is tractable for every $\mathbb{D}$ then every $Q' \subseteq Q$ is tractable too because we can set $R_i = \emptyset$ in the database, which does not happen in the positive case.

$\beta$-acyclic queries

Good candidates for tractability of Negative Join Queries: every $Q' \subseteq Q$ is acyclic.

Compiling $\beta$-acyclic NJQ

Corollary: Direct Access for $\beta$-acyclic NJQ with $O(poly(|\mathbb{D}|))$ preprocessing and access time $O(polylog(|\mathbb{D}|)poly(|Q|))$ for lexicographical orders based on (reversed) $\beta$-elimination orders.

Going further

Technique generalizes to:

Conclusion

• Circuit based tractability of queries is powerful and modular
• Deports the heavy lifting to the compilation part, treating the circuit is usually easier than working on annotated join trees.
• Future work:
  • generalize FAQ/AJAR style queries to JNQ by working directly on the circuit
  • Better understanding on the new width measures