Papers for

database query planners

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

New math shows difference in ordering constraints for puzzles

Separating Non-redundancy and Chain Length

Abstract: For a constraint satisfaction problem defined by a relation $R$, its non-redundancy $\text{NRD}(R,n)$ is the size of largest instance (as a function of the number $n$ of variables) for which no constraint is implied by the rest. Its chain length $\text{CL}(R,n)$ is the largest such instance where the constraints can be ordered so that no constraint is implied by the preceding ones. Clearly $\text{CL}(R,n) \ge \text{NRD}(R,n)$ but so far no asymptotic separation was known between these quantities. We exhibit an explicit arity $4$ relation for which $\text{CL}(R,n) \ge ω(\text{NRD}(R,n))$.

Tue 15 SeptComputational Complexity

The gist

When solving puzzles or problems that have many rules, sometimes some rules are leftovers or repeated. The paper looks at two ways to measure how big these puzzle-like problems can get before some rules are unnecessary. The authors found an example where one way to measure can be much bigger than the other, proving they are not always the same size. This helps better understand how the structure of these problems works.

Open → 2609.17914v1