最坏情形最优连接

一张表约束它所涉及属性的联合取值。三角形查询中，每个属性被两张表约束，给每张表半份权重，便恰好覆盖每个属性一次。输出元组若很多，其联合不确定性就大；但每张输入表都限制了一部分不确定性，覆盖权重把这些限制合成为总输出的上界。

执行算法面临的是另一件事：先连接两张表，可能暂时枚举许多最终会被第三张表否决的组合。共享值的度数很大时，这一步尤其昂贵。重轻分解对高度数值改从第三张表出发，对低度数值才展开二元连接，从而把两种不同的枚举成本配平。

三角形的精确证书与达到上界的输入 ​

取

覆盖约束是 $x_R+x_T\ge 1$、$x_R+x_S\ge 1$、$x_S+x_T\ge 1$。三个整覆盖 $(1,1,0),(1,0,1),(0,1,1)$ 与半覆盖 $(1/2,1/2,1/2)$ 分别给出四个界，而且最优值恰为

这不只是列出四个可行解。令 $a=\log r,b=\log s,c=\log t$。若 $a\ge b+c$，任一覆盖的代价满足

整覆盖 $(0,1,1)$ 达到它。另两个超长边情形同理。剩下的情形满足三角不等式；置

它们非负。将三个覆盖约束分别乘以 $y_A,y_B,y_C$ 再相加，任一可行代价至少为 $(a+b+c)/2$，而半覆盖达到它。这就穷尽了全部大小组合，包括某张表只有一行的边界。

令 $X,Y,Z$ 都有 $k$ 个值，取 $R=X\times Y,S=Y\times Z,T=X\times Z$。三张表各有 $N=k^2$ 行，连接恰为 $X\times Y\times Z$，共有 $k^3=N^{3/2}$ 行。因此等大输入的指数 $3/2$ 不能降低。非平方或任意指定大小未必精确取等；一般 AGM 紧性结论允许一个仅依赖查询的常数因子。

三角形的重轻枚举 ​

令 $R[b]=\{a:(a,b)\in R\}$，$S[b]=\{c:(b,c)\in S\}$，记 $d_R(b)=|R[b]|$。选阈值 $\tau >0$，定义重值集合 $D=\{b:d_R(b)>\tau \}$。以下伪代码使用集合成员索引，并按 $B$ 分组；阈值可以是实数，直接与整数度数比较。

Triangle(R, S, T):
    if any input is empty: return
    build membership indexes for R, S, T
    group R and S by their B coordinate
    tau = sqrt(|R| * |T| / |S|)
    D = {b in keys(R): |R[b]| > tau}

    for b in D:                         # 重值：从第三张表出发
        for (a, c) in T:
            if (a, b) in R and (b, c) in S:
                emit (a, b, c)

    for b in keys(R) with b not in D:    # 轻值：展开受控的二元连接
        for a in R[b]:
            for c in S.get(b, empty):
                if (a, c) in T:
                    emit (a, b, c)

每个输出的 $b$ 恰好属于一个分支。重分支遍历其必需的 $T$ 元组再核验另外两项；轻分支直接枚举 $R,S$ 的匹配再核验 $T$。因此既不漏报，也没有跨分支重复；集合输入保证每个分支内部同样不重复。

因为 $|D|\tau \le \sum _{b\in D}{d}_R(b)\le r$，重分支的候选数至多 $rt/\tau$。轻分支的候选数满足

取 $\tau =\sqrt{rt/s}$，两项分别至多 $\sqrt{rst}$，合计至多 $2\sqrt{rst}$。若要达到大小不等时的 $U$，先比较四个代价值：半覆盖最小时用以上算法；否则枚举相应两张表的笛卡尔积，检查共享坐标相等及第三张表的成员关系。后三种方法分别至多检查 $rs,rt,st$ 个候选。无需把四种算法都运行一次。

16 行输入为什么产生 72 与 24 ​

在每张表的两个属性位置放入同一个对称星形关系

每张表有 $16$ 行。先做任意一对二元连接时，共享值 $0$ 产生 $8\cdot 8=64$ 个元组，八个叶值各产生一个，共 $72$ 个。最终答案却为空：星形图没有三角形；具体地，两步路径的两端要么都是叶子，要么都是 $0$，都不属于第三张表。

重轻算法取 $\tau =\sqrt{16}=4$，唯一重值是 $0$。重分支枚举 $D\times T$ 的 $16$ 个候选；每个轻值只有一条 $R$ 记录与一条 $S$ 记录，轻分支共枚举 $8$ 个。总共 24 个候选，最后全部拒绝。一个候选可能执行两次成员查询，这个数不是哈希探测总数。

把 $8$ 换成 $k$，三张表大小 $N=2k$，任意第一步二元连接都有 $k^2+k=\mathrm{\Theta }(N^2)$ 行，最终仍为空。当 $k>2$ 时，阈值 $\sqrt{2k}$ 仍把中心单独列为重值，这个分解只产生 $2k+k=3k$ 个候选。于是差距随着规模增长，不只是一次 $72$ 与 $24$ 的数值比较。这说明仅选定二元连接次序、物化其中间结果不能保证三角形的 $O(N^{3/2})$ 界；它没有排除额外使用半连接、索引或多路过滤的执行器。

一般 NPRR：按锚关系拆分属性 ​

下面展开原始 NPRR 的边顺序递归，而非把逐个属性的 Generic Join 改名为 NPRR。[4, Algorithms 2–4、Procedure 5] 先固定边顺序 $e_1,\dots ,e_m$。对当前属性块 $U$ 和前 $k$ 张表，以 $e_k$ 为锚，拆成

$V=\varnothing$ 时先单独处理：每张零列表只有空集或 $\{()\}$ 两种可能，检查全部表后返回空集或 $\{()\}$，成本为 $O(m+1)$；没有输入表时按空合取返回 $\{()\}$。以下计划树及显式查询因子均限于 $m,n\ge 1$。

查询计划树的左子问题是 $(W,k-1)$，右子问题是 $(Z,k-1)$。空属性块不建节点；若一个块不与前面的任何边相交，也不再建子树。若 $U$ 包含于每个 $e_i$（$i\le k$），就停止为叶子。其余情况继续拆分。树只依赖查询，不依赖数据；每层属性块两两不交、每条路径的 $k$ 严格下降，所以节点数 $H\le mn$。

按左块在前、右块在后的顺序输出属性；没有右子树时仍输出只由锚覆盖的剩余属性。这给出一个全局次序，使每个递归属性块连续。每张表按这个次序的限制建立前缀索引，支持三种操作：前缀是否存在；固定前缀后某段属性投影有多少个不同元组；枚举该投影。计数存在索引中，不为每次询问重新扫描原表。用原文的哈希索引实现，可在 $O(n^2\sum _i{N}_i)$ 期望时间内完成预处理；一次访问至多处理 $n$ 个属性。[4, §5.3.2]

记 $R_i[s]$ 为把已赋值属性限制为 $s$ 后、删去这些属性所得的切片。一次调用处理 $(U,k,y,s)$：$y_1,\dots ,y_k$ 覆盖 $U$，$s$ 是全局次序中 $U$ 之前属性的固定取值。其任务是求各切片在 $U\cap e_i$ 上投影的连接。只涉及已赋值属性的约束也要检查：它的零列投影为真关系 $\{()\}$ 或空关系，不能把空关系当成没有约束。

Join(U, k, y, s):
    检查前 k 张表的相关切片投影；若有空集，返回空集
    若 U 为空，返回 {s}
    若 U 包含于每个 e_i (i <= k):
        枚举最小的 U 投影，只保留属于其余全部投影的元组
        返回它们与 s 的拼接

    W = U \ e_k; Z = U ∩ e_k
    L = {s} 若 W 为空，否则 Join(W, k-1, y[1:k-1], s)
    若 Z 为空，返回 L
    q = 锚关系 R_k[s] 在 Z 上的投影大小

    对每个 (s,w) in L:
        A_i = R_i[(s,w)] 在 Z ∩ e_i 上的投影 (i < k)
        若某个 A_i 为空，跳过本前缀
        alpha = y_k
        若 alpha < 1，计算 p = product_i |A_i|^(y_i/(1-alpha))
        若 alpha < 1 且 p < q:
            递归 Join(Z, k-1, y[1:k-1]/(1-alpha), (s,w))
            用锚关系的 Z 投影过滤递归答案
        否则:
            枚举锚关系的 Z 投影，用所有 A_i 过滤
        输出通过过滤的完整拼接

零权重对应的因子为一；先拒绝空切片，再计算乘积，因此无需把 $0^0$ 当成有效成本。比较相等时扫描锚关系，只有严格 $p<q$ 才递归。覆盖权重作为查询输入，预算比较沿用算术成本口径；固定有理权重时也可清分母比较整数幂，不依赖浮点近似来决定分支。

递归调用确实有合法覆盖。$W$ 中的属性不属于 $e_k$，所以删掉 $y_k$ 后仍被覆盖。对 $z\in Z$，若 $\alpha <1$，

若某个 $Z$ 属性只由锚覆盖，必有 $\alpha \ge 1$，算法直接扫描锚，不会调用不存在的右子树。

正确性按树归纳。叶子求的是集合交；内部节点中，任何完整答案的 $W$ 投影必在左侧结果 $L$ 中。固定该前缀后，它的 $Z$ 部分既满足全部 $A_i$，也属于锚投影。两种分支都恰好枚举其中一边、检查另一边，故无漏报也无误报。不同 $w$ 对应不同完整元组，集合索引内没有重复，因此不会重复输出。根调用没有尚未处理的属性，返回的正是完整连接；中间的投影连接只保证包含所有能延伸为最终答案的前缀，并不声称每个前缀都能延伸。

非三角超图的两层分支 ​

取四张三元表

每张表在其显示的列顺序上都使用七个元组

每个属性出现三次，故 $x_i=1/3$ 是覆盖。将四条覆盖约束相加得 $3\sum _i{x}_i\ge 4$，所以等大表的最优证书是 $U=7^{4/3}$。这是四维 Loomis–Whitney 查询；它不是三角形，也不是一般超图的穷举代表，算法的普适性来自上一节的递归证明。

按上面的边顺序，根的锚为 $R_4$，先处理 $W=\{D\}$，再处理 $Z=\{A,B,C\}$。左侧三个一列投影都是 $\{0,1,2\}$，扫描最小投影产生三个前缀。固定 $D$ 后，前三张表变成三角形的三个二列切片；根的锚预算始终为 $q=7$。

后两次递归的锚是 $AB$ 表，先求三个变量中剩余的 $C$，只有 $C=0$。此时另外两个一列切片大小都为一，预算 $p=q=1$，按相等分支扫描一行锚。完整输出按 $ABCD$ 顺序为

枚举循环共执行 $3+7+2(1+1)=14$ 次；其中根的最终扩展候选只有 $7+1+1=9$ 个。两种计数都不是哈希探测总数：每个候选还要做成员检查，预算计算也会读取切片计数。

任意两张原表先二元连接时，共享的两个坐标为 $00$ 会产生 $3\cdot 3=9$ 个组合；共享坐标中的四个非零单点各贡献一行，总共 $13$ 行。将取值 $1,2$ 扩展到 $1,\dots ,h$，有

上述 NPRR 执行的枚举循环为 $(h+1)+(1+3h)+2h=6h+2$ 次。因为 $(1+2h{)}^{3/2}>1+3h$（平方后差为 $3h^2+8h^3>0$），$D=0$ 始终走扫描锚分支，正值始终递归。这给出了随规模增长的成本差，而非仅在七行输入上的巧合。

集合、投影与约束的边界 ​

若每张表包含同一匹配二元组的 $N$ 份副本，bag 连接有 $N^3$ 个输出出现次数。集合 AGM 界约束的是不同完整元组，不能套在这个重复次数上。若查询投影掉部分变量，完整见证的数量仍受本页界约束，但可能远大于去重后的答案数，因此这里没有证明投影查询按实际答案规模最优。

键约束、函数依赖或已知度数分布会缩小允许实例的范围，可能给出更强的界。AGM 使用的只是表大小和属性覆盖；上面的无三角形星形实例也表明，它通常不是单个实例的精确输出预测。

用条件熵证明一般 AGM 界 ​

若 $J$ 为空，结论立即成立。否则从 $J$ 中均匀抽一个完整元组 $X_V$，于是 $H(X_V)=\log |J|$。按某个固定次序把属性写成 $v_1,\dots ,v_n$，记 $X_{<j}=(X_{v_1},\dots ,X_{v_{j-1}})$。使用条件熵公理库条件熵Conditional entropy已知一个随机变量后另一个随机变量剩余不确定性的平均值。的链式法则与“增加条件平均不增熵”，对每个 $e_i$ 有

乘以非负的 $x_i$ 后求和，换序并使用覆盖约束，得到

第二步用到了离散条件熵非负。另一方面，$X_{e_i}$ 的支持集包含在 $R_i$ 中，故 $H(X_{e_i})\le \log N_i$。合并便有 $\log |J|\le \sum _i{x}_i\log N_i$，取指数即得 AGM 界。边缘分布既不需要均匀，也不需要互相独立；均匀性只用于最初选取完整答案。

一般递归的成本为何不会乘出巨大中间表 ​

固定一次调用，记各非空投影大小为

零列真关系的大小为一。所有 $b_i\ge 1$，所以 $B\ge 1$；空切片检测的成本稍后另计。左递归的投影不比这里的大，故其预算 $B_L\le B$，而 AGM 给出 $|L|\le B_L$。

固定 $w$，令 $a_i(w)=|A_i|$。若 $\alpha =y_k<1$，两种扩展的较小预算满足

若 $\alpha \ge 1$，扫描成本预算为 $q$；由于非空切片大小都至少一，同样有 $q\le q^{\alpha }\prod _{i<k}{a}_i(w{)}^{y_i}$。

现在不能直接将每个前缀的最坏成本乘以 $|L|$。需要把式 (1) 对 $w$ 求和，并利用切片互不相交。所用的离散不等式是：若 $z_i\ge 0$、$\sum _i{z}_i\ge 1$，则

证明如下。零权重略去；若某个正权重因子的总和为零，左侧也为零。否则将每个 $f_i$ 除以自身总和，得到 $0\le p_i(t)\le 1$。令 $c=\sum _i{z}_i$、${\lambda }_i=z_i/c$，则 $z_i\ge {\lambda }_i$，从而

第二步是加权算术—几何平均不等式，证明了式 (2)。

按全局次序把 $W$ 写为 $w_1,\dots ,w_d$，从最后一个坐标开始消去求和。含有该坐标的因子具有总权重至少一，因为锚不含 $W$；不含该坐标的因子可提出求和号。对其余因子使用式 (2)，切片大小的和至多是把该坐标重新加入投影后的大小。不同坐标值对应不相交切片；只对 $L$ 允许的值求和可能漏掉一些切片，因此用的是“至多”。依次消去全部 $W$ 坐标，得到

没有剩余坐标时，式 (3) 就是单次扩展界。若某前缀的切片为空，直接拒绝它，不把检查开销记成“零时间”。

为把递归调度也写进账本，设 $h(u)$ 为当前计划子树节点数。可按树归纳给出一个保守界：非空调用的时间至多为 $Cmnh(u)B$，其中 $C$ 为统一常数。叶子扫描最小投影，其大小不超过 $B$，每个元组最多检查 $m$ 张表、每次至多处理 $n$ 个属性。内部节点的左递归由 $B_L\le B$ 支付；对所有右递归，归纳成本中的预算之和由式 (3) 支付。所有计数、空切片拒绝、分支决定和最终过滤的额外开销不超过 $O(mn)(|L|+\sum _{w}t(w)+1)=O(mnB)$。将左右子树系数相加再加当前节点，正好由 $h(u)$ 控制。

根的非空输入给出 $B=\prod _i{N}_i^{x_i}$、$H=h(\mathrm{root})\le mn$。因此这份逐项账本证明了

对固定查询，$m,n,H$ 都是常数；选择最优覆盖后就是 $O(\sum _i{N}_i+U)$。式 (4) 故意保留一个较松的查询因子，以完整支付递归管理和空切片检查。原文更紧的 $O(mnU+n^2\sum _i{N}_i+m^{2}n)$ 作为其一般算法定理引用，[2, Theorem 3.2；4, Theorem 5.1] 并不冒称由这份较松账本已经证明同样的查询因子。求覆盖的线性规划成本另计；输入覆盖和预建索引都不是免费的隐藏步骤。

运行时间实际包含什么 ​

三角形算法读取、分组并建立哈希表公理库哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。索引，预处理的期望时间与空间都是 $O(r+s+t)$。假设属性值及固定长度元组可用常数个机器字表示，哈希与相等比较为常数成本，并维持适当负载因子，每个候选的成员检查具有期望 $O(1)$ 成本。因此选择最佳证书后的总期望时间为

答案可以流式输出，额外工作空间为 $O(r+s+t)$；若保存全部答案，还须加上输出空间。长字符串的读写与比较、外存 I/O，以及比较树索引带来的对数因子，都不在这个单位成本哈希模型中。

固定查询的结构常数不能在查询也增长时隐去。NPRR 原文 Theorem 3.2 给出的一般界为 $O(mnU+n^2\sum _i{N}_i+m^{2}n)$，其中 $m$ 是关系数、$n$ 是属性数。这是枚举保证，与合取查询的联合成员判定 NP 完全、固定查询成员判定的数据复杂度结论回答不同的问题。