Direct Access for Conjunctive Queries with Negations

Join Queries

Join Query : $Q(x_1, \dots, x_n) = \bigwedge_{i=1}^k R_i(\mathbf{x_i})$

where $\mathbf{x_i}$ is a tuple over $X = \{x_1,\dots,x_n\}$

Direct Access

Quickly access $Q(\mathbb{D})[k]$, the $k^{th}$ element of $Q(\mathbb{D})$.

Naive Direct Access

Naive algorithm: materialize $Q(\mathbb{D})$ in an array, sort it. Access.

Orders

Applications

Direct Access generalizes many tasks that have been previously studied:

• Uniform sampling without repetitions
• Ranked enumeration
• Counting queries:
  • how many answers between $\tau_1$ and $\tau_2$?
  • how many answers extend a partial answer etc.

Beating Naive Direct Access

Naive Direct Access:

• Preprocessing at least $O(\#Q(\mathbb{D}))$.
• Access time $O(1)$.

Complexity of Direct Access

Computing $\#Q(\mathbb{D})$ given $Q$ and $\mathbb{D}$ is $\#P$-hard.

An easy query?

$$Q(a,b,c) = A(a,b) \wedge B(b,c).$$

A not so easy query

$$Q(a,c,b) = A(a,b) \wedge B(b,c).$$

Characterizing preprocessing time

Given a query $Q$ and order $\pi$ on its variables, we can compute $\iota(Q,\pi)$ such that:

End of the story?

So, if we understand everything for Direct Access and lexicographical orders, what is our contribution?

Definition

$Q = \bigwedge_{i=1}^k P_i(\mathbf{z_i})$ $\bigwedge_{i=1}^l \lnot N_i(\mathbf{z_i})$

Negation interpreted over a given domain $D$:

Positive Encoding not Optimal

$Q(x_1,\dots,x_n) = \neg N(x_1,\dots,x_n)$, domain $\{0,1\}$.

Hardness of subqueries

Subqueries and negative atoms

Measuring hardness of SJQ

Good candidate for $Q = Q^+ \wedge Q^-$:

For $Q$ a (positive) JQ signed JQ, and $\pi$ a variable ordering, we can solve DA with

• Preprocessing $\tilde{O}(|\mathbb{D}|^{\iota(Q,\pi)})$ $\tilde{O}(|\mathbb{D}|^{1+show(Q,\pi)})$
• Access time $O(\log |\mathbb{D}|)$

A word on show

Signed HyperOrder Width (and incidentally, our result) generalizes:

• $\beta$-acyclicity (#SAT and #NCQ are already known tractable)
• signed-acyclicity (Model Checking for SCQ known to be tractable)
• Nest set width (SAT / Model Checking for NCQ known to be tractable)

Basically, everything that is known to be tractable on SCQ/NCQ.

Relational Circuits

Ordered Relational Circuits

Direct Access on Relational Circuits

Preprocessing

Idea : for each gate $v$ over $x_i$ and for each domain value $d$

compute the size of the relation where $x_i$ is set to a value $d'\leqslant d$

Preprocessing

Direct Access 7th solution

Compute the 7^th solution $\to$ 111

Direct Access the 13th solution

Compute the 13^th solution $\to$ 221

Solving DA for SCQ

SCQ $Q(x_1,\dots,x_n)$, $\pi = (x_1,\dots,x_n)$.

Preprocessing: $\tilde{O}(|\mathbb{D}|^{1+show(Q,\pi)})$

1. Construct $\pi$-ordered circuit $C$ of size $\tilde{O}(|\mathbb{D}|^{1+show(Q,\pi)} poly(Q))$
2. Preprocess $C$ in time $O(|C| \log |\mathbb{D}|)$.

Direct Access : $O(\log |\mathbb{D}|)$

1. Directly on $C$
2. in time $O(n\log |D|)$ !

DPLL: building circuits

Compilation based on a variation of DPLL :

1. $Q(\mathbb{D}) = \biguplus_{d \in D} [x_1 = d] \times Q[x_1=d](\mathbb{D})$
2. $Q(\mathbb{D}) = Q_1(\mathbb{D}) \times Q_2(\mathbb{D})$ if $Q = Q_1 \wedge Q_2$ with $var(Q_1) \cap var(Q_2) = \emptyset$
3. Top down induction + caching

Other usage of circuits

1. Extension to $\exists$SJQ:
   • Last variable in $C$ can be existentially projected without increase in circuit size
   • Give DA for $\exists x_{k}, \dots, x_n Q(x_1,\dots,x_n)$.
2. Semi-ring Aggregation
   • $w : X \times D \rightarrow (\mathbb{K}, \oplus, \otimes)$
   • Compute $\bigoplus_{\tau \in Q(\mathbb{D})} \bigotimes_{x \in X} w(x, \tau(x))$

Work in progress

1. Improve preprocessing
   $(||^{show(Q,)+1})$
   doable with a few tweaks in DPLL, joint work with S. Salvati.
2. Lower bounds: preprocessing in $|\mathbb{D}|^{show(Q,\pi)}$
   unavoidable under Zero-clique conjecture (join work with N. Carmeli).
3. Aggregation
   $Q(x_1,\dots, x_k, F(x_{k+1}, \dots, x_n))$, generalizing work by I. Eldar, N. Carmeli, B. Kimelfeld.