约束数据库与最近邻问题：维度影响的深度剖析

### 约束数据库与最近邻问题：维度影响的深度剖析 #### 1. 约束数据库中的正交维度与查询评估 在约束数据库领域，对于 P - 安全的布尔连接合取查询（P - safe BCCQ）有着独特的性质。若 q 是一个 P - 安全的 BCCQ 查询，它由合取查询 {q1, …, qn} 的布尔组合构成。由于 q 是 P - 安全的，满足 BB(q) = ∅ = BB(q1) ∪ … ∪ BB(qn)，所以对于 i ∈ {1, …, n}，有 BB(qi) = ∅。每个 qi 是安全的，属于 ALGℓ，并且会产生正交维度为 ℓ 的关系。而 q 本身涉及对正交维度为 ℓ 的关系进行布尔运算，因此也属于 ALGℓ。 新查询 q′ 的获取较为容易。若 q 是形如 πσ 的合取查询的布尔组合，那么 q′ 可通过将 q 中的所有 σ 替换为 ˜σ 得到。由此可以得出，存在一种对 P - 安全的 BCCQ 的评估方式，使得每个操作仅处理维度为 ℓ 的点集。具体总结如下： - 若 s 是正交分解为 P 的数据库模式，那么在 s 上评估 P - 安全的 BCCQ 的复杂度仅与全局维度呈线性关系。 在多维数据库中，对其中对象的几何形状进行了限制。这些限制一方面可以通过对表示数据库的约束公式进行句法限制来轻松刻画；另一方面，能确保在评估诸如 P - 安全的 BCCQ 这类大量查询时具有更好的性能。实际已经证明，查询评估的复杂度与全局维度呈线性关系。 不过，当前既限制了数据库的类别，也限制了感兴趣的查询类别。尽管这两类在实际应用中都极具价值，但可以尝试放宽这些限制。由于具有有界松散正交维度的输入类的闭包性质较差，因此可以考虑采用严格正交维度。不过，在小维度（例如 d ≤ 3）的关系情况下，这一类别仍值得深入研究，并且可以证明某些相关结果（如定理 3、4 等）在这类关系中同样适用。 查询类别也可以向多个方向扩展。例如，投影仅限于对同一组件的变量进行投影的 P - 安全查询子类也具有类似性质，它们可以重写为 ALGℓ 查询。在一个时空应用中，在 dedale 系统上运行正交维度为 2 的对象。这种限制对用户是透明的，并且 P - 安全的 BCCQ 的评估仅依赖于二维操作，这使得可以以处理二维数据的成本来处理多维数据。 #### 2. 最近邻问题概述 近年来，许多研究人员致力于寻找最近邻（NN）问题的高效解决方案。该问题的定义为：在一个 m 维度量空间中，给定一组数据点和一个查询点，找出距离查询点最近的数据点。特别地，在高维空间中解决此问题备受关注，这是因为一些技术会用长“特征”向量来近似复杂数据，如图像、序列、视频和形状等。相似性查询通过将给定的复杂对象近似为高维向量作为查询点，然后在底层特征空间中确定与之最接近的数据点。 相关研究主要有以下三个方面的贡献： 1. **维度对最近邻距离的影响**：在一系列广泛的条件下（比独立同分布维度的条件更宽泛），随着维度的增加，最近邻距离会趋近于最远邻距离。也就是说，不同数据点之间的距离差异会逐渐消失。这一结果并非针对特定算法，而是针对问题本身，并且同样适用于 k - 最近邻问题。结合高维 NN 大多是某些领域相似性启发式方法的情况，这引发了对许多将相似性问题映射到高维 NN 问题的有效性的质疑。此外，一些用于提高性能的近似最近邻技术可能会进一步加剧这个问题。 2. **实际数据验证**：基于合成分布的实证结果表明，在低至 15 维时，最近邻和最远邻的区别可能就会变得模糊。对真实图像数据库的实验也表明，这种维度效应在实际中确实存在。这意味着在多媒体相似性搜索中使用高维特征向量表示时需要谨慎，必须检查工作负载是否能为典型查询提供最近邻和最远邻之间的清晰区分（例如通过采样）。同时，也识别出了一些特殊的工作负载，在这些工作负载下，高维中的最近邻概念仍然是有意义的。 3. **现有研究的问题**：数据库文献中关于最近邻处理技术的研究未能将新技术与线性扫描进行比较。从相关数据可以推断，在高维情况下，线性扫描在大多数被检查的数据集上几乎总是优于所提出的技术。这并不奇怪，因为用于评估这些技术的工作负载属于研究中确定的“表现不佳”的工作负载类别。虽然所提出的方法可能在适当选择的工作负载下有效，但在性能评估中并未对此进行研究。 #### 3. 最近邻的意义探讨 最近邻问题是指在一个数据集中确定距离给定查询点最近的点，该问题在地理信息系统（GIS）中经常被使用，例如查询“哪个城市离我当前位置最近”。然而，并非所有情况下最近邻查询都有有意义的答案。 例如，在某些情况下，即使存在明确的最近邻，但最近邻与数据集中其他点之间的距离差异非常小，这使得该答案在解决实际问题（如最小化旅行成本）时的实用性很低。此外，如果每个点的位置被认为位于某个置信度较高的圆内（可能是由于计算位置时的数值误差或推导点的算法产生的“启发式误差”），那么在这种情况下，以合理的置信度确定最近邻是不可能的。 在二维地理数据库或其他