Structure of closures in relational schemas with join and functional dependencies

Translations of relational schemas are extended to the set of functional and join dependencies. A basic theorem on the representation of the closure of an attribute subset is proved.Translated from Kibernetika, No. 5, pp. 18–26, September–October, 1990.     

Ordered functional dependencies in relational databases

We extend the relational data model to incorporate linear orderings into data domains, which we call the ordered relational model. The conventional Functional Dependencies (FDs) are examined in the context of ordered relational databases by using the notion of System Ordering Independence (SOI), which refers to the desirable scenario that the ordering of tuples in a relation is independent of the implementation of the underlying DBMS. We also extend Armstrong's axiom system for FDs to object relations, which are a subclass of ordered relations that allow us to view tuples as objects. We formally define Ordered Functional Dependencies (OFDs) for the extended model by means of two possible extensions of domains, pointwise-orderings and lexicographical orderings. We first present a sound and complete axiom system for OFDs in the case of pointwise-orderings and then establish a sound and complete set of chase rules for OFDs in the case of lexicographical orderings. Our main result shows that the implication problems for both cases of OFDs are decidable, and that it is linear time for the case of pointwise-orderings.     

Discovering functional and inclusion dependencies in relational databases

We consider the problem of discovering the functional and inclusion dependencies that a given database instance satisfies. This technique is used in a database design tool that uses example databases to give feedback to the designer. If the examples show deficiencies in the design, the designer can directly modify the examples. the tool then infers new dependencies and the database schema can be modified, if necessary. the discovery of the functional and inclusion dependencies can also be used in analyzing an existing database. the problem of inferring functional dependencies has several connections to other topics in knowledge discovery and machine learning. In this article we discuss the use of examples in the design of databases, and give an overview of the complexity results and algorithms that have been developed for this problem. © 1992 John Wiley & Sons, Inc.     

Membership problems for data dependencies in relational expressions

In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied).Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E.Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in $\text{R}{}_1\text{???R}{}_{\mathrm{s}}$, where R₁,…,R_s are relation schemes with FDs and MVDs, and $\text{R}{}_{\mathrm{i}}\text{?R}{}_{\mathrm{j}}$ is the natural join of R_i and R_j.     

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.     

Representation of functional dependencies in relational databases using linear graphs

Functional dependencies in relational databases are investigated. Eight binary relations, viz., (1) dependency relation, (2) equipotence relation, (3) dissidence relation, (4) completion relation, and dual relations of each of them are described. Any one of these eight relations can be used to represent the functional dependencies in a database. Results from linear graph theory are found helpful in obtaining these representations. The dependency relation directly gives the functional dependencies. The equipotence relation specifies the dependencies in terms of attribute sets which functionally determine each other. The dissidence relation specifies the dependencies in terms of saturated sets in a very indirect way. Completion relation represents the functional dependencies as a function, the range of which turns out to be a lattice. Depletion relation which is the dual of the completion relation can also represent functional dependencies and similarly can the duals of dependency, equipotence, and dissidence relations. The class of depleted sets, which is the dual of saturated sets, is defined and used in the study of depletion relations.     

Another view of functional and multivalued dependencies in the relational database model

In this paper, pseudo-functional and pseudo-multivalued dependencies are introduced. They are shown to be isomorphic with functional and multivalued dependencies, i.e., they behave in the same way with respect to implication. This formalism leads in a very natural way to a rather efficient algorithm for the inference of functional and multivalued dependencies. Some applications to acyclic join dependencies are discussed.     

新的贝叶斯网络结构学习方法

贝叶斯网络是一种将贝叶斯概率方法和有向无环图的网络拓扑结构有机结合的表示模型,它描述了数据项及数据项之间的非线性依赖关系.报告了贝叶斯网络研究的现状,并针对传统算法需要主观规定网络中结点顺序的缺点,提出了一个新的可以在无约束条件下,根据观测得到的训练样本集的概率关系,自动完成学习贝叶斯网络结构的新方法.     

具有丢失数据的贝叶斯网络结构学习算法

学习具有丢失数据的贝叶斯网络结构主要采用结合 EM 算法的打分一搜索方法,其效率和可靠性比较低.针对此问题建立一个新的具有丢失数据的贝叶斯网络结构学习算法.该方法首先用 Kullback-Leibler(KL)散度来表示同一结点的各个案例之间的相似程度,然后根据 Gibbs 取样来得出丢失数据的取值.最后,用启发式搜索完成贝叶斯网络结构的学习.该方法能够有效避免标准 Gibbs 取样的指数复杂性问题和现有学习方法存在的主要问题.     

Constructing structure maps of multiple on-line texts

We propose that in many contexts of text use, people need to consult a mental representation of the mapping between the content of documents and their structure. We report three experiments that investigate the construction and use of such ‘structure maps.’ In each experiment people read multiple on-line texts on the same topic, and then searched for specific pieces of information in those texts. Search performance was compared with people who had not read the texts. People who had read multiple texts were, to some extent, able to recall where information was in the texts as shown by the locations in which they first searched (Experiments 1 and 2) or the number of pages opened during a search (Experiment 3). We also found that readers of multiple texts were able to find facts in those texts faster than were people who had not read the texts, and that this speedup was not a simple effect of faster reading while scanning for facts (Experiments 1 and 2) or of greater familiarity with the general topic (Experiment 3). These incidental effects of reading occurred whether or not participants were warned before reading that they would have subsequently to search the texts and were not compromised by transformations in the appearance of text (double column to single column) that disrupted the positions of facts on pages (Experiment 2). We conclude that readers spontaneously construct structure maps of multiple electronic texts, even when their reading goal stresses abstraction of meaning across sources. Structure maps likely play a vital role in many aspects of text use, such as re-reading and knowledge updating, so that their support is an important consideration in the design of on-line texts.     

A note on approximation measures for multi-valued dependencies in relational databases

We consider the problem of defining a normalized approximation measure for multi-valued dependencies in relational database theory. An approximation measure is a function mapping relation instances to real numbers. The number to which an instance is mapped, intuitively, describes the strength of the dependency in that instance. A normalized approximation measure for functional dependencies has been proposed previously: the minimum number of tuples that need be removed for the functional dependency to hold divided by the total number of tuples. This leads naturally to a normalized measure for multi-valued dependencies: the minimum number of tuples that need be removed for the multi-valued dependency to hold divided by the total number of tuples.The measure for functional dependencies can be computed efficiently, O(|r|log(|r|)) where |r| is the relation instance. However, we show that an efficient algorithm for computing the analogous measure for multi-valued dependencies is not likely to exist. A polynomial time algorithm for computing the measure would lead to a polynomial time algorithm for an NP-complete problem (proven by a reduction from the maximum edge biclique problem in graph theory). Hence, we argue that it is not a good measure. We propose an alternate measure based on the lossless join characterization of multi-valued dependencies. This measure is efficiently computable, O(|r|²).     

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’.     

Data dependencies in extended possibility‐based fuzzy relational databases

Based on the semantic equivalence degree the formal definitions of fuzzy functional dependencies (FFDs) and fuzzy multivalued dependencies (FMVDs) are first introduced to the fuzzy relational databases, where fuzziness of data appears in attribute values in the form of possibility attributions, as well as resemblance relations in attribute domain elements, called extended possibility‐based fuzzy relational databases. A set of inference rules for FFDs and FMVDs is then proposed. It is shown that FFDs and FMVDs are consistent and the inference rules are sound and complete, just as Armstrong's axioms for classic cases. © 2002 Wiley Periodicals, Inc.     

基于结构继承的贝叶斯网结构学习优化设计

采用遗传算法建立贝叶斯网络的优化学习结构,一直是贝叶斯网络研究倍受关注的课题.传统遗传算法的个体设计存在需要反复进行无环性检验的问题,降低了进化效率.针对这个问题,提出一种新的个体编码方式.考虑到进化过程中家族得分的可继承性,提出基于家族继承的结构评分改进算法,进而设计相应的改进遗传算法.实验结果表明,改进算法在BN建网精度与效率上都得到明显提升.     

The max-min hill-climbing Bayesian network structure learning algorithm

We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc_paper/mmhc_index.html. Editor: Andrew W. Moore     

Efficient and effective Bayesian network local structure learning

In this paper, we propose a more efficient Bayesian network structure learning algorithm under the framework of score based local learning (SLL). Our algorithm significantly improves computational efficiency by restricting the neighbors of each variable to a small subset of candidates and storing necessary information to uncover the spouses, at the same time guaranteeing to find the optimal neighbor set in the same sense as SLL. The algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results testify its improved speed without loss of quality in the learned structures.     

具有传递变量的动态贝叶斯网络结构学习

针对现有学习方法对完全时间不对称数据的动态贝叶斯网络学习不具有实用性,提出一种借助传递变量进行完全时间不对称数据的动态贝叶斯网络结构学习方法.首先进行相邻时间片间的传递变量序列学习;然后,基于节点排序和局部打分一搜索,进行动态贝叶斯网络局部结构学习;最后通过时序扩展得到整个动态贝叶斯网络结构.     

A case study in mapping conceptual designs to object‐relational schemas

The recent emergence of object‐relational technology into the commercial database market has caused new challenges for the implementation of conceptual database designs. This paper presents our experience with using the Oracle 8 object‐relational data model in the implementation of an engineering application described using the EXPRESS conceptual modeling language. EXPRESS is part of the engineering community's Standard for the Exchange of Product Data and can be characterized as a structurally object‐oriented modeling language, supporting the notion of entities, entity hierarchies, complex constraints on entity hierarchies, relationships and inverse relationships between entities, and user‐defined types. As a result, EXPRESS provides an excellent framework for studying the mapping of conceptual modeling concepts into an object‐relational model. In this paper, we describe the way in which the features of EXPRESS can be mapped into object‐relational features such as object tables, object references, and nested tables. We also describe the manner in which features such as member functions on object types, triggers, and stored procedures can be used to support the implementation of constraints associated with a conceptual schema. Although the mappings presented are specific to EXPRESS and Oracle 8, the mappings are generalizable to conceptual modeling languages and object‐relational models with similar features. Our work defines how traditional mapping concepts must be revised in order to make adequate use of the features now found in object‐relational models. As part of this paper, we also compare our mapping approach using Oracle 8 to mapping issues for the PostgreSQL object‐relational model and the Objectivity/DB object‐oriented data model. Copyright © 2000 John Wiley & Sons, Ltd.     

Graphical normal forms based on root dependencies in relational data base systems

Normal forms and dependencies are an area of great current interest in the design of relational data bases. Only a subclass, namely, root dependencies and the normal forms based on them, are of direct interest to the data base designer. Dependencies outside this subclass do not have clear cut semantics and may in the long run prove to be of theoretical interest only. We have proposed the fifth normal form (5NF) to control the pattern of codependancy, the highest known root dependency. We have also shown a strong parallel between root dependencies and their normal forms and a family of hypergraphs calledS-diagrams. Graphical normal forms, based onS-diagrams have been proposed and their equivalence to conventional normal forms proved.This work was supported in part by the Science and Engineering Research Board Grant Number 214–7248.