最坏情形最优连接

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

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

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

取

覆盖约束是 $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})$ 界；它没有排除额外使用半连接、索引或多路过滤的执行器。

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

若每张表包含同一匹配二元组的 $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 界。边缘分布既不需要均匀，也不需要互相独立；均匀性只用于最初选取完整答案。

运行时间实际包含什么 ​

三角形算法读取、分组并建立哈希表公理库哈希表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 完全、固定查询成员判定的数据复杂度结论回答不同的问题。