arXiv CSopen access

Lexicographic Direct Access with Functional Dependencies

Lexicographic Direct Access with Functional Dependencies Florent Capelli Univ. Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), Lens, France

Nofar Carmeli # Inria, LIRMM, University of Montpellier, CNRS, France

Stefan Mengel Univ. Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), Lens, France

arXiv:2607.13875v1 [cs.DB] 15 Jul 2026

Abstract We study the complexity of lexicographic direct access to join query answers over databases that satisfy functional dependencies (FDs). More precisely, we give fine-grained lower and upper bounds on the preprocessing time required to achieve polylogarithmic access time. We start by considering the simple approach of a reordered extension, which first incorporates the FDs in the query and order, and then ignores the FDs during evaluation. We show that this simple approach gives tight bounds for unary FDs but fails for general FDs. We then consider a second approach, inspired by size bounds for query answers using information theory, that takes the FDs into account while materializing the bags of a decomposition tailored to the direct access task at hand. Interestingly, we show that the same reordering is also useful while constructing the decomposition in this second approach for reducing the complexity. While the obtained upper and lower bounds are generally not tight, we show that they yield a complete characterization of lexicographic direct access with linear preprocessing time. All lower bounds in this paper apply only to queries without self-joins and rely on the Zero-Clique Conjecture. 2012 ACM Subject Classification Theory of computation → Database theory Keywords and phrases join queries, direct access, functional dependencies Acknowledgements The authors would like to thank Mahmoud Abo Khamis for helpful clarifications on the PANDA algorithm.

1

Introduction

Recent years have seen steady progress in the understanding of the complexity of conjunctive query evaluation. On the one hand, worst-case optimal evaluation algorithms [25, 26, 24, 12] have been a breakthrough and have recently been combined with fast matrix multiplication to give even better runtimes [17, 2, 20]. On the other hand, techniques and conjectures from fine-grained complexity theory have been used to show lower bounds for many different query answering settings. In particular, this has lead to a good understanding of the classes of queries that can be solved in linear time for many query answering settings [9, 23]. However, almost all of the above lower bound results are only for the case without any constraints in the input database, while on the algorithmic side it is known that different constraints on the data can lead to huge speedups [5, 16]. Functional Dependencies (FDs) [1, Part C] form a simple class of database constraints of great practical importance, especially since they are crucial for database normalization [21]. This combination of simplicity and importance has led to a significant amount of work on them in database theory [19, 18, 4, 13, 3], and yet, even for FDs, very few lower bounds are known [13, 14], and linear-time characterizations are largely lacking. In this paper, we make a step towards a better understanding of the complexity of join query answering under constraints. Even though we focus on join queries, some of our results

2

Lexicographic Direct Access with Functional Dependencies

also apply to conjunctive queries (including projection). We study lexicographic direct access to query results under FDs. The aim of direct access is to, after some preprocessing, allow access to the query answers as if they were materialized into a sorted array. Often it is possible to do so without actually computing the query result, using a preprocessing that is far more efficient [8, 10, 14, 11]. We remark that direct access can be used to efficiently compute quantiles and histograms and also to support sampling without repetitions [15]. We focus on direct access in which the underlying query order is lexicographical, according to a variable order defined by the user together with the query. Without FDs, we know the optimal preprocessing required to get access in logarithmic time [11]. The hardness part of this result, like all hardness results in the RAM computation model, is a conditional lower bound, relying on the assumed hardness of a well-studied problem. In this case, just like the lower bounds we show in this paper, it assumes the Zero-Clique Conjecture. We here study how this complexity changes in the presence of FDs. For lexicographic direct access over databases satisfying a given set of FDs, Tziavelis et al. [14] studied the case that all FDs are unary (i.e., one variable implies another), and showed a dichotomy that identifies which combinations of conjunctive query, variable order, and FD set admit an algorithm with quasilinear preprocessing and logarithmic access time. The hardness part of this dichotomy, like most lower bounds in the field and the lower bounds shown in this paper, is restricted to queries without self-joins; that is, every query atom uses a distinct relation. This dichotomy is obtained with the approach of reordered extensions. The idea of this approach is to rewrite the query to incorporate the extra information that can be obtained from the FDs in order to end up in an equivalent setting without FDs. Then, known results for the general setting can be applied to derive the complexity of the setting with FDs. For this to work also for the lower bounds, the specified variable order is reordered to take the FDs into account. We show that for unary FDs, this simple approach is surprisingly powerful, beyond the linear preprocessing dichotomy: it allows to completely understand the complexity of lexicographic direct access under unary FDs, identifying the optimal preprocessing time required to obtain logarithmic access time. We generalize the extension-based approach beyond unary FDs. However, we show that, in this general case, the obtained algorithm is not optimal. Interestingly, this gap occurs even in the restricted case that the underlying query is acyclic, in contrast to the related problem of enumeration where the extension-based approach is known to be tight for acyclic queries [13]. Following the failure of reordered extensions for direct access, we turn to techniques based on information theory, and in particular, the celebrated PANDA algorithm for join evaluation [5]. We combine it with direct access techniques [11, 14] by taking the FDs into account when inspecting the complexity of materializing the bags of a so-called disruptionfree-decomposition. Interestingly, we show that the same reordering from the extension approach is also useful while constructing the decomposition in this second approach for reducing the complexity. To complement the algorithm with lower bounds, we use a coloring technique that was previously used to bound the size of query results [19]. Unfortunately, our complexity upper and lower bounds are generally not tight, which stems from the fact that the corresponding bounds on join sizes based on the so-called polymatroid bound are generally also not tight. Thus, similarly to the case of join size computation and worst-case optimal join algorithms, fully resolving the complexity of direct access under FDs would likely require fundamental advances in information theory. We do show that our algorithms and lower bounds form a dichotomy characterizing the combinations of join query, variable order, and FD set that admit lexicographic direct access with linear preprocessing and logarithmic access time (for general FDs).

F. Capelli, N. Carmeli, S. Mengel

Finally, we compare the two approaches presented in this paper. We show that the algorithm based on information-theory techniques is always at least as good as the extensionbased algorithm and sometimes better, but that in the case of unary FDs, both algorithms yield the same complexity. We give preliminary notation and recall useful known results in Section 2. We study the extension-based approach in Section 3. For our second approach, the algorithm is devised in Section 4, the lower bound in Section 5, and the linear preprocessing dichotomy in Section 6. Finally, we compare the two approaches in Section 7, and we conclude in Section 8.

2

Preliminaries

Given a natural number n, we set [n] := {1, . . . , n}. Given a tuple ⃗a = (a1 , . . . , an ), we set ⃗a[i] := ai . Given an ordering π, we write a ≤π b to say that a appears before b in π. Databases. A schema is a set of relational symbols. Each relational symbol R is associated with a natural number arity(R), called the arity of R. A database D over the schema S contains a finite relation RD ⊆ domarity(R) for each R ∈ S, where dom is a set of constant values called the domain. We sometimes write R instead of RD when D is clear from the context. If (c1 , . . . , carity(R) ) ∈ RD , then the expression R(c1 , . . . , carity(R) ) is called a fact of D. The size of a database D, denoted |D|, is the number of facts it contains. The database schemas we consider are extended with Functional Dependencies (FDs). An FD is an expression of the form R : A → B, where A, B ⊆ [arity(R)]. A database satisfies such an FD if for every two facts R(t1 ), R(t2 ) of D, we have that if t1 [i] = t2 [i] for all i ∈ A, then t1 [j] = t2 [j] for all j ∈ B. If the schema S contains a set ∆ of FDs, a database over S must satisfy all FDs in ∆. We may assume without loss of generality that all FDs are of the form Ri : A → b where b is a single variable because we can replace an FD of the form Ri : A → B with a set of FDs {Ri : A → b | b ∈ B}. If |A| = 1, the FD is called unary. Queries. A conjunctive query (CQ) Q over schema S is an expression of the form Q(⃗x) ← R1 (⃗x1 ), . . . , Rℓ (⃗xℓ ), where the tuples ⃗x, ⃗x1 , . . . , ⃗xℓ hold variables, every variable in ⃗x appears in some ⃗x1 , . . . , ⃗xℓ , we have that R1 , . . . , Rℓ ∈ S, and ⃗xi has the same arity as Ri for all i ∈ [ℓ]. Each Ri (⃗xi ) is called an atom of the query Q, and the set of all atoms is denoted by atoms(Q). When we do not need to refer to the order of variables within an atom Ri (⃗xi ), we sometimes denote it by Ri (Xi ) for simplicity, where Xi is a set of variables. We use var(Q) for the set of variables that appear in Q. The variables ⃗x are called free. We say that variables that are not free are projected. If the CQ does not contain projections, i.e., all query variables are free, it is called a join query. A repeated occurrence of a relational symbol in two different atoms is a self-join, and if no self-joins exist, the CQ is called self-join-free. A homomorphism from a CQ Q to a database D is a mapping of var(Q) to constants from dom such that every atom of Q maps to a fact of D. A query answer is such a homomorphism followed by a projection on the free variables. The set of query answers is denoted Q(D). In the context of answering a CQ, we can assume without loss of generality that FDs are expressed using the query variables [14, Section 8]. That is, if the database contains the FD Ri : A → b, and the query contains the atom Ri (⃗xi ), we can denote by Y and {z} the sets of variables in positions A and {b} respectively of ⃗xi , and specify the FD as Ri : Y → z. When Ri is clear or irrelevant, we denote the FD simply by Y → z, and we say that Y implies z. We write Y →∗ Z when every variable of Z is transitively implied by some subset of Y . Hypergraphs and query structure. A hypergraph (V, E) is a set V of vertices and a set E of subsets of V called hyperedges. Two vertices are neighbors if they appear in the same hyperedge. A path is a sequence of vertices such that every two succeeding vertices

3

4

Lexicographic Direct Access with Functional Dependencies

are neighbors. Given a set S of vertices, we denote by N (S) the set containing all vertices that have a neighbor in S. Two vertices are connected if there is a path between them. A connected component is a maximal set of vertices such that every two vertices of the set are connected. A join tree of a hypergraph (V, E) is a tree where the nodes are the hyperedges E and the running intersection property holds, namely: for all u ∈ V the set {e ∈ E | u ∈ e} forms a (connected) subtree. A hypergraph is acyclic if it has a join tree. We associate a hypergraph HQ = (V, E) to a CQ Q where the vertices are the variables of Q, and every atom of Q corresponds to a hyperedge with the same set of variables. A CQ Q is acyclic if HQ is acyclic, and otherwise it is cyclic. Lexicographic direct access. Lexicographic direct access, sometimes simply called direct access, is a task defined by a query Q and an ordering π of its free variables. Given an input database D, after a preprocessing phase, the user can specify an index j and expects the jth answer in Q(D) according to the lexicographic order corresponding to π or an out-of-bounds error if there are fewer than j answers. When the valid inputs to the problem are restricted to those satisfying a set ∆ of FDs, we specify such a task by the triple (Q, π, ∆). The time it takes to provide an answer given an index is called the access time. As in previous work, as a computation model, for an input of size n, we use the word-RAM model with O(log(n))-bit words and unit-cost operations. V Given k ∈ N, the k-star query is defined as Q⋆k (x1 , . . . , xk+1 ) ← i∈[k] Ri⋆ (xi , xk+1 ). A variable ordering for Q⋆k is called bad if xk+1 is last. The following hardness result is obtained by combining Proposition 19, Lemma 22, and Theorem 23 by Bringmann et al. [11]. ▶ Theorem 2.1 ([11]). Let 2 ≤ k ∈ N. Assuming the Zero-Clique Conjecture, there is no ε > 0 such that for all δ > 0 there is a direct access algorithm for Q⋆k with respect to a bad ordering with preprocessing time O(|D⋆ |k−ε ) and access time O(|D⋆ |δ ). In the Zero-k-Clique problem, given an n-node graph with integer edge weights in [−nc , . . . , nc ] for some constant c ≥ 1, the task is to decide whether the graph contains a k-clique with total weight 0. The Zero-Clique Conjecture states that, for every k ≥ 3, there is no constant ε > 0 such that Zero-k-Clique has a randomized algorithm running in time O(nk−ε ) [11]. Disruption-free decompositions and the incompatibility number. Let Q(X) ← R1 (X1 ), . . . , Rℓ (Xℓ ) be a join query and π = (v1 , . . . , vn ) an ordering of its variables. For every i ∈ [n], we denote by Q[vi , . . . , vn ] the query Q(X ∩ {xi , . . . , xn }) ← R1 (X1 ∩ {xi , . . . , xn }), . . . , Rℓ (Xℓ ∩ {xi , . . . , xn }). Denote by Si the vertices in the connected component of vi in Q[vi , . . . , vn ]. The disruption-free decomposition of Q according to π is defined1 to be the hypergraph (var(Q), {B1 , . . . , Bn }) where Bi := {vi } ∪ {vj | j < i, vj ∈ N (Si )} for i ∈ [n]. We call the sets Bi the bags of the decomposition and say that vi is the variable creating the bag Bi . The join query with an atom Ri (Bi ) for every bag Bi of the disruption-free decomposition admits lexicographic direct access according to π with O(|D|) preprocessing and O(log(|D|)) access time over a database D [11, 14]. Given a hypergraph H = (V, E) and a set of vertices S ⊆ V , a fractional edge cover of S P using H is a mapping µ : E → [0, 1] such that for every v ∈ S we have e:v∈e µ(e) ≥ 1. The P fractional edge cover number of S using H is ρ∗H (S) := minµ e∈E µ(e), where the minimum is taken over all fractional edge covers of S using H. We remark that it can be computed 1

In the definition by Bringmann et al. [11], disruption-free decompositions are also defined to contain a hyperedge for every atom of Q. Since every atom is contained in the bag created by its largest variable, and adding or removing hyperedges contained in the created bags does not make a difference for our purposes, we chose the current definition for simplicity.

F. Capelli, N. Carmeli, S. Mengel

efficiently by linear programming. The incompatibility number ι of Q and π is defined to be the maximum fractional edge cover number of a bag of the disruption-free decomposition using the query hypergraph. That is, ι(Q, π) = maxi∈[n] ρ∗Q (Bi ). ▶ Example 2.2. Consider Q(v1 , v2 , v3 , v4 , v5 ) ← R1 (v1 , v4 ), R2 (v4 , v3 ), R3 (v3 , v5 ), R4 (v5 , v2 ) and π = (v1 , v2 , v3 , v4 , v5 ). We get that S5 = {v5 }, S4 = {v4 }, S3 = {v3 , v4 , v5 }, S2 = {v2 , v3 , v4 , v5 }, and S1 = {v1 , v2 , v3 , v4 , v5 }. The resulting bags are B5 = {v2 , v3 , v5 }, B4 = {v1 , v3 , v4 }, B3 = {v1 , v2 , v3 }, B2 = {v1 , v2 }, and B1 = {v1 }. The biggest fractional edge cover number out of these bags is that of B3 , which is 3, so ι(Q, π) = 3. The incompatibility number determines the preprocessing time for direct access as follows: ▶ Theorem 2.3 ([11]). Given a join query Q and an ordering π of its variables, lexicographic direct access for (Q, π) is possible with O(|D|ι(Q,π) ) preprocessing time and O(log(|D|)) access time, and there is no constant ε > 0 such that for all δ > 0 Lexicographic direct access for (Q, π) is possible with preprocessing time O(|D|ι(Q,π)−ε ) and access time O(|D|δ ), assuming the Zero-Clique Conjecture. The Polymatroid Bound and the PANDA Algorithm. We next present some basics on the polymatroid bound, slightly adapted to our setting. Let V be a finite set. A set function is then a function h : 2V → R+ . If for all A ⊆ B ⊆ V we have h(A) ≤ h(B), we say that h is monotone. We call h submodular if for all A, B ⊆ V we have h(A) + h(B) ≥ h(A ∪ B) + h(A ∩ B). If h is monotone and submodular and we have h(∅) = 0, we also call it a polymatroid. We will only be interested in polymatroids whose V ground set V is the set of variables of a CQ. So fix a query Q(X) := i∈[k] Ri (Xi ) and let S V := i∈[k] Xi . We say that a polymatroid h is guarded by Q if for all i ∈ [k], we have h(Xi ) ≤ 1. We say that h respects an FD Y → z, if h(z | Y ) := h(Y ∪ {z}) − h(Y ) = 0. We will be interested in the set function defined for every S ⊆ V by PQ,∆ (S) := maxh h(S) where the maximum is taken over all polymatroids that are guarded by Q and respect all FDs in ∆. Remark that PQ,∆ (S) is the solution of a linear program with integer coefficients with the variable set {h(Y ) | Y ⊆ V } and as constraints the submodularity and monotonicity requirements as well as the guardedness. Since we assume that every variable of Q is in an atom, PQ,∆ (S) is always bounded by a finite number; for example, |S| is a very P crude upper bound because h(S) ≤ x∈S h({x}) ≤ |S| holds for every h by submodularity and monotonicity and the fact that for every x there is i ∈ [k] with x ∈ Xi and thus h({x}) ≤ h(Xi ) ≤ 1. As the solution of a linear program with a bounded target function, PQ,∆ (S) is computable and always a rational number. We are interested in PQ,∆ (S) because of the following result often called the polymatroid bound2 . ▶ Theorem 2.4 ([19, 4]). Let Q(X) be a CQ and ∆ a set of FDs. For every database D that respects the constraints in ∆, we have that |Q(D)| ≤ |D|PQ,∆ (X) . Due to Theorem 2.4, we call the function PQ,∆ the exponent of the polymatroid bound. A fundamental result from [4] is that the polymatroid bound is essentially also a runtime bound for CQ evaluation. In particular, there is an algorithm (called PANDA) that for every

2

To avoid confusion, we remark that in [4], PQ,∆ (S), using different notation, is scaled by a logarithmic factor compared to [19]. This difference is purely arithmetic and does not change the polymatroid bound. We here use the variant from [19] since it better matches our asymptotic perspective.

5

6

Lexicographic Direct Access with Functional Dependencies

CQ Q(X) with a set of FDs ∆ does the following: given a database D respecting ∆, PANDA computes a relation R ⊇ Q(D) in time polylog(|D|)|D|PQ,∆ (X) . Note that, we cannot expect the PANDA algorithm to compute Q(D) exactly, since doing so might be computationally hard even if the polymatroid bound is small. For example, Q can be a clique query of which we only want the projection to a single variable. This query has polymatroid bound 1, but for big enough cliques we cannot even expect to decide in linear time if it has any answers, assuming the exponential time hypothesis, see e.g. [22]. When considering join queries (without projections), this does not happen: in that case, we can always simply filter the relation R computed by PANDA with all atoms to compute Q(D) in time polylog(|D|)|D|PQ,∆ (X) , see [4] for details.

3

Reordered Extensions

In this section, we inspect the approach of achieving direct access with FDs using a reduction to a reordered extension without dependencies, and we show that this approach yields optimal preprocessing time (up to sub-polynomial factors) for logarithmic access time in the case of unary FDs. We first provide a natural generalization of ∆-reordered extensions [14] for general FDs. ▶ Definition 3.1 (∆-reordering). Given a CQ Q, a set of FDs ∆, and an ordering π of variables from Q, we say that π ′ is a ∆-reordering of π if it can be obtained by the following procedure: Initialize π ′ empty. Then, for every variable v according to the order π: if v is not in π ′ , append it to π ′ ; then, for every FD Y → y with Y in π ′ and y not in π ′ , append y to π ′ . We say that π is consistent with respect to ∆ if it is a ∆-reordering of itself. We remark that a problem may admit more than one ∆-reordering, and any choice of reordering will work for our purposes. As an example, given the FDs x → y and x → z and π = (x), both (x, y, z) and (x, z, y) are valid reorderings. The reordering serves as a way of representing the problem’s complexity more directly without changing the query answering problem. In other words, for every database D that satisfies ∆, ordering Q(D) by π is the same as ordering it by its ∆-reordering π ′ . ▶ Observation 3.2. Given a CQ Q, a set of FDs ∆, a variable order π, and a ∆-reordering π ′ of π, then the triples (Q, π ′ , ∆) and (Q, π, ∆) induce the same output in the same order. ∆-reordered extensions extend the atoms and head of CQs using the FDs, in addition to reordering the required variable order. ▶ Definition 3.3 (∆-reordered extension). Given a self-join free CQ Q(X), a set of FDs ∆, and a variable order π, their ∆-reordered extension is a CQ Q+ (X + ), a set of FDs ∆+ and a variable order π + defined as follows. Q+ body and ∆+ are obtained as the fixpoint of the following extension step: Given an FD Y → z ∈ ∆, if Y ⊆ Xi and z ∈ / Xi for some atom Ri (Xi ), then increase the arity of Ri by one, replace Ri (Xi ) with Ri (Xi , z), and add Ri : Y → z to the FD set ∆+ . Q+ head is obtained as the fixpoint of the following extension step, starting with X + := X: given an FD Y → z ∈ ∆, if Y ⊆ X + and z ∈ / X + , then add z to X + . + π is a ∆-reordering of π. We will next use exact reductions to connect the complexity of a direct access problem and its ∆-reordered extension. Given a variable order π, and query answers a1 , a2 , we denote by a1 ⪯π a2 the fact that a1 appears before a2 in the lexicographic order defined by π.

F. Capelli, N. Carmeli, S. Mengel

Consider CQs Q and Q′ , FD sets ∆ and ∆′ , and variable orders π and π ′ . We say that there is an exact reduction from (Q, π, ∆) to (Q′ , π ′ , ∆′ ) if for every database D that satisfies ∆, we can construct in linear time a database D′ that satisfies ∆′ such that there is a bijection τ from Q′ (D′ ) to Q(D) that is computable in constant time, and for all query answers a1 , a2 of Q′ , we have that a1 ⪯π′ a2 iff τ (a1 ) ⪯π τ (a2 ). Building on a reduction by Carmeli and Kröll [13], we can reduce (Q, π, ∆) to (Q+ , π, ∆+ ). The latter represents the same problem as (Q+ , π + , ∆+ ) by Observation 3.2. Finally, as any database that satisfies ∆+ also satisfies ∅, this can be reduced to (Q+ , π + , ∅). Overall, we get an exact reduction from a problem to its ∆-reordered extension without FDs. ▶ Theorem 3.4. Given a self-join-free CQ Q, a variable order π, and a set of FDs ∆, there is an exact reduction from (Q, π, ∆) to (Q+ , π + , ∅). Theorem 3.4 implies an algorithm for (Q, π, ∆) with the same time guarantees we have for Q+ and π + without FDs. ▶ Corollary 3.5. Given a self-join-free join query Q, an ordering π of its variables, and a set ∆ of FDs, let ι be the incompatibility number of their reordered extension Q+ and π + . Lexicographic direct access for (Q, π, ∆) is possible with O(|D|ι ) preprocessing time and O(log(|D|)) access time. This algorithm is obtained by applying the reduction from Theorem 3.4, and then the algorithm from Theorem 2.3. Is this the most efficient way of solving (Q, π, ∆)? In case ∆ contains only unary FDs, we answer this question positively using an exact reduction in the opposite direction in Section 3.1; we answer it negatively for general FDs in Section 3.2.

3.1

Unary FDs

In case ∆ contains only unary FDs, we can show an exact reduction from (Q+ , π + , ∅) to (Q+ , π + , ∆+ ). Let us demonstrate this reduction using an example. Consider ∆ = {x1 → x3 }, the join query with the body R(x1 , x3 ), S(x3 , x2 ) which is the same as its extension, and the order π = (x1 , x2 , x3 ) which becomes π + = (x1 , x3 , x2 ). For every fact R(c1 , c3 ), the construction will introduce the fact R((c1 , c3 ), c3 ), whereas the facts in S stay the same. An answer (c1 , c3 , c2 ) to the original instance corresponds to an answer ((c1 , c3 ), c3 , c2 ) to the constructed instance. The answers we obtain conform to the order π + . We remark that we would not be able to have a similar construction with the order π because we would need the answers to be sorted by c2 before they are sorted by c3 , but c3 appears as part of the concatenated value of x1 while c2 does not. Since (Q+ , π + , ∆+ ) and (Q+ , π, ∆+ ) represent the same problem, and since Carmeli and Kröll [13] provide a reduction from (Q+ , π, ∆+ ) to (Q, π, ∆), we get the following. ▶ Theorem 3.6. Given a self-join-free CQ Q, a variable order π, and a set of unary FDs ∆, there are exact reductions in both directions between (Q, π, ∆) and (Q+ , π + , ∅). Theorem 3.6 implies that, in case of unary FDs, the complexity of lexicographic direct access (as well as any other problem closed under exact reductions, e.g., lexicographicallyordered enumeration) is the same as the complexity for the reordered extension without FDs, as long as the preprocessing is at least linear. As the complexity of lexicographic direct access for join queries is well understood, see Theorem 2.3, we can deduce a complexity result in the presence of unary FDs.

7

8

Lexicographic Direct Access with Functional Dependencies

▶ Corollary 3.7. Given a self-join-free join query Q, an ordering π of its variables, and a set of unary FDs ∆, let ι be the incompatibility number of their reordered extension Q+ and π + . Lexicographic direct access for (Q, π, ∆) is possible with O(|D|ι ) preprocessing time and O(log(|D|)) access time. There is no constant ε > 0 such that for all δ > 0 Lexicographic direct access for (Q, π, ∆) is possible with preprocessing time O(|D|ι−ε ) and access time O(|D|δ ), assuming the Zero-Clique Conjecture.

3.2

Challenges with general FDs

Let us notice that we cannot have a similar construction to that of Section 3.1 for general FDs. Consider the FD y1 , y2 → z and the join query with the body R(y1 , x1 ), S(y1 , y2 , z), T (y2 , x2 ), which is equal to its extension. A similar construction would copy the z value to y1 or y2 , but since z does not appear in all atoms where y1 and y2 appear, such a construction cannot be done in linear time and would not constitute an exact reduction. In fact, this is not just a problem with the specific construction: we will see in Example 3.8 that Corollary 3.7 does not hold for general FDs. That is, reordered extensions do not capture the direct access complexity in general. A natural question is whether reordered extensions capture the complexity in the restricted case of acyclic queries (and general FDs). We remark that, for enumeration with constant delay after linear preprocessing, ∆-extensions do capture all tractable cases for acyclic CQs, as they do for unary FDs, even though the general case is open [13]. One could expect that a proof in the spirit of that used for enumeration would also apply here. However, we found that this proof does not generalize to our case, and in fact, we answer this question negatively, as shown by the following acyclic example. ▶ Example 3.8. Consider Q(v1 , v2 , v3 , v4 , v5 ) ← R1 (v1 , v4 ), R3 (v4 , v3 , v5 ), R2 (v5 , v2 ), with the FD v4 , v5 → v3 , and the variable order π = (v1 , v2 , v3 , v4 , v5 ). The reordered extension is the same as the original problem. The incompatibility number is ι(Q, π) = ρ∗ (B3 ) = 3 because B3 = {v1 , v2 , v3 }. Thus, the optimal preprocessing time required for direct access with polylog access time for the reordered extension (Q+ , π + , ∅) is Θ(|D|3 ) up to subpolynomial factors by Theorem 2.3. However, the FDs reduce the complexity in this case, and there is an algorithm for direct access for (Q+ , π + , ∆+ ) = (Q, π, ∆) with preprocessing time O(|D|2 ), as we explain next. Consider the following algorithm. First, build a lookup table according to the FD in R3 . That is, given a pair (a4 , a5 ), the lookup table searches for a value a3 such that (a4 , a3 , a5 ) ∈ R3 . Note that, due to the FD, at most one such value exists. Then, for every (a1 , a4 ) ∈ R1 and (a5 , a2 ) ∈ R2 , search for (a4 , a5 ) in the lookup table, and if a value a3 is found, store (a1 , a2 , a3 , a4 , a5 ) as an answer to Q. Building the lookup table takes linear time, and it is used at most |D|2 times, with a constant time for each lookup. Overall, the algorithm takes O(|D|2 ) time to produce all the answers. We can now sort all answers, store them in an array, and support direct access with constant access time. The preprocessing time O(|D|2 ) is tight for our example (up to sub-polynomial factors) since we can use our query to solve Q⋆2 , as we sketch next. For every fact R1⋆ (a, c), introduce the facts R1 (a, c) and R3 (c, c, c). For every fact R2⋆ (b, c), introduce the fact R2 (c, b). This construction satisfies the FD as v3 , v4 , and v5 are always equal in R3 . As this is a lineartime exact reduction, direct access to our example cannot be faster than for Q⋆2 , which, by Theorem 2.1, requires essentially quadratic preprocessing. The next two sections devise general algorithms and lower bounds that correctly capture the complexity of this example.

F. Capelli, N. Carmeli, S. Mengel

4

9

An Algorithm Based on the Polymatroid Bound

In this section, we will show our main algorithmic result, an algorithm for direct access that uses PANDA. To this end, we define a generic way of defining width measures based on disruption-free decompositions and specialize this framework to apply the polymatroid bound. We then give an algorithm whose runtime is determined by the resulting measure. Finally, we show that this algorithm should be applied on a ∆-reordering to get better guarantees.

4.1

Width Measures for Disruption-Free Decompositions

This section introduces a width measure based on the polymatroid bound that captures the complexity we obtain when using PANDA over a decomposition for the preprocessing for direct access. We start in a slightly more abstract way, introducing a generic width measure which we then reuse in Section 5 for lower bounds. The underlying idea is the same as in [11]: we want to transform the input query into an acyclic query compatible with the given variable order (i.e., the incompatibility number is 1) and construct a matching database, so we can then simply run a direct access algorithm from [14]. The new query has atoms whose variable sets are the bags of the disruption-free decomposition, and the complexity bottleneck lies in materializing relations for these atoms. Without FDs, bounding this complexity by the AGM-bound of the bags using a worst-case optimal join algorithm yields an optimal approach [11]. For the case with FDs, there are generally no known tight bounds on join sizes and no worst-case optimal join algorithms, so we introduce a generic way of measuring the size of a bag which we then specialize for different applications. We now explain the technical details. ▶ Definition 4.1. Let π be a variable order of a join query Q(X), and let f : 2X → R+ . We define the disruption-free f -width of Q and π as f -width(Q, π) := maxi∈n f (Bi ), where {X, {B1 , . . . , Bn }} is the disruption free decomposition of Q according to π. We remark that this essentially the same as the definition of f -width proposed by Adler [7]. Notice that ρ∗Q -width(Q, π) is the incompatibility number of Q and π, as defined in Section 2. ρ∗

-width(Q+ ,π + )

Thus, the algorithm from Corollary 3.5 runs with preprocessing time O(|D| Q+ ). In this section, we will mostly be interested in the case where the function f from Definition 4.1 is the exponent of the polymatroid bound, in which case we call the resulting width measure PQ,∆ -width(Q, π) the disruption-free polymatroid bound of Q, ∆ and π. ▶ Example 4.2. Consider Example 3.8 again. We claim that PQ,∆ -width(Q, π) = 2. Set X := {v1 , v2 , v3 , v4 , v5 }. First note that B3 = {v1 , v2 , v3 }. It is readily checked that the set function defined by h(S) := |S ∩ {v1 , v2 }| is a polymatroid, guarded by Q, and respecting the FD v4 , v5 → v3 . Moreover, h(B3 ) = 2, so PQ,∆ -width(Q, π) ≥ h(B3 ) ≥ 2. Next, consider any polymatroid h guarded by Q and respecting the FD. We will show that h(Bi ) ≤ 2 for every bag Bi , which proves that PQ,∆ -width(Q, π) ≤ 2. First, by submodularity, we get h({v3 , v4 , v5 )}) + h(X \ {v3 }) ≥ h(X) + h({v4 , v5 }). Since h respects the FD, h({v4 , v5 }) = h({v3 , v4 , v5 }). So overall, h(X\{v3 }) ≥ h(X). Let Bi be any bag of the disruption-free decomposition, then h(Bi ) ≤ h(X) ≤ h(X \{v3 }) ≤ h({v1 , v4 })+h({v5 , v2 }) ≤ 2, where the first inequality is by monotonicity, the third by submodularity, and the fourth because h is guarded by Q. Overall, we get that PQ,∆ -width(Q, π) = 2.

4.2

The Algorithm

We get the following runtime bounds based on the disruption-free polymatroid bound.

10

Lexicographic Direct Access with Functional Dependencies

▶ Theorem 4.3. Let Q(X) be a join query, π a variable order, and ∆ a set of FDs. Then there is an algorithm that, given a database D that respects ∆, allows direct access on Q(D) with preprocessing time O(|D|PQ,∆ -width(Q,π) polylog(|D|)) and access time O(polylog(|D|)).3 Proof. Denote by Q′ the join query represented by the disruption-free decomposition of Q according to π (containing an atom for every bag). We will show how to build a database D′ such that Q(D) = Q′ (D′ ) in O(|D|PQ,∆ -width(Q,π) polylog(|D|)) time. As discussed in the preliminaries, we can then use a direct access algorithm from [14] for Q′ (D′ ) with linear preprocessing and logarithmic access time. This acts as a direct access algorithm for Q(D) with the required time bounds. Consider a bag Bi of the decomposition, and consider a CQ Qi (Bi ) representing this bag, with the same body as Q and the bag variables as the free variables. We can compute a relation Si ⊇ Qi (D) using PANDA in time |D|PQ,∆ (Bi ) polylog(|D|). This fits within the required time because PQ,∆ (Bi ) ≤ PQ,∆ -width(Q, π). We then filter Si by all atoms of Q that are contained in the bag. That is, if Ri (Xi ) is an atom of Q with Xi ⊆ Bi , remove from Si all facts that, projected to Xi , do not appear in RiD . Denote by D′ the obtained database, with a relation Si for each bag Bi of the decomposition. We have that Q(D) ⊆ Q′ (D′ ) because PANDA gives a superset of the answers Q(D) projected to the bag variables, and the filtering step does not remove answers of Q. We have that Q(D) ⊇ Q′ (D′ ) because the relations comprising D′ are filtered by all atoms of Q (since every atom of Q is contained in some bag). ◀ ▶ Example 4.4. Theorem 4.3 provides an algorithm for Example 3.8 with quadratic preprocessing since PQ,∆ -width(Q, π) = 2, as seen in Example 4.2.

4.3

The Effect of Reorderings

In Section 4.2, we have seen a direct access algorithm that is exponential in PQ,∆ -width(Q, π). From Observation 3.2, we know that we can reorder the variables specifying a desired lexicographic order in certain ways while maintaining the same answer order. The obvious question is then whether we should always do so, or whether leaving the variable order unchanged can yield faster preprocessing. This section shows that ∆-reorderings may decrease the disruption-free polymatroid bound, they never increase it, and every ∆-reordering yields the same bound. Thus, it is always a good idea to replace a variable order with an arbitrary ∆-reordering before applying the algorithm of Theorem 4.3. ▶ Proposition 4.5. Let Q be a join query, π a variable order, and ∆ a set of FDs. If π ′ and π ′′ are ∆-reorderings of π, then PQ,∆ -width(Q, π ′′ ) = PQ,∆ -width(Q, π ′ ) ≤ PQ,∆ -width(Q, π). Let us first show that reordering can decrease PQ,∆ -width(Q, π), improving the runtime of Theorem 4.3. The following example shows that this runtime gain is unbounded. ▶ Example 4.6. Consider Q⋆k with π = (x1 , . . . , xk , xk+1 ) and ∆ = {x1 → xk+1 }. We claim that PQ⋆k ,∆ -width(Q⋆k , π) ≥ k − 1. To see this, note first that the set function defined by h(S) := |S ∩ {v2 , . . . , vk }| is a polymatroid, respecting the FD, and guarded by Q⋆k . Moreover, we have that Bk+1 = {v1 , . . . , vk+1 }, and h(Bk+1 ) = k − 1. So, PQ⋆k ,∆ -width(Q⋆k , π) ≥ PQ⋆k ,∆ (Bk+1 ) ≥ k − 1. After reordering to π ′ = (x1 , xk+1 , x2 , . . . , xk ), we get that, other than

3

A very recent preprint [6] offers an improved version of PANDA with a tighter output bound. Using it would improve the polylog(|D|) factors in both the preprocessing and the access time to log(D).

F. Capelli, N. Carmeli, S. Mengel

11

B1 = {x1 }, all bags are of the form {xi , xk+1 }. Since Q⋆k contains the atoms Ri⋆ (xi , xk+1 ), any guarded polymatroid has h({xi , xk+1 }) ≤ 1, and it follows that PQ⋆k ,∆ -width(Q⋆k , π ′ ) ≤ 1. So, the preprocessing time from Theorem 4.3 decreases from roughly |D|k−1 to quasilinear due to ∆-reordering. Instead of proving Proposition 4.5 directly, we show a more abstract version that is also useful for Section 5. To this end, we define another property of set functions. Let Q(X) be a join query and ∆ a set of FDs. We call a set function f : 2X → R+ ∆-stable if for every FD Y → z in ∆ and every set Y ⊆ S ⊆ X, we have that f (S) = f (S ∪ {z}). Since PQ,∆ is ∆-stable, all properties that we show for general f -stable functions hold for PQ,∆ . ▶ Lemma 4.7. Let Q(X) be a join query and let ∆ be a set of FDs. Then, PQ,∆ is ∆-stable. We can show that, for a ∆-stable set function f , the f -width of a ∆-reordering is at most that of the original order. We get that two ∆-reorderings of the same order have the same f -width because they are ∆-reorderings of each other. ▶ Proposition 4.8. Let Q be a join query with FDs ∆ and a variable order π. Let π ′ and π ′′ be ∆-reorderings of π. If f : 2var(Q) → R+ is monotone and ∆-stable, then f -width(Q, π ′′ ) = f -width(Q, π ′ ) ≤ f -width(Q, π). Thus, the algorithm we propose in this section is obtained by taking a ∆-reordering and then applying Theorem 4.3. Given a join query Q, a set ∆ of FDs, and a ∆-reordering π ′ of ′ a desired variable order, the preprocessing obtained is O(|D|PQ,∆ -width(Q,π ) polylog(|D|)).

5

Lower Bounds Based on FD-Aware Incompatibility

In Section 3.2, we have seen that the extension approach cannot be used to show lower bounds for direct access when the FDs we consider are not unary. Thus, to show lower bounds in this setting, we have to develop new techniques. In this section, we do so by combining the decomposition approach used to show lower bounds for direct access without FDs [11] with the coloring approach used to show size lower bounds for CQs under FDs [19].

5.1

FD-Aware Incompatibility

We define a generalization of the incompatibility number [11] for queries with FDs. To this end, we use a generalization of the fractional edge cover number from [19], the color number. Given a join query Q, a k-coloring L : var(Q) → 2[k] with k ≥ 1 assigns a set of colors to S each query variable. Given a set of variables V , we set L(V ) = v∈V L(v), and we say that V contains a color c if c ∈ L(V ). Given a set of FDs, we say that a coloring L is valid if for every FD Y → z, we have that L(z) ⊆ L(Y ). ▶ Definition 5.1 (Color Number [19]). Given a self-join-free join query Q with a distinguished set of variables S and a set ∆ of FDs, the color number CQ,∆ (S) is the maximum over all valid colorings of Q of the number of colors appearing in S divided by the maximum number |L(S)| 4 of colors appearing in an atom. That is, CQ,∆ (S) := maxL maxR (X )∈atoms(Q) |L(Xi )| . i

4

i

The color number was originally defined for queries with self-joins [19]. We consider here a simplified definition without self-joins.

12

Lexicographic Direct Access with Functional Dependencies

We call the width measure CQ,∆ -width, as specified by Definition 4.1, the FD-aware incompatibility number. We remark that, in case there are no FDs, the FD-aware incompatibility number coincides with the incompatibility number from [11]: without FDs, the fractional edge cover number and the color number coincide [19, Section 3.1]. ▶ Example 5.2. Consider the query from Example 3.8 again. Its FD-aware incompatibility number is 2, given by B3 and the coloring with L(v1 ) = {1}, L(v2 ) = {2}, and L(v3 ) = L(v4 ) = L(v5 ) = ∅. Without the FD, the incompatibility number is 3, as can be seen by the coloring L′ (v1 ) = {1}, L′ (v2 ) = {2}, L′ (v3 ) = {3}, and L′ (v4 ) = L′ (v5 ) = ∅. However, given the FD v4 , v5 → v3 , L′ is not valid. ▶ Lemma 5.3. Let Q(X) be a self-join-free join query and ∆ a set of FDs. Then, the color number CQ,∆ is monotone and ∆-stable. As a direct consequence of Proposition 4.8 and Lemma 5.3, it is well-defined to refer to the FD-aware incompatibility number of a ∆-reordering. ▶ Proposition 5.4. Let Q be a self-join-free join query with FDs ∆ and a variable order π. Let π ′ and π ′′ be ∆-reorderings of π. Then, CQ,∆ -width(Q, π ′ ) = CQ,∆ -width(Q, π ′′ ).

5.2

Hardness Proof

We will show that the FD-aware incompatibility number of a ∆-reordering gives a lower bound for direct access. As in [11], we will use a reduction from star queries. The following lemma shows how to use the hardness of Q⋆ to deduce the hardness of any query that admits a coloring with certain properties. We say that a coloring is connected if, for every color, the set of variables assigned this color is connected. Given a coloring L and an ordering of variables π, we say that a variable v introduces a color c if v is the first variable in π such that c ∈ L(v). ▶ Lemma 5.5. Let Q be a self-join-free join query over a schema with FDs, π an ordering of its variables, 1 < ι ∈ R, and 2 ≤ k ∈ N, such that there is a valid connected (k + 1)-coloring of Q satisfying: The color k + 1 shares an atom with every other color. The maximum number of colors out of [k] that appear in an atom is kι . The variable that introduces the color k + 1 does not come before a variable that introduces another color. If there exists ε > 0 such that for all δ > 0 there is a direct access algorithm for Q and π with preprocessing time O(|D|ι−ε ) and access time O(|D|δ ), then there exists ε′ > 0 such that for all δ ′ > 0 there is a direct access algorithm for Q⋆k with respect to a bad ordering with ′ ′ preprocessing time O(|D⋆ |k−ε ) and access time O(|D⋆ |δ ). Proof sketch. The construction is similar to that used by Bringmann et al. [11, Lemma 17]; we repeat the ideas here for completeness. Let L : var(Q) → 2[k+1] be the said coloring of Q. Given a database D⋆ for Q⋆k , we construct a database D for Q. Given an atom R(v1 , . . . , vn ), let c1 , . . . , cℓ be those colors of [k] that appear in L(v1 ) ∪ . . . ∪ L(vn ). We note that ℓ ≤ kι . Compute the join of Rc1 (xc1 , xk+1 ), . . . , Rcℓ (xcℓ , xk+1 ). Every answer assignment h to this join defines a function fh from colors to the domain of D⋆ ; we extend this to a function fh+ from a set of colors by setting fh+ ({c1 , . . . , cm }) = (fh (c1 ), . . . , fh (cm )) assuming c1 < ... < cm , and fh+ (∅) = ⊥; and we add to RD the fact obtained by this function: R(fh+ (L(v1 )), . . . , fh+ (L(vn ))). We assume that the domain is sorted lexicographically. The

F. Capelli, N. Carmeli, S. Mengel

construction satisfies the FDs because the coloring is valid. It can be shown that the construction encodes the answers in Q⋆k (D⋆ ) in a bad lexicographic order, so direct access to Q(D) simulates direct access to Q⋆k (D⋆ ). ◀ It remains to find the coloring used by Lemma 5.5. ▶ Lemma 5.6. Let Q be a self-join-free join query over a schema with FDs ∆, and π an ordering of its variables. Let π ′ be a ∆-reordering of π. If CQ,∆ -width(Q, π ′ ) > 1, then there exists 2 ≤ k ∈ N such that there is a valid connected (k + 1)-coloring of Q satisfying: 1. The color k + 1 shares an atom with every other color. k 2. The maximum number of colors out of [k] that appear in an atom is CQ,∆ -width(Q,π ′) . 3. The variable that introduces the color k + 1 does not come before a variable that introduces another color. Proof sketch. One can show that there is a valid connected coloring L : var(Q) → 2[k] for some integer k such that |L(B)| = k for some bag B of the disruption-free decomposition and k CQ,∆ -width(Q, π ′ ) = maxR(X)∈atoms(Q) |L(X)| . Let vt be the last variable in π that introduces a color, and let this color w.l.o.g. be k. We define Bt and St as in the definition of a disruption-free decomposition: Bt is the bag obtained when treating vt (i.e., the bag in which vt is the last variable with respect to π), and St is the connected component of Q[vt , . . . , vn ] that contains vt . Add a fresh color k + 1 to all color sets L(v) with v ∈ St , and call the resulting coloring L′ . One can show that L′ has all claimed properties. ◀ We can now deduce the main result of this section. ▶ Theorem 5.7. Let Q be a self-join-free join query with FDs ∆ and π an ordering of its variables. Let π ′ be a ∆-reordering of π. If CQ,∆ -width(Q, π ′ ) > 1, then there is no ε > 0 such that for all δ > 0 there is a direct access algorithm for Q and π with preprocessing time ′ O(|D|CQ,∆ -width(Q,π )−ε ) and access time O(|D|δ ), assuming the Zero-Clique Conjecture. Proof. According to Observation 3.2, π and π ′ define the same problem, so we will work with π ′ , which is consistent with ∆. Lemma 5.6 identifies a coloring that, by Lemma 5.5, shows that the hardness of a star query implies the hardness of Q. The hardness of the star query is given by Theorem 2.1, assuming the Zero-Clique Conjecture. ◀ ▶ Example 5.8. Theorem 5.7 shows a quadratic lower bound for Example 3.8 since CQ,∆ -width(Q, π) = 2, as seen in Example 5.2. Note that, by Proposition 5.4, all ∆-reorderings yield the same bound in Theorem 5.7. Due to Proposition 4.5, the best algorithm we currently have is taking an (arbitrary) ∆reordering of π and applying Theorem 4.3. Comparing this algorithm with the lower bound of Theorem 5.7, we get an optimal algorithm (up to sub-polynomial factors) whenever CQ,∆ -width(Q, π ′ ) and PQ,∆ -width(Q, π ′ ) coincide. Let us discuss the connection between these two measures next. Of course, we cannot expect the lower bounds from Theorem 5.7 to be higher than the upper bounds in Theorem 4.3. Indeed, we can show the following: ▶ Proposition 5.9. For every self-join-free join query with FDs ∆ and every variable ordering π, we have CQ,∆ -width(Q, π) ≤ PQ,∆ -width(Q, π). Generally, CQ,∆ -width(Q, π) and PQ,∆ -width(Q, π) are not equal, and the gap between them can be arbitrarily big, as we see from the following result.

13

14

Lexicographic Direct Access with Functional Dependencies

▶ Proposition 5.10. For all k ∈ N, there is a join query Q, a variable order π, and a set of FDs ∆, such that PQ,∆ -width(Q, π ′ ) ≥ CQ,∆ -width(Q, π ′ ) + k for every ∆-reordering π ′ of π. Proof sketch. We start from a query Q′k in [19] that shows a separation between the color number and the exponent of the polymatroid bound for join queries, and we add a fresh variable and some atoms to force the variables into a common bag of the disruption-free decomposition. ◀

6

Linear Preprocessing Dichotomy

Having shown lower and upper bounds for direct access on join queries and general FDs, we now turn to showing a dichotomy for linear preprocessing time algorithms. A crucial part of such algorithms for query answering is often getting a decomposition of the query in which all materialized bags have linear size. Since the relations corresponding to the bags of the decomposition are essentially answers to the query at hand with additional projections, the main technical contribution of this section is proving a combinatorial property of CQs under FDs that have color number 1. From this property, we can then easily compute a linear-size superset of the query answers. This superset computation forms a decomposition of linear materialized bag size that is then used similarly to the proof of Theorem 4.3 to yield a linear preprocessing time direct access algorithm for all join queries under FDs and lexicographic orders for which such an algorithm exists, assuming the Zero-Clique Conjecture. We will now formulate and prove our linear-time dichotomy for lexicographic direct access with FDs. To this end, we need an additional definition. Let Q(X) be a CQ with a set of FDs ∆. A set of variables S is ∆-guarded if there is an atom Ri (Xi ) of Q such that Xi →∗ S. ▶ Theorem 6.1. Let Q be a self-join-free join query over a schema with FDs ∆ and π an ordering of its variables. Let H be the disruption-free decomposition of Q according to a ∆-reordering of π. There is a direct access algorithm for Q and π with preprocessing time O(|D|) and access time O(log |D|) if and only, for every bag in H, the bag variables are ∆-guarded in Q, assuming the Zero-Clique Conjecture. Let us remark that, as in Theorem 5.7, the choice of ∆-reordering does not matter in Theorem 6.1. This is due to Proposition 4.8 and its application for the different width measures. The upper bound of Theorem 6.1 follows from the following observation that ∆-guardedness yields a simple algorithm that slightly improves on PANDA for queries with ∆-guarded output variables with respect to the output size and computation time. ▶ Lemma 6.2. Let Q(X) be a CQ and ∆ a set of FDs. If X is ∆-guarded in Q, then there is an algorithm that, given a database D respecting ∆, computes a relation Rsup ⊇ Q(D) in linear time. Proof Sketch. Consider an atom R(Z) such that Z →∗ X. For every FD in ∆, build a lookup table that retrieves an assignment to the FD head given an assignment to the FD body. Extend R using these lookup tables to get a relation with variables Z ∪ X and then project to keep only X. ◀ The following lemma proves the combinatorial property needed for our dichotomy. ▶ Lemma 6.3. Let Q(X) be a CQ and ∆ a set of FDs. If CQ,∆ (X) = 1, then X is ∆-guarded in Q.

F. Capelli, N. Carmeli, S. Mengel

15

We remark that ∆-guardedness in fact characterizes the CQs and sets of FDs with linear output size, see Section E for details. Before proving Lemma 6.3, let us see how it combines with Lemma 6.2 to prove Theorem 6.1. Proof Sketch for Theorem 6.1. For the positive direction, follow the proof of Theorem 4.3 on a ∆-reordering, but replace the application of PANDA with Lemma 6.2. For the negative direction, let π ′ be a ∆-reordering of π and consider the corresponding disruption-free decomposition H. According to Lemma 6.3, if some bag Bi of H is not ∆-guarded, then CQ,∆ (Bi ) > 1 and thus CQ,∆ -width(Q, π ′ ) > 1. According to Theorem 5.7 with ε = CQ,∆ -width(Q, π ′ ) − 1, there exists δ > 0 such that there is no direct access algorithm for Q and π with preprocessing time O (|D|) and access time O(|D|δ ), assuming the Zero-Clique Conjecture. ◀ To complete the proof of Theorem 6.1, it remains to show Lemma 6.3. We need some more definitions. We call a set of variables S compatible with an FD Y → z if z ∈ / S or S ∩ Y ̸= ∅. In other words, if S contains the head of the FD, it has to contain at least one variable of the body. We say that S is compatible with a set of FDs ∆ if it is compatible with every FD of ∆. Our proof is based on a linear programming characterization of the color number. ▶ Lemma 6.4. Let Q(X) be a CQ and ∆ a set of FDs. The optimal value of the following linear program on variables σRi (Xi ) is CQ,∆ (X). X minimize σRi (Xi ) Ri (Xi )∈Q

X

subject to

σRi (Xi ) ≥ 1

∀S ⊆ V compatible with ∆ with S ∩ X ̸= ∅

Ri (Xi )∈Q:S∩Xi ̸=∅

σRi (Xi ) ≥ 0

∀Ri (Xi ) ∈ Q

Proof sketch. We start from a linear programming characterization of the color number by Gottlob et al. [19], take its dual, and then perform simplification steps, deleting unnecessary constraints. ◀ We can now prove Lemma 6.3. Proof of Lemma 6.3. We want to prove that there is an atom R(Z) of Q such that Z →∗ X. Denote by PC (Q, ∆) the linear program defined in Lemma 6.4, and denote by cS its constraint for the set S ⊆ V . Since the color number is 1, the optimal value of PC (Q, ∆) is 1. We first claim that there exists an atom R(Z) of Q such that σR(Z) appears in every constraint cS of PC (Q, ∆). Indeed, consider an optimal solution (σ ∗ ) of PC (Q, ∆) and a constraint cS of the program. We have that: X X ∗ ∗ 1= σR ≥ σR ≥1 (X ) i i i (Xi ) Ri (Xi )∈Q

Ri (Xi )∈Q:S∩Xi ̸=∅

where the first equality is since the optimal value of the program is 1, and the last inequality is due to the constraint cS . Thus, the two sums equal 1. For every atom Ri (Xi ) of Q such ∗ ∗ that σR > 0, we have that σR must appear in cS , because otherwise the sum above i (Xi ) i (Xi ) ∗ would be smaller than 1. Hence any arbitrary atom R(Z) such that σR(Z) > 0 has the desired property. We now proceed to prove that Z →∗ X. Denote by Z ∗ the set of variables y of Q such that Z →∗ y and assume toward a contradiction that there exists x ∈ X such that x ∈ / Z ∗. We will construct a set S ∗ ⊆ V such that:

16

Lexicographic Direct Access with Functional Dependencies

cS ∗ is a constraint of PC (Q, ∆), that is, S ∗ is compatible with ∆ and S ∗ ∩ X ̸= ∅, Z ∩ S ∗ = ∅. To do so, we construct a sequence S 0 ⊊ · · · ⊊ S r for some r ∈ [n] such that S 0 = {x} and Z ∗ ∩ S i = ∅ for every i ≤ r. We start with S 0 = {x} which has the desired property since x ∈ / Z ∗ . Now, given S i , we explain how to construct S i+1 : if there is an FD Y → z in ∆ such that z ∈ S i and Y ∩ S i = ∅, then we pick z ′ ∈ Y \ Z ∗ and define S i+1 = S i ∪ {z ′ }. Observe that z ′ always exists. Indeed, if Y ⊆ Z ∗ , then we would have z ∈ Z ∗ , which does not hold because z ∈ S i and we ensure by induction that S i ∩ Z ∗ = ∅. If no such FD exists, we stop and set S ∗ = S i . Observe that this process must stop at some point since |S i | is an increasing sequence bounded by |V |. Since we do not insert to S ∗ elements of Z ∗ , this construction ensures that S ∗ ∩ Z ∗ = ∅. Now we claim that the set S ∗ is compatible with ∆. Indeed, let Y → z be an FD of ∆. If z ∈ / S ∗ , then S ∗ is compatible with the FD by definition. If z ∈ S ∗ , then we must have S∗ ∩ Y = ̸ ∅ by construction of S ∗ , and so S ∗ is compatible with the FD. Overall, S ∗ is compatible with ∆, and X ∩ S ∗ ̸= ∅ since x ∈ S ∗ . The linear program PC (Q, ∆) contains the constraint cS ∗ , but since Z ∩ S ∗ = ∅, σR(Z) does not appear in cS ∗ , which contradicts the established property of R(Z). Hence, we have that x ∈ Z ∗ for every x ∈ X, and so Z →∗ X. ◀

7

Connection between the approaches

In this section, we compare the extension-based approach from Section 3 with that based on disruption-free decompositions from Section 4. We have already seen in Example 4.2 that the approach from Section 4 is sometimes more efficient than the other. We show that it is always at least as good as that from Section 3, and that in the case of unary FDs, the two approaches yield the same complexity. For the rest of this section, consider a self-join-free join query Q, a set of FDs ∆, and an ordering π of the variables of Q that is consistent with respect to ∆. Deonte by Q+ be the extension of Q, and remark that π + = π since it is consistent. Recall that ρ∗Q+ -width(Q+ , π) is the incompatibility number of Q+ and π, and it determines the runtime exponent for the approach from Section 3 as given in Corollary 3.5. The polymatroid-based measure PQ,∆ -width(Q, π) determines the runtime exponent for the approach from Section 4 as given in Theorem 4.3. This section compares these two measures. In this section, we use the following notation. We denote π = (v1 , . . . , vn ). We let bi denote the bag created by vi in the disruption-free decomposition of Q, and let Bi be the bag created by vi in that of the extension Q+ . Given a set S of variables, we define the set S + as the fixpoint of the following extension step, starting with S + := S: if there is an FD Y → z such that Y ⊆ S and z ∈ / S + , then add z to S + . Clearly, the choice of the order in which we handle the FDs and add variables in the construction of S + does not change the end result, so S + is well-defined.

7.1

Superiority of the polymatroid-based approach

The following proposition shows that the approach from Section 4 is always at least as good as the extension-based approach.

F. Capelli, N. Carmeli, S. Mengel

17

▶ Proposition 7.1. Let Q be a self-join-free join query, ∆ a set of FDs, and π a consistent ordering with respect to ∆. Moreover, let Q+ be the extension of Q. Then, PQ,∆ -width(Q, π) ≤ ρ∗Q+ -width(Q+ , π). Remember that in Example 3.8 and Example 4.2, we have seen that the two width measures PQ,∆ -width(Q, π) and ρ∗Q+ -width(Q+ , π) differ in some cases, so the inequality of Proposition 7.1 can in general be strict. We will show Proposition 7.1 in two steps. We start with the following. ▶ Lemma 7.2. Let Q, Q+ , ∆, and π be as in Proposition 7.1. Then, we have that PQ,∆ -width(Q, π) ≤ PQ+ ,∅ -width(Q+ , π). Proof. We show that PQ,∆ (bi ) ≤ PQ+ ,∅ (Bi ). By definition, we have that PQ,∆ (bi ) is the solution of maximize h(bi ) subject to h(Xi ) ≤ 1 h({z} | Y ) ≤ 0

for every atom Ri (Xi ) of Q for every FD Y → z of ∆

h is a polymatroid. Let h∗ be the polymatroid that maximizes the value h(bi ) in this system. As defined at the beginning of this section, given a set V of variables, we denote by V + the set obtained by extending V according to ∆. Then we have, due to the constraints for the FD, that h∗ (V + ) ≤ h∗ (V ) and thus, for every atom Ri (Xi ), we have h∗ (Xi+ ) ≤ h∗ (Xi ). It follows that h∗ is a feasible solution for maximize h(Bi ) subject to h(Xi+ ) ≤ 1

for every atom Ri (Xi+ ) of Q+

h is a polymatroid. The optimal solution of this linear program is PQ+ ,∅ (Bi ) by definition. Due to the monotonicity of the polymatroid h∗ an since bi ⊆ Bi , we have that h∗ (bi ) ≤ h∗ (Bi ). Overall, we get that PQ,∆ (bi ) = h∗ (bi ) ≤ h∗ (Bi ) ≤ PQ+ ,∅ (Bi ). The claim follows since PQ,∆ -width(Q, π) = maxi∈n PQ,∆ (bi ) ≤ maxi∈n PQ+ ,∅ (Bi ) = PQ+ ,∅ -width(Q+ , π). ◀ It remains to show the following. ▶ Lemma 7.3. Let Q+ be a self-join-free join query and let π be a variable order of Q+ . Then, PQ+ ,∅ -width(Q, π) = ρ∗Q+ -width(Q+ , π). Proof. It suffices to show that, for every variable set of the disruption-free decomposition of Q+ and π, we have PQ+ ,∅ (B) = ρ∗Q+ (B). However, this is exactly the so-called Modularization Lemma, Lemma 3.1 in [4]. ◀ Combining Lemma 7.2 and Lemma 7.3 directly yields Proposition 7.1.

18

Lexicographic Direct Access with Functional Dependencies

7.2

Equivalence in case of unary FDs

We show next that, for unary FDs, the two approaches give the same width values and thus the same runtimes. We remark that this can be concluded immediately, conditioned on the Zero-Clique Conjecture, from Proposition 7.1 and Corollary 3.7 since the extension approach is optimal in the unary case and the polymatroid bound approach is at least as good. In this section, we show that this also holds unconditionally. ▶ Proposition 7.4. Let Q be a self-join-free join query, ∆ a set of FDs, and π a consistent ordering π with respect to ∆. Let moreover Q+ be the extension of Q. Then, CQ,∆ -width(Q, π) = PQ,∆ -width(Q, π) = ρ∗Q+ -width(Q+ , π).

8

Conclusion

In this paper, we proved upper and lower bounds for lexicographic direct access for self-joinfree join queries that take FDs into account. Unfortunately, these bounds are not tight in general, which is likely related to the fact that there is no known worst-case optimal algorithm for join queries with functional dependencies. While the PANDA algorithm reaches the polymatroid bound, this bound is in general bigger than the so-called entropic bound which determines the size of query results asymptotically [4], and thus PANDA is not worst-case optimal when taking FDs into consideration. Since we use a join algorithm as a black-box, improving upon PANDA, if this is even possible, might be necessary to get tight bounds in our setting. That said, even now our results allow us to characterize the combinations of a query, a variable order, and a set of FDs that admit logarithmic access time after linear preprocessing. We also proved a tight characterization of the preprocessing time required for logarithmic access time in case all FDs are unary. We studied two approaches in this paper, and saw using our running example (Example 3.8) that the approach of taking the FDs into account while inspecting the bags of a disruption-free decomposition (Theorem 4.3 applied to a ∆-reordering) sometimes yields better complexity than the simple approach of using a reordered extension (Corollary 3.5). We also saw that, in terms of complexity, this approach is never worse, so we can always use the approach from Section 4.2. However, if all FDs are unary, the two approaches yield the same complexity, so it could make sense to use the simpler approach from Section 3. A natural next step is to try and generalize our results. On the query side, one could check whether the direct-access lower-bound techniques for queries with self-joins [11] can be combined with the generalization of the color number to such queries [19]. On the constraints side, as PANDA also supports degree constraints [4], our algorithmic approach can remain the same to support such constraints, and it would be interesting to try and prove a matching lower bound. Finally, we would like to see whether the techniques from this paper can be used for other query answering tasks, such as enumeration, counting, or more general aggregation. References 1

Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.

2

Mahmoud Abo Khamis, Xiao Hu, and Dan Suciu. Fast matrix multiplication meets the submodular width. Proc. ACM Manag. Data, 3(2):98:1–98:26, 2025. doi:10.1145/3725235.

F. Capelli, N. Carmeli, S. Mengel

3

4

5

6

7

8

9

10 11 12

13 14

15

16

17

18

Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. Computing join queries with functional dependencies. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 327–342, 2016. Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? CoRR, abs/1612.02503, 2016. URL: http://arxiv.org/abs/1612.02503, arXiv:1612.02503. Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. PANDA: query evaluation in submodular width. TheoretiCS, 4, 2025. URL: https://doi.org/10.46298/theoretics.25.12, doi: 10.46298/THEORETICS.25.12. Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. Pandaexpress: a simpler and faster PANDA algorithm. CoRR, abs/2512.10217, 2025. URL: https://doi.org/10.48550/arXiv. 2512.10217, arXiv:2512.10217, doi:10.48550/ARXIV.2512.10217. Isolde Adler. Width functions for hypertree decompositions (Weitefunktionen für Hyperbaumzerlegungen). PhD thesis, University of Freiburg, Germany, 2006. URL: https: //freidok.uni-freiburg.de/data/2468. Guillaume Bagan, Arnaud Durand, Etienne Grandjean, and Frédéric Olive. Computing the jth solution of a first-order query. RAIRO Theor. Informatics Appl., 42(1):147–164, 2008. doi:10.1051/ita:2007046. Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News, 7(1):4–33, 2020. doi:10.1145/ 3385634.3385636. Johann Brault-Baron. De la pertinence de l’énumération: complexité en logiques propositionnelle et du premier ordre. PhD thesis, Université de Caen, 2013. Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries. ACM Trans. Database Syst., 50(1):1:1–1:44, 2025. doi:10.1145/3707448. Florent Capelli, Oliver Irwin, and Sylvain Salvati. A simple algorithm for worst case optimal join and sampling. In Sudeepa Roy and Ahmet Kara, editors, 28th International Conference on Database Theory, ICDT 2025, Barcelona, Spain, March 25-28, 2025, volume 328 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. URL: https://doi.org/10.4230/LIPIcs.ICDT.2025.23, doi:10.4230/LIPICS.ICDT.2025.23. Nofar Carmeli and Markus Kröll. Enumeration complexity of conjunctive queries with functional dependencies. Theory of Computing Systems, 64(5):828–860, 2020. Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. Tractable orders for direct access to ranked answers of conjunctive queries. ACM Transactions on Database Systems, 48(1):1–45, 2023. Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, and Nicole Schweikardt. Answering (unions of) conjunctive queries using random access and random-order enumeration. ACM Transactions on Database Systems (TODS), 47(3):1–49, 2022. Kyle Deeds and Timo Camillo Merkl. Partition constraints for conjunctive queries: Bounds and worst-case optimal joins. In Sudeepa Roy and Ahmet Kara, editors, 28th International Conference on Database Theory, ICDT 2025, Barcelona, Spain, March 25-28, 2025, volume 328 of LIPIcs, pages 17:1–17:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. URL: https://doi.org/10.4230/LIPIcs.ICDT.2025.17, doi:10.4230/LIPICS.ICDT.2025.17. Shaleen Deep, Xiao Hu, and Paraschos Koutris. Fast join project query evaluation using matrix multiplication. In David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 1213–1223. ACM, 2020. doi:10.1145/3318464.3380607. Tomasz Gogacz and Szymon Torunczyk. Entropy bounds for conjunctive queries with functional dependencies. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, Venice, Italy, March 21-24, 2017, volume 68 of LIPIcs,

19

20

Lexicographic Direct Access with Functional Dependencies

19

20 21 22

23

24

25 26

pages 15:1–15:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https: //doi.org/10.4230/LIPIcs.ICDT.2017.15, doi:10.4230/LIPICS.ICDT.2017.15. Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. Size and treewidth bounds for conjunctive queries. J. ACM, 59(3):16:1–16:35, 2012. doi:10.1145/2220357. 2220363. Xiao Hu. Output-optimal algorithms for join-aggregate queries. Proc. ACM Manag. Data, 3(2):104:1–104:27, 2025. doi:10.1145/3725241. William Kent. A simple guide to five normal forms in relational database theory. Communications of the ACM, 26(2):120–125, 1983. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bull. EATCS, 105:41–72, 2011. URL: http://eatcs.org/beatcs/index. php/beatcs/article/view/92. Stefan Mengel. Lower bounds for conjunctive query evaluation. In Floris Geerts and Benny Kimelfeld, editors, Companion of the 44th Symposium on Principles of Database Systems, PODS 2025, Berlin, Germany, June 22-27, 2025, page 5. ACM, 2025. doi:10.1145/3722234. 3725824. Hung Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 111–124. ACM, 2018. doi:10.1145/3196959.3196990. Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms. J. ACM, 65(3):16:1–16:40, 2018. doi:10.1145/3180143. Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96– 106. OpenProceedings.org, 2014. URL: https://doi.org/10.5441/002/icdt.2014.13, doi: 10.5441/002/ICDT.2014.13.

F. Capelli, N. Carmeli, S. Mengel

A

Proofs for Section 3 (Reordered Extensions)

▶ Observation 3.2. Given a CQ Q, a set of FDs ∆, a variable order π, and a ∆-reordering π ′ of π, then the triples (Q, π ′ , ∆) and (Q, π, ∆) induce the same output in the same order. Proof. Given an FD Y → z, once the assignment for Y is set, z can have at most one possible assignment, so as long as z comes after all variables of Y in the order, its exact position or whether it is considered as part of the order does not influence the answer ordering. This observation was already stated for unary FDs [14, Lemma 8.16]. ◀ As any database that satisfies a set of FDs ∆ also satisfies ∅, using the identity for the construction and bijection yields a trivial exact reduction from a problem with FDs to the same problem without FDs. ▶ Observation A.1. Given a self-join-free CQ Q, a variable order π, and a set of FDs ∆, there is an exact reduction from (Q, π, ∆) to (Q, π, ∅). Carmeli and Kröll [13, Theorem 2] show exact reductions in both directions between a query and its reordered extension. Inspecting their proofs, we notice that they preserve the answer order. ▶ Lemma A.2. Given a self-join-free CQ Q, a variable order π, and a set of FDs ∆, there are exact reductions in both directions between (Q, π, ∆) and (Q+ , π, ∆+ ). Proof. We first show an exact reduction from (Q, π, ∆) to (Q+ , π, ∆+ ). Carmeli and Kröll [13, Claim 1 of Theorem 2] show an exact reduction from (Q(X), ∆) to (Q+ (X + ), ∆+ ) without discussing the answer order. In this reduction, the bijection τ keeps the assignments to the free variables of Q as is and projects away the assignments for the variables X + \ X. Since π only depends on X, the answer order is maintained. We next show an exact reduction from (Q+ , π, ∆+ ) to (Q, π, ∆). Carmeli and Kröll [13, Claim 2 of Theorem 2] show an exact reduction from (Q+ , ∆+ ) to (Q, ∆) without discussing the answer order. In this reduction, the bijection τ keeps the assignments to the free variables of Q as is and only extends the mappings with assignments for the variables X + \ X. Since π only involves variables of X, the answer order is maintained. ◀ ▶ Theorem 3.4. Given a self-join-free CQ Q, a variable order π, and a set of FDs ∆, there is an exact reduction from (Q, π, ∆) to (Q+ , π + , ∅). Proof. We reduce (Q, π, ∆) to (Q+ , π, ∆+ ) using Lemma A.2. The latter represents the same problem as (Q+ , π + , ∆+ ) by Observation 3.2. Finally, we apply Observation A.1 for a reduction from (Q+ , π + , ∆+ ) to (Q+ , π + , ∅). ◀ ▶ Lemma A.3. Given a self-join-free CQ Q, a variable order π, and a set of unary FDs ∆, there is an exact reduction from (Q+ , π + , ∅) to (Q+ , π + , ∆+ ). Proof. We follow a similar construction to that of [14, Lemma 8.6] and show that it preserves the lexicographic order π + . Given a database D that is not required to conform to any FDs, we construct a database D+ conforming to ∆+ as follows. ⃗ v the sequence of all variables that are transitively Given a variable v, denote by imp implied by v in the order in which they appear in π + (if v does not appear in π, take an arbitrary order). By the definition of the extension, for every variable v, every atom of ⃗ v variables. For every fact in the relation that Q+ that contains v also contains all imp ⃗ v -values. corresponds to such an atom, we replace the v-value with the concatenation of imp

21

22

Lexicographic Direct Access with Functional Dependencies

These concatenated domain values are assumed to be sorted lexicographically according to ⃗ v . This construction can be done in linear time, and the resulting database satisfies the imp FDs. We now claim that this construction preserves the answers through a bijection. Note that ⃗ v are all free. for every free variable v, by the definition of the extension, the variables in imp Every answer to the original problem gives an answer over our construction by assigning ⃗ v . Every answer over every free variable v with the concatenation of the assignments of imp our construction gives an answer to the original problem by keeping only the value that corresponds to the original variable for every free variable. ⃗ v that do not appear before v, the Since π + contains right after v all variables of imp answer order is preserved. ◀ ▶ Theorem 3.6. Given a self-join-free CQ Q, a variable order π, and a set of unary FDs ∆, there are exact reductions in both directions between (Q, π, ∆) and (Q+ , π + , ∅). Proof. The reduction from (Q, π, ∆) to (Q+ , π + , ∅) is given by Theorem 3.4. For the other direction, Lemma A.3 reduces (Q+ , π + , ∅) to (Q+ , π + , ∆+ ), Observation 3.2 shows that (Q+ , π + , ∆+ ) and (Q+ , π, ∆+ ) represent the same problem, and Lemma A.2 reduces (Q+ , π, ∆+ ) to (Q, π, ∆). ◀

B

Proofs for Section 4 (An Algorithm Based on the Polymatroid Bound)

▶ Lemma 4.7. Let Q(X) be a join query and let ∆ be a set of FDs. Then, PQ,∆ is ∆-stable. Proof. Consider an FD Y → z in ∆ and a set Y ⊆ S ⊆ X. It is known that for any polymatroid h : 2V → R+ , all sets A ⊆ B ⊆ V and v ∈ V , we have h(A ∪ {v}) − h(A) ≥ h(B ∪ {v}) − h(B) [?, Chapter 44]. Setting A = Y, B = S and v = z, it follows that h(Y ∪ {z}) − h(Y ) ≥ h(S ∪ {z}) − h(S). By monotonicity, h(S ∪ {z}) − h(S) ≥ 0. If h also respects the FD Y → z, we have that h(Y ∪ {z}) − h(Y ) = 0, and thus h(S ∪ {z}) = h(S). It follows that PQ,∆ (S ∪ {z}) = PQ,∆ (S). ◀

B.1

Proof of Proposition 4.8

We first show that for monotone and ∆-stable functions f , reordering can only decrease the disruption-free f -width. We start by proving a special case. ▶ Lemma B.1. Let Q be a join query, ∆ a set of FDs, and π = (v1 . . . vn ) a variable order. Let π ′ = (v1 . . . vi−1 vi+1 vi vi+2 . . . vn ) such that there is Y ⊆ {v1 . . . vi−1 } where Y → vi+1 is an FD in ∆. If f : 2var(Q) → R+ is monotone and ∆-stable, then f -width(Q, π ′ ) ≤ f -width(Q, π). Proof. For every j, let Bj and Bj′ the bags as in definition of the disruption-free decompositions for π and π ′ , respectively. Moreover, let Sj and Sj′ be defined as the sets Sj for π and π ′ . We first observe that for j ∈ / {i, i + 1}, we have Sj = Sj′ and thus Bj = Bj′ . So, the only bags that could lead to a difference between the disruption-free f -widths are those created by vi and vi+1 . Consider first the case that vi and vi+1 are not connected by a path in Q[vi , vi+1 , . . . , vn ]. ′ ′ Then, Si = Si′ and Si+1 = Si+1 , and thus Bi = Bi′ and Bi+1 = Bi+1 . It follows directly that the disruption-free f -width of Q and π is the same as that of Q and π ′ . If vi and vi+1 are connected by a path in Q[vi , vi+1 , . . . , vn ], then vi and vi+1 appear in the same connected component of Q[vi , vi+1 , . . . , vn ], and this connected component is

F. Capelli, N. Carmeli, S. Mengel

′ ′ Si = Si+1 . We claim that both f (Bi′ ) and f (Bi+1 ) are at most f (Bi ), from which the lemma follows directly. ′ ′ We first show that f (Bi+1 ) ≤ f (Bi ). To this end, observe that, due to Si = Si+1 , we have ′ Bi \ {vi } = Bi+1 \ {vi+1 }. Moreover, since the FD Y → vi+1 is covered by a relation, we ′ have that all variables in Y are neighbors of vi+1 in Q, so Y ⊆ Bi+1 and thus by ∆-stability, ′ ′ we have f (Bi+1 ) = f (Bi+1 \ {vi + 1}) = f (Bi \ {vi }) ≤ f (Bi ), where the inequality follows from monotonicity of f . We next show that f (Bi′ ) ≤ f (Bi ). First note that vi+1 ∈ Si since there is a path from vi to vi+1 in Q[vi , vi+1 , . . . , vn ]. Since all variables in Y are neighbors of vi+1 , we have Y ⊆ Bi . It follows that f (Bi ) = f (Bi ∪ {vi+1 }) since f is ∆-stable. We have Si′ ⊆ Si , so Bi′ ⊆ Bi ∪ {vi+1 }, and thus f (Bi′ ) ≤ f (Bi ∪ {vi+1 }) = f (Bi ). ◀

We can now prove the general case using Lemma B.1. ▶ Lemma B.2. Let Q be a join query, π a variable order, and ∆ a set of FDs. Let π ′ be a ∆-reordering of π. If f : 2var(Q) → R+ is monotone and ∆-stable, then f -width(Q, π ′ ) ≤ f -width(Q, π) Proof. The idea is that we can simulate the construction of any ∆-reordering by iteratively bubbling variables to the front, increasing the disruption-free f -width in none of the steps due to Lemma B.1. More precisely, we claim that there exists a sequence π = π1 . . . , πℓ = π ′ of variable orders such that πj and πj+1 satisfy the conditions of Lemma B.1 for all j. We conclude that f -width(Q, πj+1 ) ≤ f -width(Q, πj ), and overall f -width(Q, π ′ ) ≤ f -width(Q, π). Consider a variable order πj ̸= π ′ , let t be the first position in which they differ, and let z be the variable in position t in π ′ . By the definition of the reordering, there is an FD Y → z with Y appearing in the first t − 1 positions of πj . Define πj+1 to be similar to πj but with the variable z advanced by one position. Clearly, the conditions of Lemma B.1 apply for πj and πj+1 . Compared to πj , πj+1 either has a later first different position with respect to π ′ , or the same first different position t and the variable in position t in π ′ is closer to t in πj+1 than in πj . Thus, this sequence will eventually produce π ′ . ◀ We get that different reorderings have the same disruption-free f -width. ▶ Lemma B.3. Let Q be a join query, π a variable order, and ∆ a set of FDs. Let π ′ and π ′′ be ∆-reorderings of π. If f : 2var(Q) → R+ is monotone and ∆-stable, then f -width(Q, π ′ ) = f -width(Q, π ′′ ). Proof. We notice that π ′ is a ∆-reordering of π ′′ and vice-versa. Indeed, in the construction of ∆-reorderings in Definition 3.1, there are two reasons to add a variable z at a specific position to a reordering π ′ : either there is a set Y already added to π ′ such that Y → z or there is no such FD but z is the next variable in π that has not already been added to π ′ . We call the former type of variables dependent and the latter type independent. For every independent variable vj , let us define the set dep(vj ) to contain all dependent variables that we have to add until we add the next independent variable. Clearly, dep(vj ) does not depend on the choices in the construction and is thus well-defined. Also, the orders π ′ and π ′′ can only differ in the order inside the sets dep(yj ) while the positions of the independent variables are fixed, and any order inside the sets dep(yj ) is allowed in a reordering. Thus, π ′ is a ∆-reordering of π ′′ and vice-versa. By applying Lemma B.2 twice, we get that f -width(Q, π ′ ) ≤ f -width(Q, π ′′ ) ≤ f -width(Q, π ′ ), so overall f -width(Q, π ′ ) = f -width(Q, π ′′ ). ◀

23

24

Lexicographic Direct Access with Functional Dependencies

Proposition 4.8 is obtained by combining Lemma B.3 and Lemma B.2.

C

Proofs for Section 5 (Lower Bounds Based on FD-Aware Incompatibility)

▶ Lemma 5.3. Let Q(X) be a self-join-free join query and ∆ a set of FDs. Then, the color number CQ,∆ is monotone and ∆-stable. Proof. First, notice that the color number is monotone. Consider the sets S1 ⊆ S2 ⊆ X, and let L′ be an optimal coloring for Q, S1 , and ∆. Then, C(Q, S1 , ∆) =

|L′ (S1 )| maxRi (Xi )∈atoms(Q) |L′ (Xi )|

≤

|L′ (S2 )| maxRi (Xi )∈atoms(Q) |L′ (Xi )|

≤ C(Q, S2 , ∆).

Next, we show ∆-stability. Consider an FD Y → z of ∆ and a set Y ⊆ S ⊆ X. Let L be an optimal coloring for Q, S ∪ {z}, and ∆. Since L is valid, we have that L(z) ⊆ L(Y ). Thus, |L(S ∪ {z})| = |L(S)|, and C(Q, S∪{z}, ∆) =

|L(S ∪ {z})| |L(S)| = ≤ C(Q, S, ∆). maxRi (Xi )∈atoms(Q) |L(Xi )| maxRi (Xi )∈atoms(Q) |L(Xi )|

The inequality in the other direction holds because the color number is monotone, so, overall, we get that C(Q, S, ∆) = C(Q, S ∪ {z}, ∆). ◀ ▶ Lemma C.1. Let Q be a CQ, S a subset of its variables, and ∆ a set of FDs. There is a valid connected coloring witnessing its color number CQ,∆ (S) such that S contains all colors. Proof. Consider a valid coloring witnessing the color number. First, remove colors that do not appear in S. Then, if there are several connected components of variables containing a color, remove this color from all but one component that includes a variable in S. Since every FD is contained in an atom, removing entire connected components does not affect the validity of the coloring. These two steps do not change the number of colors that appear in S, and they do not increase the number of colors assigned to an atom. Thus, they do not decrease the color number. Since we started with a coloring witnessing the maximum possible color number, we conclude that the color number of the modified coloring is equal to that of the original coloring. ◀ ▶ Lemma 5.5. Let Q be a self-join-free join query over a schema with FDs, π an ordering of its variables, 1 < ι ∈ R, and 2 ≤ k ∈ N, such that there is a valid connected (k + 1)-coloring of Q satisfying: The color k + 1 shares an atom with every other color. The maximum number of colors out of [k] that appear in an atom is kι . The variable that introduces the color k + 1 does not come before a variable that introduces another color. If there exists ε > 0 such that for all δ > 0 there is a direct access algorithm for Q and π with preprocessing time O(|D|ι−ε ) and access time O(|D|δ ), then there exists ε′ > 0 such that for all δ ′ > 0 there is a direct access algorithm for Q⋆k with respect to a bad ordering with ′ ′ preprocessing time O(|D⋆ |k−ε ) and access time O(|D⋆ |δ ). Proof. The construction is similar to that used by Bringmann et al. [11, Lemma 17]; we repeat the ideas here for completeness. Let L : var(Q) → 2[k+1] be the said coloring of Q.

F. Capelli, N. Carmeli, S. Mengel

25

Construction. Given a database D⋆ for Q⋆ , we construct a database D for Q. Given an atom R(v1 , . . . , vn ), let c1 , . . . , cℓ be those colors of [k] that appear in L(v1 ) ∪ . . . ∪ L(vn ). We note that ℓ ≤ kι . Compute the join of Rc1 (xc1 , xk+1 ), . . . , Rcℓ (xcℓ , xk+1 ). Every answer assignment h to this join defines a function fh from colors to the domain of D⋆ ; we extend this to a function fh+ from a set of colors by setting fh+ ({c1 , . . . , cm }) = (fh (c1 ), . . . , fh (cm )) assuming c1 < ... < cm , and fh+ (∅) = ⊥; and we add to RD the fact obtained by this function: R(fh+ (L(v1 )), . . . , fh+ (L(vn ))). We assume that the domain is sorted lexicographically. The construction satisfies the FDs because the coloring is valid. Correctness. We claim that we get a bijection τ from Q(D) to Q⋆ (D⋆ ): if a coordinate corresponding to a color c is assigned a value d in an answer a to Q(D), then τ (a) assigns d to xc . First, since the coloring is connected, all occurrences of the same color get assigned the same value, and so τ is well-defined. Given an answer to Q⋆ (D⋆ ), it is clear that it is obtained by our construction because the construction combines subjoins of Q⋆ . Given an answer to Q(D), we argue that it yields an answer to Q⋆ . Indeed, given any atom Ri (xi , xk+1 ) of Q⋆ , the color i shares an atom with the color k + 1 by the conditions of this lemma, and hence there exists a relation in Q that uses the atom Ri (xi , xk+1 ) in the subjoin defining it. It is left to notice that the construction produces the results in a bad ordering because the variable that introduces k + 1 does not come before variables that introduce other colors. If the same variable introduces both k + 1 and another color c, our construction ensures that the values are sorted first by the assignment to xc and then by the assignment to xk+1 . Time complexity. Since every atom contains at most kι colors out of [k], every relation k of D is obtained by the join of at most kι relations of D⋆ . Thus, |D| = O(|D⋆ | ι ). Given an algorithm for Q with preprocessing time O(|D|ι−ε ), we set ε′ = min(k − kι , kε ι ). With this ′ ⋆ kι choice, we get that the construction time for the database D is O(|D | ) ≤ O(|D⋆ |k−ε ), and k the preprocessing time of this algorithm over our construction is O(|D|ι−ε ) ≤ O(|D⋆ | ι (ι−ε) ) ≤ ′ ′ O(|D⋆ |k−ε ). Then, given δ ′ > 0, we set δ = δkι and get that the access time is O(|D|δ ) ≤ k δ′ ι

′

O(|D⋆ | ι k ) ≤ O(|D⋆ |δ ).

◀

▶ Lemma 5.6. Let Q be a self-join-free join query over a schema with FDs ∆, and π an ordering of its variables. Let π ′ be a ∆-reordering of π. If CQ,∆ -width(Q, π ′ ) > 1, then there exists 2 ≤ k ∈ N such that there is a valid connected (k + 1)-coloring of Q satisfying: 1. The color k + 1 shares an atom with every other color. k 2. The maximum number of colors out of [k] that appear in an atom is CQ,∆ -width(Q,π ′) . 3. The variable that introduces the color k + 1 does not come before a variable that introduces another color. Proof. Use Lemma C.1 to get a valid connected coloring L : var(Q) → 2[k] for some integer k such that |L(B)| = k for some bag B of the disruption-free decomposition and k CQ,∆ -width(Q, π ′ ) = maxR(X)∈atoms(Q) |L(X)| . Let vt be the last variable in π that introduces a color, and let this color w.l.o.g. be k. We define Bt and St as in the definition of a disruption-free decomposition: Bt is the bag obtained when treating vt (i.e., the bag in which vt is the last variable with respect to π), and St is the connected component of Q[vt , . . . , vn ] that contains vt . Add a fresh color k + 1 to all color sets L(v) with v ∈ St , and call the resulting coloring L′ . ▷ Claim C.2. L′ is a valid coloring. Proof. Since L′ is constructed from the valid coloring L by adding the fresh color k + 1 to every variable in St , we only need to show that for every FD X → y such that y ∈ St , there is a variable x ∈ X in St .

26

Lexicographic Direct Access with Functional Dependencies

Denote by x the last variable of X in π. Let ux be the last variable in π implied by the variables in the prefix of π ending with x. In particular, x ≤π ux . Due to the FD, we have that y ≤π ux . Since y ∈ St , we have that y ≥π vt . So overall, vt ≤π ux . Since vt introduces the color k in the valid coloring L, it cannot be implied by a set of variables coming before it (as the color k must appear in one of the implying variables). As π is consistent with the FDs, this means that we cannot have that x <π vt ≤π ux . We conclude that vt ≤π x. Since there must be an atom containing all variables of the FD, x and y are neighbors, and since y ∈ St , we conclude that x ∈ St as well. ◁ It is clear from the construction that the coloring L′ is connected. In L′ , as in L, the k maximum number of colors from [k] in an atom is CQ,∆ -width(Q,π ′ ) , as required by Item 2 of the lemma. By construction, the color k + 1 is introduced in vt which also introduces the last color of [k]. This proves Item 3 of the lemma. We will show next that every color of [k] appears in a variable of the bag Bt . We also have that every variable of Bt is a neighbor of a variable in St by definition of the bag. Since we assigned the color k + 1 to every variable in St , every color shares an atom with k + 1, as required by Item 1 of the lemma. It is left to prove the following claim. ▷ Claim C.3. [k] ⊆ L(Bt ). Proof. We define a sequence of bags Bi1 , . . . , Biℓ such that Bi1 = B is the bag from the definition of L, Bij+1 is the bag created by the second largest element of Bij , and Biℓ = Bt is the bag created by vt . We will prove that this sequence is well-defined and that [k] ⊆ L(Bij ) for every j ∈ [ℓ]. First, note that L(Bi1 ) = [k] by choice of L. Next, assume that [k] ⊆ L(Bij ) and Bij ̸= Bt . Let vij be the variable creating Bij (and thus the largest variable in Bij ). First, we claim that vij >π vt . To see this, observe that Bij contains the color k, which is introduced in vt . It follows that Bij must contain a variable ≥π vt . Since Bij only contains variables ≤π vij by definition, we deduce that vij ≥π vt . Since we are in the case that Bij ̸= Bt , we have that vij ̸= vt and thus vij >π vt , as claimed. Let c ∈ L(vij ). Since vij >π vt and vt introduces the last color, there exists a variable u <π vij with c ∈ L(u). Since the coloring L is connected, there is a path from vij to u on which every variable contains c. Let u′ be the first variable on this path such that u′ <π vij . By definition of the decomposition, Bij contains u′ . Since this is true for every color in L(vij ), we get that L(vij ) ⊆ L(Bij \ {vij }). It follows that L(Bij \ {vij }) = L(Bij ) ⊇ [k]. Hence, Bij \ {vij } = ̸ ∅, so Bij has a second largest element, and Bij+1 is well-defined. By definition of the decomposition, Bij+1 must contain Bij \ {vij }, so [k] ⊆ L(Bij \ {vij }) ⊆ L(Bij+1 ). Since the query is finite, the sequence Bi1 , . . . , Biℓ must end, and we get that Biℓ = Bt . ◁ This completes the proof of Lemma 5.6.

◀

▶ Proposition 5.9. For every self-join-free join query with FDs ∆ and every variable ordering π, we have CQ,∆ -width(Q, π) ≤ PQ,∆ -width(Q, π). In the proof of Proposition 5.9, we will use the following result, which is implicit in [19, Section 6]. We give a simple proof for the convenience of the reader. ▶ Lemma C.4. For every self-join-free CQ Q(X) and set ∆ of FDs, CQ,∆ (X) ≤ PQ,∆ (X).

F. Capelli, N. Carmeli, S. Mengel

27

Proof. Consider a valid coloring L of Q. Let d := maxRi (Xi )∈atoms(Q) |L(Xi )| be the maximum number of colors assigned to the variables of an atom by L. Let V be the set of variables of Q, then we define f : 2V → R+ by f (S) = |L(S)| d . We claim that f is a polymatroid. Clearly, f is monotone. For submodularity, consider A, B ⊆ V . Then, d · (f (A ∪ B) + f (A ∩ B)) = |L(A ∪ B)| + |L(A ∩ B)| = |L(A) \ L(B)| + |L(B) \ L(A)| + |L(A) ∩ L(B)| + |L(A ∩ B)| ≤ |L(A) \ L(B)| + |L(B) \ L(A)| + 2|L(A) ∩ L(B)| = |L(A)| + |L(B)| = d · (f (A) + f (B)) , so f is submodular and thus a polymatroid. Clearly, f is guarded by Q. Moreover, for every FD Y → z, we have L(z) ⊆ L(Y ) because L is valid. Thus d · f (Y ∪ {z}) = |L(Y ∪ {z})| = |L(Y )| = d · f (Y ), so f respects the FD. It follows that PQ,∆ (X) ≥ f (X) = |L(X)| ≥ CQ,∆ (X). ◀ d Proof of Proposition 5.9. The claim follows directly from Lemma C.4.

◀

▶ Proposition 5.10. For all k ∈ N, there is a join query Q, a variable order π, and a set of FDs ∆, such that PQ,∆ -width(Q, π ′ ) ≥ CQ,∆ -width(Q, π ′ ) + k for every ∆-reordering π ′ of π. Proof. The starting point is a join query Q′k (X ′ ) with a set of FDs ∆ from [19, Proposition 6.11] such that CQ′k ,∆ (X ′ ) ≤ 2, and for every N ∈ N, there is a database D of size N respecting ∆ such that |Q′k (D)| ≥ |D|k . Treating a join query as a set of atoms, we define Qk := Q′k ∪ {Rx (x, x∗ ) | x ∈ X ′ }, where x∗ is a fresh variable and all Rx are fresh relation symbols, and we set X := X ′ ∪ {x∗ }. Let π be an order of X, stable with respect to ∆, such that x∗ comes last. Note that x∗ does not appear in any FD, so π can be chosen by taking any ordering of X ′ , appending x∗ , and performing ∆-reordering. Observe that the bag created by x∗ in the disruption-free decomposition is B := X ′ ∪ {x∗ }, so B contains all variables of Qk . To bound the color number CQk ,∆ (B), let L be an optimal coloring, so CQk ,∆ (B) = ≤

|L(B)| maxRi (Xi )∈atoms(Qk ) |L(Xi )| |L(X ′ )| maxRi (Xi )∈atoms(Qk ) |L(Xi )|

+

′

≤

|L(X )| maxRi (Xi )∈atoms(Q′k ) |L(Xi )|

+

|L(x∗ )| maxRi (Xi )∈atoms(Qk ) |L(Xi )| |L(x∗ )| maxRi (Xi )∈atoms(Qk ) |L(Xi )|

′

≤ CQ′k ,∆ (X ) + 1 ≤ 3, where we use that L restricted to X ′ is a valid coloring for Q′k and CQ′k ,∆ (X ′ ) ≤ 2. For every bag B ′ of the decomposition, B ′ ⊆ B, and since CQk ,∆ is monotone, we get that CQk ,∆ (B ′ ) ≤ CQk ,∆ (B) ≤ 3. Therefore, CQ,∆ -width(Q, π) ≤ 3. Due to Proposition 5.4, for every ∆-reordering π ′ of π, CQ,∆ -width(Q, π ′ ) = CQ,∆ -width(Q, π) ≤ 3. To show the lower bound on PQk ,∆ (B), we extend for some N ∈ N the database D for Q′k from [19] into a database for Qk by fixing x∗ to a constant and adding all facts in Rx in which x takes any possible value. Call the resulting database D∗ , then the size of D∗ has increased w.r.t. that of D only by a constant factor at most. D∗

28

Lexicographic Direct Access with Functional Dependencies

satisfies all constraints in ∆ because so does D. Moreover, |Qk (D∗ )| = |Q′k (D)| ≥ |D|k . Due to Theorem 2.4, |Qk (D)| ≤ |D|PQ,∆ (X) . It follows that PQk ,∆ (B) ≥ k and thus PQk ,∆ -width(Qk , π) ≥ PQk ,∆ (B) ≥ k. Due to Proposition 4.5, for every ∆-reordering π ′ of π, PQk ,∆ -width(Qk , π ′ ) = PQk ,∆ -width(Qk , π) ≥ k. Given k ∈ N, we have that PQk+3 ,∆ -width(Qk+3 , π ′ ) ≥ k + 3 ≥ CQk+3 ,∆ -width(Qk+3 , π ′ ) + k for every ∆-reordering π ′ of π.

D

◀

Proofs for Section 6 (Linear Preprocessing Dichotomy)

▶ Lemma 6.4. Let Q(X) be a CQ and ∆ a set of FDs. The optimal value of the following linear program on variables σRi (Xi ) is CQ,∆ (X). minimize

X

σRi (Xi )

Ri (Xi )∈Q

X

subject to

σRi (Xi ) ≥ 1

∀S ⊆ V compatible with ∆ with S ∩ X ̸= ∅

Ri (Xi )∈Q:S∩Xi ̸=∅

σRi (Xi ) ≥ 0

∀Ri (Xi ) ∈ Q

Proof. Denote the variables of Q by V . A known characterization of the color number states that it is given by the optimal value of the following linear program [19, Proposition 6.10], which we denote P1 (Q, ∆). maximize h(X) subject to h(Xi ) ≤ 1

for every atom Ri (Xi ) of Q

h({z} | Y ) ≤ 0 I(S | V \ S) ≥ 0

for every FD Y → z of ∆ for every S ⊆ V

P with h(S1 | S2 ) = S:S∩S1 ̸=∅,S∩S2 =∅ I(S | V \ S) for every pair of disjoint sets S1 , S2 ⊆ V . We denote IS = I(S | V \ S). The linear program P1 (Q, ∆) can be rewritten as the follows. maximize

X

IS

S∩X̸=∅

subject to

X

IS ≤ 1

for every atom Ri (Xi ) of Q

S∩Xi ̸=∅

X

IS ≤ 0

for every FD Y → z of ∆

{z}⊆S⊆V \Y

IS ≥ 0

for every S ⊆ V

Consider the dual of P1 (Q, ∆). It has the same optimal value, and it has one variable per constraint of P1 (Q, ∆), that is, one variable σRi (Xi ) for each atom of Q and one variable σY →z for each FD of ∆. It has one constraint cS for every variable IS of P1 (Q, ∆), and it bounds the sum of the corresponding variables by the coefficient of IS in the objective function of P1 (Q, ∆). Its objective is to minimize the sum of the variables corresponding to

F. Capelli, N. Carmeli, S. Mengel

29

the constraints of P1 (Q, ∆) bounded by 1. The dual of P1 (Q, ∆), which we denote P2 (Q, ∆), is then X minimize σRi (Xi ) Ri (Xi )∈Q

subject to

X Ri (Xi )∈Q:S∩Xi ̸=∅

X Ri (Xi )∈Q:S∩Xi ̸=∅

X

σRi (Xi ) +

σY →z ≥ 1 for every S ⊆ V with S ∩ Xi ̸= ∅

Y →z∈∆:{z}⊆S⊆V \Y

X

σRi (Xi ) +

σY →z ≥ 0 for every S ⊆ V with S ∩ Xi = ∅

Y →z∈∆:{z}⊆S⊆V \Y

σRi (Xi ) ≥ 0 for every Ri (Xi ) ∈ Q, σY →z ≥ 0 for every Y → z ∈ ∆ We now proceed to simplify P2 (Q, ∆). Since all variables of P2 (Q, ∆) are non-negative, the constraints cS with S ∩ X = ∅ are trivially satisfied and can be removed. Second, as the objective function of P2 (Q, ∆) does not use variables of the form σY →z , we can set all such variables to 1 without changing the optimal value of the program. After doing so, each constraint cS for which there exists an FD Y → z in ∆ such that {z} ⊆ S ⊆ V \ Y is trivially satisfied. In other words, if S is not compatible with ∆, then cS is trivially satisfied after setting σY →z to 1 for all FDs Y → z in ∆. Hence, P2 (Q, ∆) is equivalent to the linear program stated in this lemma. ◀

E

Characterizing Linear Output Size

In this Appendix, we give new characterizations of the CQs with guaranteed linear output size. We say that Q has linear output size under ∆ if, for every database D respecting ∆, we have that |Q(D)| = O(|D|). As a stricter property, we say that Q is size preserving under ∆ if, over such databases, we have that |Q(D)| ≤ |D|. We previously only defined CQ,∆ and PQ,∆ when Q is a join query. In the following, we also use this notation when Q is a CQ by ignoring the projections. The main result of this section is the following Theorem. ▶ Theorem E.1. Let Q(X) be a self-join-free CQ, and let ∆ be a set of FDs. Then, the following statements are equivalent: 1. Q(X) is size preserving under ∆. 2. Q(X) has linear output size under ∆. 3. CQ,∆ (X) = 1. 4. PQ,∆ (X) = 1. 5. X is ∆-guarded in Q. Properties 1, 2 and 3 are already known to be equivalent [19, Theorem 6.1]. It remains to prove the equivalence of Properties 3, 4, and 5. We remark that there are some cases in which Theorem E.1 is already essentially known: In case there are no FDs, the color number, the fractional edge cover number, and the polymatroid bound coincide [4, Proposition 3.2] [19, Section 3.1]. In addition, in this case, the fractional edge cover number of a variable set S is 1 if and only if there is a single atom containing S (which is equivalent to S being ∆-guarded in that case). In case all FDs are unary, some of these equivalences are known and implicit in prior work [19, 3, ?]. ▶ Lemma E.2. Let Q(X) be a CQ, and let ∆ be a set of FDs. If X is ∆-guarded in Q, then PQ,∆ (X) = 1.

30

Lexicographic Direct Access with Functional Dependencies

Proof. PQ,∆ (X) ≥ 1 since the function that assigns 1 to every set is a polymatroid. So it suffices to show the upper bound. If X is ∆-guarded, there is an atom Ri (Xi ) with Xi →∗ X. For any polymatroid respecting ∆, we then get h(X) ≤ h(XXi ) = h(Xi ) ≤ 1, where the first inequality is by monotonicity, the second is due to the FDs, and the third is since h is guarded by Q. Thus, PQ,∆ (X) ≤ 1. ◀ Proof of Theorem E.1. Properties 1, 2 and 3 are known to be equivalent [19, Theorem 6.1]. We prove next the equivalence of Properties 3, 4, and 5. Observe that CQ,∆ (X) ≥ 1 as coloring all variables with the same single color is always a valid coloring. If PQ,∆ (X) = 1, then using Lemma C.4, 1 ≤ CQ,∆ (X) ≤ PQ,∆ (X) = 1, and so CQ,∆ (X) = 1. By Lemma 6.3, if CQ,∆ (X) = 1, then X is ∆-guarded. Finally, by Lemma E.2, if X is ∆-guarded, then PQ,∆ (X) = 1. ◀

F

Proofs for Section 7 (Connection between the approaches)

We will need the fact that every bag of the extended query is contained in some extension of a bag of the original query. More specifically, we prove the following lemma. ▶ Lemma F.1. Let j be the smallest index such that vj implies vi . Then, Bi ⊆ b+ j . Remark that, in Lemma F.1, j ≤ i because vi implies itself regardless of the set of FDs. We proceed to showing claims that will help prove the lemma. ▷ Claim F.2. If va →∗ vb (with unary FDs), then there is a path between va and vb in Q that uses only variables that imply vb . Proof. Since va →∗ vb , there is a sequence va = v1 , . . . , vk = vb with an FD vi → vi+1 in ∆ for every i ∈ [k − 1]. This sequence forms the required path. ◀ ▷ Claim F.3. Let j be the smallest such that vj implies vi . If va →∗ vb , with b ≥ i, then a ≥ j. Proof. Assume by way of contradiction that a < j. Since a < j ≤ i ≤ b and it is a consistent ordering, va →∗ vb means that vi must be implied by va or a variable preceding it, which is a contradiction to the minimality of j. ◀ ▷ Claim F.4. Let j be the smallest such that vj implies vi . If va , vb are neighbors in Q+ with a, b ≥ i, then there is a path between va and vb in Q that uses only variables ≥ j. Proof. If va , vb are neighbors in Q, the claim is immediate. Otherwise, since they are neighbors in Q+ , there exist variables vc and vd , neighbors in Q, that imply va and vb respectively (it could be the case that c = d). By applying Claim F.2 twice, there is a path va , . . . , vc , vd . . . , vb in Q using only variables that imply va or vb . By using Claim F.3 on all variables of the path, and since a, b ≥ i, these variables are all ≥ j. ◀ Proof of Lemma F.1. Let vt ∈ Bi . We need to show that vt ∈ b+ j . We have that vj ∈ bj ⊆ + ∗ b+ , and since v → v , we have that v ∈ b . Thus, if t ∈ {i, j}, we have that vt ∈ b+ j i i j j j . Recall that j ≤ i because vi implies itself. Thus, it remains to handle the case that j < t < i and the case that t < j. Consider the case that j < t < i. First we claim that vj is not implied by any variable preceding it. Indeed, since vj →∗ vi , such a variable would transitively imply vi , contradicting the minimality of j. Since the ordering is consistent, no variable preceding vj implies it, and

F. Capelli, N. Carmeli, S. Mengel

vj →∗ vi , we get that vj implies all variables between vj and vi . Since j < t < i, we have that vj →∗ vt . Since vj ∈ bj , we conclude that vt ∈ b+ j . The last case is that t < j ≤ i. By Claim F.2, since vj →∗ vi , there is a path between vj and vi that only goes through variables that imply vi . Due to the minimality of j, these variables are all ≥ j. Since vy ∈ Bi , there is a path vt , vk , . . . , vi in Q+ that only goes through variables ≥ i. By applying Claim F.4 on the edges of vk , . . . , vi , we get a path from vk to vi in Q that only goes through variables ≥ j. By combining these paths, we get a path from vk to vj that only goes through variables ≥ j. It follows that vk ∈ Sj , where Sj is the set from the definition of the disruption-free decomposition of Q. Thus, if vt neighbors vk in Q, we conclude that vt ∈ bj ⊆ b+ j , and we are done. Otherwise, since vt neighbors vk in Q+ , there exist variables va and vb , neighbors in Q, that imply vt and vk respectively (again, it could be that a = b). Since vb →∗ vk , from Claim F.2 and Claim F.3, we get a path between vb and vk using only variables ≥ j. Since va →∗ vt , from Claim F.2 we get a path from va to vt on which all variables imply vt . Let vm be the first variable on this path smaller than j (it exists because t < j). By composing the paths we discovered, we get a path vm , . . . , va , vb . . . , vk . . . , vj in Q that, other than vm , only uses variables ≥ j. Thus, vm ∈ bj , and since vm →∗ vt , we get that vt ∈ b+ ◀ j .

We use Lemma F.1 to relate ρ∗Q+ -width(Q+ , π), PQ+ ,∅ -width(Q, π) and PQ+ ,∅ -width(Q, π).

▶ Proposition 7.4. Let Q be a self-join-free join query, ∆ a set of FDs, and π a consistent ordering π with respect to ∆. Let moreover Q+ be the extension of Q. Then, CQ,∆ -width(Q, π) = PQ,∆ -width(Q, π) = ρ∗Q+ -width(Q+ , π). Proof. By Proposition 5.9 and Proposition 7.1, we have CQ,∆ -width(Q, π) ≤ PQ,∆ -width(Q, π) ≤ ρ∗Q+ -width(Q+ , π), so it suffices to show ρ∗Q+ -width(Q+ , π) ≤ CQ,∆ -width(Q, π). Let L be any coloring of {v1 , . . . , vn }. We define a new coloring L′ by setting for every variable v L′ (v) := L(v) ∪

[

L(z).

v→∗ z∈∆

Clearly, L′ is ∆-valid by construction. We claim that for every set S, we have L′ (S) = L(S + ). For every variable z ∈ S + , there is a variable y ∈ S such that y →∗ z. By definition of L′ , we have that L(z) ⊆ L′ (y). Consequently, L(S + ) ⊆ L′ (S). Finally, if c ∈ L′ (v) for some v ∈ S, then either c ∈ L(v) or c ∈ L(z) for some v →∗ z ∈ ∆. In any case, c ∈ L(S + ). Consider any bag Bi of the disruption-free decomposition of Q+ . By Lemma F.1, there

31

32

Lexicographic Direct Access with Functional Dependencies

is an index j such that Bi ⊆ b+ j . It follows that CQ+ ,∅ (Bi ) = max L1

≤ max L1

= max L1

=

|L1 (Bi )| maxRi (Xi )∈atoms(Q) |L1 (Xi+ )| |L1 (b+ j )| maxRi (Xi )∈atoms(Q) |L1 (Xi+ )| |L1 ′ (bj )| maxRi (Xi )∈atoms(Q) |L1 ′ (Xi )|

max

|L2 (bj )|

∆-valid L2 maxRi (Xi )∈atoms(Q) |L2 (Xi )|

= CQ,∆ (bj ), By Section 3.1 of [19], we have for all sets S that ρ∗Q+ (S) = CQ+ ,∅ (S), so we get ρ∗Q+ (Bi ) ≤ CQ,∆ (bj ). It follows that ρ∗Q+ -width(Q+ , π) ≤ CQ,∆ -width(Q, π), which completes the proof. ◀

Related documents

• TrajectoryDB: A New Database for Agent Trajectories#673620
• Preserving contextual information in cultural heritage metadata through multidimensional knowledge graphs#673621
• X-DigCheck: Co-Evolving Application Profiles and Knowledge Graphs, Demonstrated on the RTI Documentation of Rupe Magna#673622
• Open Tabular Insight Extraction: Where Do We Stand, and Where Should We Go?#673623
• Protocol effects on feature-based hardware-Trojan detection across Trust-Hub families#673624