#StackBounty: #complexity #db.databases #query-complexity #model-checking #finite-model-theory What is the impact of encodings of spars…

Bounty: 150

Some preliminaries first.
Consider a purely-relational structure (a.k.a. database) $mathfrak{A} = (A, R_1^{mathfrak{A}}, ldots, R_{|tau|}^{mathfrak{A}})$ over some finite signature $tau = { R_1, R_2, ldots, R_{|tau|} }$, where each relational symbol $R_i$ has an associated arity $mathsf{ar}(R_i)$. We assume that $A$ is ordered in some way, just for the sake of encodings.

There are two different ways to represent $mathfrak{A}$ in the memory: one way comes from finite model theory, the second one from database theory. Let me call them the matrix encoding and the list encoding and define $|mathfrak{A}|$ as the size of its encoding.

  1. In the matrix encoding the structure $mathfrak{A}$ is represented as $1^{|A|} cdot 0 cdot mathsf{enc}(R_1) cdot mathsf{enc}(R_2) cdot ldots cdot mathsf{enc}(R_{|tau|})$, where $mathsf{enc}(R_i)$ is an $|A|^{mathsf{ar}(R_i)}$ bit string, with the intended meaning that its $j$-th bit is 1 iff the $j$-th $mathsf{ar}(R_i)$-tuple of $A$ belongs to $R_k^{mathfrak{A}}$.
  2. In the list encoding we encode the structure $mathfrak{A}$ as $1^{|A|} cdot 0 cdot mathsf{enc}(R_1) cdot mathsf{enc}(R_2) cdot ldots cdot mathsf{enc}(R_{|tau|})$, but this time $mathsf{enc}(R_i)$ just lists all the tuples included in $R_i^{mathfrak{A}}$.

Hence, $|mathfrak{A}| approx |A| + Sigma_{i=1}^{|tau|} |A|^{mathsf{ar}(R_i)}$ in the matrix encoding, while $|mathfrak{A}| approx |A| + Sigma_{i=1}^{|tau|} mathsf{ar}(R_i) cdot |R_i^{mathfrak{A}}|$ in the list encoding.
Note that the difference between the encoding is when we have a symbol $S$ of high-arity, let’s say $n$ and there are only a few tuples in $S^{mathfrak{A}}$. Then in the list encoding we will have only a few tuples included, so the representation of $mathfrak{A}$ will be short, while in the matrix encoding we will store all the possible bits, no matter whether a tuple belongs to the relation $S^{mathfrak{A}}$ or not. This seems to be also crucial when we have queries with negation: the relation itself can be "small" but its complement can be "huge", but the complement is not stored directly.

Finally, here comes my question. Do you know any logic (or query language) $mathcal{L}$ for which the combined complexity of the model-checking problem (or query evaluation problem) differs (i.e. we have $mathfrak{A}$ and a formula $varphi$ as an input and we ask if $mathfrak{A} models varphi$ holds)? Of course the signature may differ for different structures. And we need to exploit negations and higher-arity relations somehow.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.