An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.     

XML多值依赖及其消除冗余模式的算法

从消除XML文档内数据冗余的角度出发研究了文档的规范化问题.首先引入XML上的数据冗余及其消除处理示例,同时基于函数依赖,提出了规范化的DTD概念和XML DTD 规范化处理规则;其次通过XML多值依赖的定义,给出用于消除冗余模式的算法;最后给出用于XML模式及其消除冗余模式的算法.该算法相应于其他XML模式的研究,在算法产生的层次模式中,完全MVD和嵌入MVD的集合由给出的MVD集合导出;并且产生的XML模式具有消除冗余模式和满足无损连接的特性.     

用于XML模式和DTD规范化设计的层次模式设计

XML模式和DTD(document type definition)规范化设计是给出一个很好地表示数据间依赖关系并消除了冗余的XML模式或DTD的集合.目前在这一方面开展的研究还不多,而且才刚起步.Provost提出将关系数据库理论应用于XML模式规范化设计的思想,这一思想还没有付诸实施.在Provost思想的基础上给出用于XML模式和DTD规范化设计的层次模式设计的算法.首先分析了基于Provost思想的层次分解;然后给出用于消除冗余模式的分解树设计算法;最后给出用于XML模式和DTD规范化设计的层次     

Discovering branching and fractional dependencies in databases

The discovery of dependencies between attributes in databases is an important problem in data mining, and can be applied to facilitate future decision-making. In the present paper some properties of the branching dependencies are examined. We define a minimal branching dependency and we propose an algorithm for finding all minimal branching dependencies between a given set of attributes and a given attribute in a relation of a database. Our examination of the branching dependencies is motivated by their application in a database storing realized sales of products. For example, finding out that arbitrary p products have totally attracted at most q new users can prove to be crucial in supporting the decision making.In addition, we also consider the fractional and the fractional branching dependencies. Some properties of these dependencies are examined. An algorithm for finding all fractional dependencies between a given set of attributes and a given attribute in a database relation is proposed. We examine the general case of an arbitrary relation, as well as a particular case where the problem of discovering the fractional dependencies is considerably simplified.     

On data dependency structures of relational databases

The properties of the set of all functional dependencies (which is defined to be FD sub-structure), derivable from a given set of functional dependencies (FD's) and multivalued dependencies (MVD's) for a relational database, are studied. A necessary and sufficient condition that a set of FD's is a cover for the FD sub-structure is proved, which can be tested for validity by an efficient algorithm. An algorithm of generating a cover for the FD substructure is presented. It can be shown, however, that in at least one instance, the number of FD's in the cover may actually increase more than exponentially as the number of MVD's increases.     

Query rewriting using views in the presence of functional and inclusion dependencies

Query rewriting using views is a technique for determining how a query may be answered using a given set of resources, which may include materialized views, cached results of previous queries, or queries answerable by other databases. The power of query rewriting can be considerably enhanced by taking into account integrity constraints that are known to hold on base relations. This paper describes an extension of query rewriting that utilizes inclusion dependencies to find rewritings of queries that would otherwise be overlooked. We describe a complete strategy for finding rewritings in the presence of inclusion dependencies and present a basic algorithm that implements that strategy. We also describe extensions to this algorithm when both inclusion and functional dependencies are considered.     

Impurity measures in databases

We introduce purity dependencies as generalizations of functional dependencies in relational databases starting from the notion of impurity measure. The impurity measure of a subset of a set relative to a partition of that set and the relative impurity of two partitions allow us to define the relative impurity of two attribute sets of a table of a relational database and to introduce purity dependencies. We discuss properties of these dependencies that generalize similar properties of functional dependencies and we highlight their relevance for approximate classifications. Finally, an algorithm that mines datasets for these dependencies is presented. Received: 4 July 2000 / 16 November 2001     

Losslessness and project-join constructibility in relational databases

Summary Checking a database scheme for the lossless join property with respect to a set, M, of multivalued dependencies (MVDs) is NP-hard. We prove that, for a class of MVDs that includes the set of projected full MVDs, this check can be performed in polynomial time. Even with a lossless database scheme and a consistent database, joining the set of relations in the database can take time and space that is exponential in the size of the relation finally obtained. Joining the set of relations of such a database can be performed in polynomial time if the database scheme is project-join constructible with respect to M. We prove that project-join constructibility, a stricter condition than the lossless join property, can be detected in a database scheme in polynomial time.     

Full hierarchical dependencies in fixed and undetermined universes

Full hierarchical dependencies (FHDs) constitute a large class of relational dependencies. A relation exhibits an FHD precisely when it is the natural join over at least two of its projections that all share the same join attributes. Therefore, FHDs generalise multivalued dependencies (MVDs) in which case the number of these projections is precisely two. The implication of FHDs has originally been defined in the context of some fixed finite universe. This paper identifies a sound and complete set of inference rules for the implication of FHDs. This axiomatisation is very reminiscent of that for MVDs. Then, an alternative notion of FHD implication is introduced in which the underlying set of attributes is left undetermined. The first main result establishes a finite axiomatisation for FHD implication in undetermined universes. It is then formally clarified that the complementation rule is only a mere means for database normalisation. In fact, the second main result establishes a finite axiomatisation for FHD implication in fixed universes which allows to infer FHDs either without using the complementation rule at all or only in the very last step of the inference. This also characterises the expressiveness of an incomplete set of inference rules in fixed universes. The results extend previous work on MVDs by Biskup.     

一个具有多时间粒度时态函数依赖集的成员籍算法

对于具有函数依赖（FDs)约束的传统关系数据库规范化理论来说，判定一个FD是否被给定FD集所逻辑蕴涵（即成员籍问题）是非常重要的，这有助于设计有效的模式分解算法，而对于具有时态函数依赖（TFDs)约束的时态模式来说，由于多时间粒度的使用使成员籍问题的解决变得更加复杂，由此讨论了时态类型的一些特性，并提出了有限决定集的概念，基于求得属性的有限决定集，对每一个元素的左部属性集是单一属性的TFD集给出了一个有效的成员籍算法和相关的正确性证明。     

一种发现函数依赖集的方法及应用

介绍了一种发现最小函数依赖集的方法.这种方法基于一致集的概念,根据一致集导出最大集及其补集,然后生成最小非平凡函数依赖集.通过使用带状划分数据库减少求一致集的运算次数,使用逐层求精的算法来计算最小非平凡函数依赖集的左部.其结果可用于数据库的重新组织和设计、属性约简、聚类、关联规则提取等知识发现工作中.     

A parallel algorithm for relational database normalization

The problem of database normalization in a parallel environment is examined. Generating relation schemes in third normal form is straightforward when given a set of functional dependencies that is a reduced cover. It is shown that a reduced cover for a set of functional dependencies can be produced in parallel. The correctness of the algorithm is based on two important theorems. it is demonstrated that the companion third normal form algorithm can be easily translated into a parallel version. The performance of the two algorithms is compared to the performance of their serial counterparts. The standard serial algorithms for computing minimal covers and synthesizing third normal form relations are presented. The parallel algorithms and their rationale are discussed     

基于模式图的规范化XML模式设计

在给定关系模式的属性集及其函数依赖最小覆盖集的基础上,提出一种基于模式图的规范化XML模式设计方法。定义了模式图,在模式图中增加了Keys的描述信息,给出由函数依赖集构造模式图的算法。该模式图独立于具体的XML模式语言,经分析证明,所设计的模式满足XNF。     

Functional dependencies among Boolean dependencies

In this paper, we consider functional dependencies among Boolean dependencies (BDs, for short). Armstrong relations are defined for BDs (called BD-Armstrong relations). For BDs, two necessary and sufficient conditions for the existence of BD-Armstrong relations are given. A necessary and sufficient condition for the existence of Armstrong relations for functional dependencies (FDs, for short) is given, which in some sense is more convenient than the condition given in [3]. We give an algorithm that solves the problem of deciding if two BDs imply the same set of functional dependencies. If the BDs are given in perfect disjunctive normal form, then the algorithm requires only polynomial time. Although Mannila and Räihä have shown that for some relations exponential time is needed for computing any cover of the set of FDs defined in this relation, as a consequence, we show that the problem of deciding if two relations satisfy the same set of FDs can be solved in polynomial time. Another consequence is a new correspondence of the families of functional dependencies to the families of Sperner systems. By this correspondence, the estimate of the number of databases given previously in [6] is improved. It is shown that there is a one-to-one correspondence between the closure of the FDs that hold in a BD and its so-calledbasic cover. As applications of basic covers, we obtain a representation of a key, the family of minimal keys and a representation of canonical covers.This research was supported by the Hungarian Foundation for Scientific Research, Grant Nos. OTKA 2575, 2149.     

A new method for computing fuzzy functional dependencies in relational database systems

In this paper, we present a new method for computing fuzzy functional dependencies between attributes in fuzzy relational database systems. The method is based on the use of fuzzy implications. A literature analysis has shown that there is no algorithm that would enable the identification of attribute relationships in fuzzy relational schemas. This fact was the motive for development a new methodology in the analysis of fuzzy functional dependencies over a given set of attributes. Solving this, not so new problem, is not only research challenge having theoretical importance, but it also has practical significance. Possible applications of the proposed methodology include GIS, data mining, information retrieval, reducing data redundancy in fuzzy relations through implementation of logical database model, estimation of missing values etc.     

Functional and embedded dependency inference: a data mining point of view

The issue of discovering functional dependencies from populated databases has received a great deal of attention because it is a key concern in database analysis. Such a capability is strongly required in database administration and design while being of great interest in other application fields such as query folding. Investigated for long years, the issue has been recently addressed in a novel and more efficient way by applying principles of data mining algorithms. The two algorithms fitting in such a trend are TANE and Dep-Miner. They strongly improve previous proposals. In this paper, we propose a new approach adopting a data mining point of view. We define a novel characterization of minimal functional dependencies. This formal framework is sound and simpler than related work. We introduce the new concept of free set for capturing source of functional dependencies. By using the concepts of closure and quasi-closure of attribute sets, targets of such dependencies are characterized. Our approach is enforced through the algorithm FUN which is particularly efficient since it is comparable or improves the two best operational solutions (according to our knowledge): TANE and Dep-Miner. It makes use of various optimization techniques and it can work on very large databases. Applying on real life or synthetic data more or less correlated, comparative experiments are performed in order to assess performance of FUN against TANE and Dep-Miner. Moreover, our approach also exhibits (without significant additional execution time) embedded functional dependencies, i.e. dependencies captured in any subset of the attribute set originally considered. Embedded dependencies capture a knowledge specially relevant in all fields where materialized data sets are managed (e.g. materialized views widely used in data warehouses).     

基于近似函数依赖的关系数据属性权重评估方法

在现实应用中,一些关系数据的规范化程度不高,往往存在数据冗余和不一致现象。为了有效评估此类数据 中的属性重要程度,提出了一种基于近似函数依赖的属性权重评估方法。该方法基于一致集的概念导出最大集,生成 最小非平凡函数依赖集,从而找出属性之间的近似函数依赖关系,进而求出近似候选码和近似关键字,在此基础上根 据属性支持度计算属性权重。实验结果和分析表明,提出的属性权重评估方法能够合理地获取关系数据中的属性重 要程度,算法具有较好的稳定性和较高的执行效率。     

粒计算支持的粗糙函数依赖的研究

利用粒计算方法对粗糙关系数据库（Rough Relational Database,RRDB）的粗糙函数依赖进行研究。首先提出了两种类型的粗糙函数依赖及粗糙相似关系的概念,分析了如何利用位模式表示粗糙关系的属性值,在此基础上给出了利用粒计算方法对粗糙关系的属性间的依赖关系的进行判定的算法,实验验证算法是有效可行的。     

Thorough investigation into “An improved algorithm based onsubset closures for synthesizing a relational databasescheme”

The paper describes a technical improvement of a synthesis algorithm for relational database scheme design, which was proposed by Yang et al. (1988). The improvement is based on the observation that the original algorithm may lose attributes in a decomposition in special cases, due to an insufficient handling of representatives of equivalence classes formed over a given set of functional dependencies. The paper then proposes a correction of the original algorithm in which this problem disappears