An Information-Theoretic Analysis of Relational Databases—Part II: Information Structures of Database Schemas

The structural properties of acyclic database schemas, especially the interrelationships between acyclic join dependencies and multivalued dependencies, are examined in this paper. The intersection closure of a database schema is a semilattice, which is usually represented by Hasse diagram in algebra. The Hasse diagram of a schema is analogous to the Bachman diagram of a network model. Based on the topological structures of Hasse diagrams, the acyclic join dependency is proved to be equivalent to a set of conflict-free multivalued dependencies. Furthermore, we show that if the Hasse diagram is loop free, then the corresponding set of multivalued dependencies is also contention-free. This result is consistent with previous results derived from the Bachman diagram.     

An analysis of multivalued and join dependencies based on the entity-relationship approach

In this paper, we show that multivalued dependencies and join dependencies are not very viable for certain cases of relational database design; they are sometimes difficult to be identified; they are relation sensitive; and we are unable to talk about these types of dependencies without referring to some specific relation. We also show that the entity-relationship approach can be used for relational database design without any of the above mentioned undesirable properties of multivalued dependencies and join dependencies.     

Constructing the Bayesian network structure from dependencies implied in multiple relational schemas

Relational models are the most common representation of structured data, and acyclic database theory is important in relational databases. In this paper, we propose the method for constructing the Bayesian network structure from dependencies implied in multiple relational schemas. Based on the acyclic database theory and its relationships with probabilistic networks, we are to construct the Bayesian network structure starting from implied independence information instead of mining database instances. We first give the method to find the maximum harmoniousness subset for the multi-valued dependencies on an acyclic schema, and thus the most information of conditional independencies can be retained. Further, aiming at multi-relational environments, we discuss the properties of join graphs of multiple 3NF database schemas, and thus the dependencies between separate relational schemas can be obtained. In addition, on the given cyclic join dependency, the transformation from cyclic to acyclic database schemas is proposed by virtue of finding a minimal acyclic augmentation. An applied example shows that our proposed methods are feasible.     

The Relational Structure of Belief Networks

This paper demonstrates the relational structure of belief networks by establishing an extended relational data model which can be applied to both belief networks and relational applications. It is demonstrated that a Markov network can be represented as a generalized acyclic join dependency (GAJD) which is equivalent to a set of conflict-free generalized multivalued dependencies (GMVDs). A Markov network can also be characterized by an entropy function, which greatly facilitates the manipulation of GMVDs. These results are extensions of results established in relational theory. It is shown that there exists a complete set of inference rules for the GMVDs. This result is important from a probabilistic perspective. All the above results explicitly demonstrate that there is a unified model for relational database and probabilistic reasoning systems. This is not only important from a theoretical point of view in that one model has been developed for a number of domains, but also from a practical point of view in that one system can be implemented for both domains. This implemented system can take advantage of the performance enhancing techniques developed in both fields. Thereby, this paper serves as a theoretical foundation for harmonizing these two important information domains.     

XML DTD的一种范式

研究了XML DTD的规范化问题。由于DTD在设计上存在不足之处，DTD中可能包含类似于关系数据库模式中存在的异常依赖，从而导致XML文档包含冗余的数据和各种操作异常。提出了关于DTD的多值依赖的概念，然后基于多值依赖的概念，提出了一种XML的范式XNF，并且用DTD的关系表示形式给出了关于DTD的无损联接分解的概念。最后给出了把DTD无损联接地分解成XNF的一种算法。     

A universal formalism to express decompositions,functional dependencies and other constraints in a relational database

A general formalism, called the general dependencies, is presented. The multivalued, mutual, join and functional dependencies can be expressed in this formalism. Some properties of general dependencies are stated and their influence on the decompositionand the partial decomposition of a relation is studied.The class of general dependencies is compared with other classes of dependencies.It is proved that every set of functional dependencies can be expressed by a single general dependency. The same property holds for the multivalued dependencies.Finally the concept of functional dependency is generalized.     

Normalization and lossless join decomposition of similarity‐based fuzzy relational databases

Fuzzy relational database models generalize the classical relational database model by allowing uncertain and imprecise information to be represented and manipulated. In this article, we introduce fuzzy extensions of the normal forms for the similarity‐based fuzzy relational database model. Within this framework of fuzzy data representation, similarity, conformance of tuples, the concept of fuzzy functional dependencies, and partial fuzzy functional dependencies are utilized to define the fuzzy key notion, transitive closures, and the fuzzy normal forms. Algorithms for dependency preserving and lossless join decompositions of fuzzy relations are also given. We include examples to show how normalization, dependency preserving, and lossless join decomposition based on the fuzzy functional dependencies of fuzzy relation are done and applied to some real‐life applications. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 885–917, 2004.     

Characterizing the MVDs That Hold in a Connected Subtree of a Join Tree: A Correction

Given an acyclic database scheme R and a connected subtree T of a join tree for R, this paper provides a characterization of the set of multivalued dependencies (MVDs) that hold over T with respect to infinR, the corresponding join dependency (JD) of R. This result corrects an error in one of my previous papers "A Comparative Study of Various Nested Normal Forms," which was published in vol. 14, no. 2, pp. 369-385, Mar./Apr. 2002.     

Characterisations of multivalued dependency implication over undetermined universes

In relational databases the original definition of a multivalued dependency is dependent on the underlying relation schema. In this context, the implication of multivalued dependencies has been characterised from multiple perspectives. Logically, it is equivalent to the logical implication of certain material implications in Boolean propositional logic. Proof-theoretically, the Chase procedure offers a convenient tool to decide implication. And algebraically, the implication can be characterised by the notion of closed attribute sets with respect to multivalued dependencies. The assumption of having a fixed underlying relation schema is not always feasible in practice, and also distinguishes multivalued dependencies from other classes of data dependencies. In this paper, we establish logical, proof-theoretical and algebraic characterisations for Biskup?s notion of multivalued dependency implication over undetermined universes. That is, we unburden the current theory of the assumption of having a fixed underlying relation schema. From the perspective of probability theory this means that is unnecessary to fix the set of discrete probabilistic variables in order to utilise conditional independencies.     

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

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

具有多时间粒度的时态多值依赖及时态模式分解方法研究

一个好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异常.对于时态数据库,通过具有多时间粒度的时态函数依赖约束对时态数据库进行规范化已有大量研究.基于时态函数依赖和多值依赖理论提出了多时间粒度约束的时态多值依赖(TMVD)等概念,并给出了时态多值依赖的推理规则,对其有效性、完备性进行了证明.由于包含有限个TMVD的TMVD集通常蕴含着无限个TMVD,给出了TMVD的有限推理规则,对其有效性、完备性进行了证明.最后,基于时态多值依赖集提出了时态第四范式,并给出了时态模式的T4NF的无损分解算法,对算法的可终止性、正确性进行了证明,并对时间复杂度进行了分析.     

Constraint preserving and lossless database transformations

The dependency preserving and lossless join properties for relational database decomposition are generalized to the constraint preserving and lossless properties for mappings between database systems. The constraint preserving and lossless properties are investigated both for relational database normalization by decomposition and for relational database distribution by selection. The constraint preserving and lossless properties are also discussed for mappings between heterogeneous databases.     

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.     

对象类视图中蕴涵的依赖关系

本文研究关系模型中对象类视图关系模式的数据依赖问题。关系数据库中用一组表存放一个对象类的数据,并用视频实现对象类。本文分析该视图的列之间存在的函数依赖和多值依赖,并证明了类的所有单值和多值属性组成对象标识的多值依赖基。     

样本依赖与连接依赖的等价性

以抽象代数为工具,探索了全样本依赖与全连接依赖之间的关系.首先,分别在全样本依赖集和全连接依赖集上建立等价关系,这两种等价关系都将作用相同的依赖视为等价依赖. 然后证明了在这两个等价关系下的商集分别构成么半群,并且这两个么半群是同构的.这就等于证明了全样本依赖类本质上等同于全连接依赖类.最后给出了一个关于全无环连接依赖的有趣结果.有关结果可以在关系数据库的设计中发挥积极作用.     

模糊关系无损连接分解的实现及检验

本文基于一个模糊关系数据库系统的实验性原型FRDB1中定义的模糊关系,首先定义了模糊等价性,描述并验证了模糊函数依赖的理论,然后基于模糊关系代数和模糊等价性的附加约束条件实现了模糊关系的无损连接分解,最后证明了追踪算法检验模糊关系的无损连接分解。     

Appropriate inferences of data dependencies in relational databases

We study inference systems for the combined class of functional and full hierarchical dependencies in relational databases. Two notions of implication are considered: the original notion in which a dependency is implied by a given set of dependencies and the underlying set of attributes, and the alternative notion in which a dependency is implied by a given set of dependencies alone. The first main result establishes a finite axiomatisation for the original notion of implication which clarifies the role of the complementation rule in the combined setting. In fact, we identify inference systems that are appropriate in the following sense: full hierarchical dependencies can be inferred without use of the complementation rule at all or with a single application of the complementation rule at the final step of the inference only; and functional dependencies can be inferred without any application of the complementation rule. The second main result establishes a finite axiomatisation for the alternative notion of implication. We further show how inferences of full hierarchical dependencies can be simulated by inferences of multivalued dependencies, and vice versa. This enables us to apply both of our main results to the combined class of functional and multivalued dependencies. Furthermore, we establish a novel axiomatisation for the class of non-trivial functional dependencies.     

最小函数依赖集Fmin求解算法研究及实现

函数依赖反映了现实世界中数据的完整性约束,对关系数据库的分析和设计起着重要的作用。最小函数依赖集和模式规范化是规范化理论和模式分解中的两个最重要概念。研究并实现了最小函数依赖集的求解算法。     

Some results on the deductive structure of join dependencies

Among the many different data dependencies defined, the so-called join dependencies play a central role, since they explicitly capture lossless join properties for relation schemes.In this paper we state some inference rules for join dependencies and embedded join dependencies. A set of two rules is shown to be complete for monadic join dependency inferences (inferences from a single dependency). Furthermore, it is shown that there is no finite set of inference rules that is complete for embedded join dependencies.     

Controlling FD and MVD inferences in multilevel relational databasesystems

The authors investigate the inference problems due to functional dependencies (FD) and multivalued dependencies (MVD) in a multilevel relational database (MDB) with attribute and record classification schemes, respectively. The set of functional dependencies to be taken into account in order to prevent FD-compromises is determined. It is proven that incurring minimum information loss to prevent compromises is an NP-complete problem. An exact algorithm to adjust the attribute levels so that no compromise due to functional dependencies occurs is given. Some necessary and sufficient conditions for MVD-compromises are presented. The set of MVDs to be taken into account for controlling inferences is determined. An algorithm to prevent MVD-compromises in a relation with conflict-free MVDs is given