提出按冗余度排序找前k个函数依赖,提升效率与实用性。
Redundancy-Driven Top-$k$ Functional Dependency Discovery
- 基于冗余度筛选,用上界剪枝加速搜索
- 在40多个数据集上速度更快、内存更低
- 适合处理大规模高维数据的依赖发现
函数依赖(FDs)是关系数据库的基本约束,广泛应用于数据管理。现有发现算法通常生成所有有效依赖,导致两个问题:计算成本高——复杂度随元组数平方增长、属性数指数增长;结果集过大,难以识别有用依赖。本文提出SDP(选择性发现与剪枝)方法,按冗余度排序找出前k个函数依赖。冗余度衡量依赖解释的重复信息量,直接关联存储开销与更新异常。SDP利用冗余的上界进行剪枝,证明该上界具有单调性:增加属性会细化划分,从而降低上界。一旦上界低于前k阈值,整条分支可跳过。进一步引入三项优化:按划分基数排序属性、使用划分基数矩阵中的成对统计量紧化上界、全局调度器优先探索有希望的分支。在超过40个数据集上的实验表明,相比穷举方法,SDP显著更快且内存消耗更少。
原文摘要 · Abstract (English)
Functional dependencies (FDs) are basic constraints in relational databases and are used for many data management tasks. Most FD discovery algorithms find all valid dependencies, but this causes two problems. First, the computational cost is prohibitive: computational complexity grows quadratically with the number of tuples and exponentially with the number of attributes, making discovery slow on large-scale and high-dimensional data. Second, the result set can be huge, making it hard to identify useful dependencies. We propose SDP (Selective-Discovery-and-Prune), which discovers the top-$k$ FDs ranked by redundancy count. Redundancy count measures how much duplicated information an FD explains and connects directly to storage overhead and update anomalies. SDP uses an upper bound on redundancy to prune the search space. It is proved that this upper bound is monotone: adding attributes refines partitions and thus decreases the bound. Once the bound falls below the top-$k$ threshold, the entire branch can be skipped. We improve SDP with three optimizations: ordering attributes by partition cardinality, using pairwise statistics in a Partition Cardinality Matrix to tighten bounds, and a global scheduler to explore promising branches first. Experiments on over 40 datasets show that SDP is much faster and uses less memory than exhaustive methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。