On learning multivalued dependencies with queries

Data dependencies play an important role in the design of relational databases. There is a strong connection between dependencies and some fragments of the propositional logic. In particular, functional dependencies are closely related to Horn formulas. Also, multivalued dependencies are characterized in terms of multivalued formulas. It is known that both Horn formulas and sets of functional dependencies are learnable in the exact model of learning with queries. Here we present an algorithm that learns a non-trivial subclass of multivalued formulas using membership and equivalence queries. Furthermore, a slight modification of the algorithm allows us to learn the corresponding subclass of multivalued dependencies.     

Negative results on learning multivalued dependencies with queries

Data dependencies are useful to design relational databases. There is a strong connection between dependencies and some fragments of the propositional logic. In particular, functional dependencies are closely related to Horn formulas. Also, multivalued dependencies are characterized in terms of multivalued formulas. It is known that both Horn formulas and sets of functional dependencies are learnable in the exact model of learning with queries. Here we proof that neither multivalued formulas nor multivalued dependencies can be learned using only membership queries or only equivalence queries.     

Mining frequent conjunctive queries in relational databases through dependency discovery

We present an approach for mining frequent conjunctive in arbitrary relational databases. Our pattern class is the simple, but appealing subclass of simple conjunctive queries. Our algorithm, called Conqueror $^+$ , is capable of detecting previously unknown functional and inclusion dependencies that hold on the database relations as well as on joins of relations. These newly detected dependencies are then used to prune redundant queries. We propose an efficient database-oriented implementation of our algorithm using SQL and provide several promising experimental results.     

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.     

Compact scheme forests in nested normal form

In the context of data base design for nested relational structures, update anomalies can be avoided if the nested scheme forest composed of scheme trees is in nested normal form (NNF) with respect to the associated set of data dependencies. In practice, minimizing the number of normal scheme trees in the nested scheme forest, which is in NNF, will also be an important design goal. This is because the number of computationally expensive join operations that are required in order to answer a given query is related to the number of normal scheme trees that must be used in the query expression.

We prove that the problem of finding a succinct NNF scheme forest is NP-complete for a subclass of the class of split-free sets of multivalued dependencies.     

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.     

时态函数依赖多值依赖混合集的成员籍问题研究

对于TFD和TMVD混合集约束的时态模式来说，由于多时间粒度的使用使成员籍问题的解决变得更加复杂．由于成员籍问题的解决对设计有效的模式分解算法必不可少，由此定义了时态类型集的强封闭集、属性集的有限闭包、属性集在给定时态类型上的有限依赖基、属性集的有限依赖基及特殊有限依赖基等概念，给出了求属性集的有限闭包、有限依赖基和特殊有限依赖基、时态混合集成员籍问题的算法，并对算法的可终止性、正确性进行了证明，对时间复杂性进行了分析，     

Functional and multivalued dependencies in nested databases generated by record and list constructor

The impact of the list constructor on two important classes of relational dependencies is investigated. Lists represent an inevitable data structure whenever order matters and data is allowed to occur repeatedly. The list constructor is therefore supported by many advanced data models such as genomic sequence, deductive and object-oriented data models including XML. The article proposes finite axiomatisations of functional, multivalued and both functional and multivalued dependencies in nested databases supporting record and list constructor. In order to capture different data models at a time, an abstract algebraic approach based on nested attributes is taken. The presence of the list constructor calls for a new inference rule which allows to infer non-trivial functional dependencies from multivalued dependencies. Further differences to the relational theory become apparent when the independence of the inference rules is investigated. The extension of the relational theory to nested databases allows to specify more real-world constraints and increases therefore the number of application domains. * Results of this article were partly presented at the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS), Vienna, Austria, 2004 [58], and the 23rd International Symposium on Principles of Database Systems (PODS), Paris, France, 2004 [54]. ** Sebastian Link was supported by Marsden Funding, Royal Society of New Zealand.     

Decomposition of object-oriented database schemas

We specify a data model with object-oriented and logic-oriented features. The model is based on F-logic. For this model, we study a decomposition of a class, the counterpart to the well-known decomposition of a relation scheme under functional dependencies. For this decomposition of a class, the transformation pivoting is used. Pivoting transplants some attributes of the class to a newly generated class. This new class is a subclass of the result class of the so-called pivot attribute. The pivot attribute maintains the link between the original class and the new subclass. We identify the conditions under which input and output of pivoting are equivalent. Additionally, we show under which conditions a schema with functional dependencies can be recursively transformed into an equivalent one without non-key functional dependencies.     

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.     

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.     

A Logical Design Method for Relational Databases Based on Generalization and Aggregation Semantics

In this paper,a series of esign methods for relational databases based on generalization and aggregation semantics is set up.The relationship between a class and its subclass s considered as a scheme constraint.The concept of inheritance dependencies,which describes the multiple inheritance among schemes, is presented in the paper.It is shown that the inference rules for inheritance dependencies are sound and complete.Furthermore,a series of results about the closure of inheritance dependencies and the minimal set of inheritance dependencies,which are analogues to functional dependencies,is obtained.In order to describe the aggregation semantices,the concept of aggregation dependencies is given.It is easy to implement these constraints under relational database management systems.     

On Polynomial-Time Learnability in the Limit of Strictly Deterministic Automata

This paper deals with the polynomial-time learnability of a language class in the limit from positive data, and discusses the learning problem of a subclass of deterministic finite automata (DFAs), called strictly deterministic automata (SDAs), in the framework of learning in the limit from positive data. We first discuss the difficulty of Pitt's definition in the framework of learning in the limit from positive data, by showing that any class of languages with an infinite descending chain property is not polynomial-time learnable in the limit from positive data. We then propose new definitions for polynomial-time learnability in the limit from positive data. We show in our new definitions that the class of SDAs is iteratively, consistently polynomial-time learnable in the limit from positive data. In particular, we present a learning algorithm that learns any SDA M in the limit from positive data, satisfying the properties that (i) the time for updating a conjecture is at most O(lm), (ii) the number of implicit prediction errors is at most O(ln), where l is the maximum length of all positive data provided, m is the alphabet size of M and n is the size of M, (iii) each conjecture is computed from only the previous conjecture and the current example, and (iv) at any stage the conjecture is consistent with the sample set seen so far. This is in marked contrast to the fact that the class of DFAs is neither learnable in the limit from positive data nor polynomial-time learnable in the limit.     

An Infornation-Theoretic Analysis of Relational Databases—Part I: Data Dependencies and Information Metric

Database design is based on the concept of data dependency, which is the interrelationship between data contained in various sets of attributes. In particular, functional, multivalued and acyclic join, dependencies play an essential role in the design of database schemas. The basic definition of an information metric and how this notion can be used in relational database are discussed in this paper. We use Shannon entropy as an information metric to quantify the information associated with a set of attributes. Thus, we prove that data dependencies can be formulated in terms of entropies. These formulas make the numerical computation and testing of data dependencies feasible. Among the different types of data dependencies, the acyclic join dependency is most important to the design of a relational database schema. The acyclic join dependency, with multivalued dependency as a special case, impose a constraint on the information-preserving decomposition of a relation. It is interesting that this constraint on a relation is similar to Gibbs' condition for separating physical systems in statistical mechanics. They both assert that entropy is preserved during the decomposition process. That is, the entropies of the corresponding set of attributes must satisfy the inclusion–exclusion identity.     

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     

Learning Read-Constant Polynomials of Constant Degree Modulo Composites

Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC⁰. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.     

Charting the completeness frontier of inference systems for multivalued dependencies

The implication of multivalued dependencies in relational databases has originally been defined in the context of some fixed finite universe. While axiomatisability and implication problems have been intensely studied with respect to this notion almost no research has been devoted towards the alternative notion of implication in which the underlying universe of attributes is left undetermined. Based on a set of common inference rules we establish all axiomatisations in undetermined universes, and all axiomatisations in fixed universes that indicate the role of the complementation rule as a means of database normalisation. This characterises the expressiveness of several incomplete sets of inference rules. We also establish relationships between axiomatisations in fixed and undetermined universes, and study the time complexity of the implication problem in undetermined universes. The results of this paper establish a foundation for reasoning about multivalued dependencies without the assumption of a fixed underlying universe.     

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

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

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     

一个多时间粒度下时态函数依赖的有限属性闭包算法

为了有效地进行时态数据库设计,支持多时间粒度的时态函数依赖(TFDs)被用于时态模式的规范化．时态模式规范化所要解决的一个关键问题是求解时态函数依赖的有限属性闭包问题．由于多时间粒度的使用,使得有限属性闭包问题变得非常复杂．实际上,TFDs与传统的函数依赖(FDs)之间存在着密切的联系．通过分析这些联系和封闭时态类型集的特性,利用传统FDs的相关算法提出一个有效的求解有限属性闭包的算法．通过分析和与相关算法的实验比较,该算法更加有效．