Extending Dependencies with Conditions
Extending Dependencies with Conditions
复制标题
DOI：
--
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Loreto Bravo;W. Fan;Shuai Ma
中科院分区：
文献类型：
--
作者：
Loreto Bravo;W. Fan;Shuai Ma
本文介绍了一类条件包含依赖性（CIND），该依赖关系通过执行语义相关数据值的绑定来扩展传统的包含依赖关系（IND）。我们表明，CIND不仅在数据清洁中很有用，而且在上下文模式匹配中也很有用[7]。为了有效利用Cind在实践中，通常有必要为它们推理。最重要的静态分析问题涉及一致性，以确定一组给定的cinds是否有冲突。另一个问题涉及含义，即确定一组Cind是否需要另一个CIND。我们对CIND的静态分析进行了全面处理，并表明Cinds保留了传统IND的最不错的特性：（a）Cinds始终是一致的； （b）cinds是有限的公理，即，存在一个声音和完整的推理系统，以暗示cinds； （c）Cinds的含义问题具有与传统的同行相同的复杂性，即Pspace-Complete，如果没有有限域的属性；但这在一般设置中是exptime complete。此外，我们研究了CIND和条件功能依赖性（CFD）之间的相互作用，这是[9]中提出的功能依赖性的扩展。我们表明，CIND和CFD的组合的一致性问题是不可决定的。鉴于不确定性，我们为CFD和CIND的一致性分析提供了启发式算法，并在实验上验证了我们算法的有效性和效率。
This paper introduces a class of conditional inclusion dependencies (CINDs), which extends traditional inclusion dependencies (INDs) by enforcing bindings of semantically related data values. We show that CINDs are useful not only in data cleaning, but are also in contextual schema matching [7]. To make effective use of CINDs in practice, it is often necessary to reason about them. The most important static analysis issue concerns consistency, to determine whether or not a given set of CINDs has conflicts. Another issue concerns implication, i.e., deciding whether a set of CINDs entails another CIND. We give a full treatment of the static analyses of CINDs, and show that CINDs retain most nice properties of traditional INDs: (a) CINDs are always consistent; (b) CINDs are finitely axiomatizable, i.e., there exists a sound and complete inference system for implication of CINDs; and (c) the implication problem for CINDs has the same complexity as its traditional counterpart, namely, PSPACE-complete, in the absence of attributes with a finite domain; but it is EXPTIME-complete in the general setting. In addition, we investigate the interaction between CINDs and conditional functional dependencies (CFDs), an extension of functional dependencies proposed in [9]. We show that the consistency problem for the combination of CINDs and CFDs becomes undecidable. In light of the undecidability, we provide heuristic algorithms for the consistency analysis of CFDs and CINDs, and experimentally verify the effectiveness and efficiency of our algorithms.