数据库约束表示与P2P系统高效Top-k查询处理

# 数据库约束表示与P2P系统高效Top-k查询处理 ## 1. Codd表约束表示相关研究 ### 1.1 寻找Armstrong表的时间复杂度 在使用Codd表表示约束时，寻找Armstrong表的时间复杂度是精确指数级的。具体而言，存在一种算法用于计算给定一组唯一约束（UCs）、函数依赖（FDs）和非空约束集（NFS）下的Armstrong表，该算法的运行时间与属性数量呈指数关系。而且，对于某些UCs、FDs和NFS，最小规模的Armstrong表中的行数也是指数级的，这意味着仅记录该关系就需要指数级的时间。 ### 1.2 计算得到的Armstrong表的大小 一个实际问题是，最小规模的Armstrong表需要多少行。若对于给定的UCs、FDs和NFS，不存在行数更少的Armstrong表，则该表为最小规模。有定理表明，在输入为（T, Σ, Ts）时，算法7计算出的Armstrong表的大小，最多是最小规模Armstrong表大小的二次方。 ### 1.3 表示方式的大小 不同的表示方式没有一种能完全主导另一种，因此建议同时使用这两种表示方式。存在一些表模式T、UCs和FDs集合Σ以及NFS Ts，使得Σ的大小为O(n)，而最小规模的Armstrong表大小为O(2n/2)；也存在一些情况，使得Armstrong表的行数为O(n)，而Σ相对于Ts的最优覆盖大小为O(2n)。 ### 1.4 约束集与Armstrong表的作用 约束集有助于识别那些被错误认为有意义的约束，而Armstrong表则有助于识别那些被错误认为无意义的约束。 ### 1.5 总结 对Codd表上的UCs和FDs组合类在弱可能世界语义下进行了研究，从公理、算法和逻辑等方面对蕴含问题进行了刻画。将约束集表示为Codd表的研究结果涵盖了经典发现，表明将全关系理论推广到实际数据库系统中的Codd表不会有额外代价。 ## 2. 过载P2P系统中的高效早期Top-k查询处理 ### 2.1 问题提出 传统的P2P系统中的Top-k查询处理虽然能减少网络流量，但可能会显著延迟用户获取答案的时间。因为通常要等所有被查询的节点都处理完查询后才返回结果，查询响应时间受最慢节点的影响，在节点过载的P2P系统中，这个问题更为突出。因此，需要解决在过载P2P系统中减少用户等待时间的问题，将其重新定义为P2P系统中的早期Top-k查询处理问题。 ### 2.2 新指标引入 为了补充响应时间，引入了两个新指标：稳定时间和累积质量差距。 - **稳定时间**：在查询执行过程中，用户接收到的Top-k中间结果不再变化的时间点，该时间可能远小于响应时间。 - **累积质量差距**：直到稳定时间为止，中间Top-k结果集与最终Top-k结果集之间的质量差异之和。累积差距越小，返回给用户的中间结果质量越高。具体定义为：设q为一个Top-k查询，Y(t)为查询q在时间t在查询发起者处的质量演化，s为查询q的稳定时间，则查询q的累积质量差距cqg为： \[ cqg = \int_{0}^{s} (1 - Y(t)) dt = s - \int_{0}^{s} Y(t) dt \] ### 2.3 P2P系统模型 #