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.     

基于语义贴近度的模糊数据依赖

本文基于语义贴近度的概念给出了模糊函数依赖（ＦＦＤ）、模糊多值依赖（ＦＭＶＤ）和模型联接依赖（ＦＪＤ）的定义。本文得到一组类似于Ａｒｍｓｔｒｏｎｇ公理的正确、完备的ＦＦＤ和ＦＭＶＤ的推理规则。进一步，我们证明了经典数据依赖满足模糊数据依赖的定义，ＦＦＤ是ＦＭＶＤ的特例，而ＦＭＶＤ又是ＦＪＤ的特例。     

The integrity constraints for similarity-based fuzzy relational databases

This paper first introduces a new definition for the conformance of tuples existing in a similarity-based fuzzy database relation. Then the formal definitions of fuzzy functional and multivalued dependencies are given on the basis of the conformance values presented here. These dependencies are defined to represent relationships between domains of the same relation that exist. The definitions of the fuzzy dependencies presented in this study allow a sound and complete set of inference rules. In this paper, we include examples to demonstrate how the integrity constraints imposed by these dependencies are enforced whenever a tuple is to be inserted or to be modified in a fuzzy database relation. © 1998 John Wiley & Sons, Inc.     

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.     

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.     

Learning Sets of Antecedent-restricted Functional and Multivalued Dependencies with Queries

Identifying dependencies that hold in relational databases is essential to produce good databases designs. In particular, functional and multivalued dependencies are used to obtain relation schemes that satisfy the 4th normal form, a property that is considered satisfactory for most applications. It is known that the class of sets of functional dependencies is learnable in the exact model of learning with queries. Also a subclass of multivalued dependencies, the class of consequent-restricted multivalued dependencies, has been shown to be learnable in this model. In this paper, we present an algorithm that learns a class that contains sets of both functional and multivalued dependencies under some restrictions imposed on the antecedents of dependencies. We also show, as a by-product, an algorithm that learns a non-trivial subclass of 2-quasi Horn formulas, closely related to the class just mentioned.     

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.     

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.     

On interpreting and inferring propositional formulas of data dependencies in a relational database

This paper concerns generally the satisfaction and the inference problem involving functional and/or multivalued dependencies in a relational database. In particular, two independent aids in solving an inference problem, concerning the logical counterparts of functional as well as multivalued dependencies, are introduced. The first aid is provided by establishing a pair of complementary inequivalence and equivalence theorems between the propositional formula corresponding to the difference, U-X, in set theory and the propositional formula not(X) where U is a relation scheme and X is a subset of U. By applying these theorems, correctness of solving an inference problem is assured. The second aid is the application of a Venn diagram for simplifying a propositional formula involving conjunctions, differences, etc., for solving an inference problem. A guideline for constructing simplified Venn diagrams is also given and discussed.     

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.     

Data Dependencies in Database with Incomplete Information

To get more meaning of incomplete information,a predicate way is proposed torepresent the nulls.The concepts of functional and multivalued dependencies areextended in the environment which allows nulls in a database relation.The inferencerules which can be applied to the extended dependencies are investigated.Finally it isshown that the rules are complete for the family of extended functional and multivalueddependencies.     

模糊多值依赖的深入探讨

本文探讨了模糊多值依赖的性质,对单一模糊多值依赖环境下的推导规则进行了补充;给出了求依赖基的算法;讨论了在模糊函数依赖、模糊多值依赖混合作用下的推导公理系统;介绍了模糊嵌入多值依赖的概念及公理系统。     

Functional dependencies with null values, fuzzy values, and crispvalues

Based on the concepts of the semantic proximity, we present a definition of the fuzzy functional dependency, We show that the inference rules for fuzzy functional dependencies, which are the same as Armstrong's axioms for the crisp case, are correct and complete. We also show that dependent constraints with dull values constitute a lattice. Functional dependencies in classical relational databases and null functional dependencies can be viewed as a special case of fuzzy functional dependencies. By applying the unified functional dependencies to the relational database design, we can represent the data with fuzzy values, null values and crisp values under relational database management systems, By using fuzzy functional dependencies, we can compress the range of a fuzzy value and make this fuzzy value “clearer”     

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     

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.     

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.     

A simple characterization of database dependency implication

A simple and elegant set-theoretic characterization is given as to when a given set of functional and multivalued dependencies logically implies a given functional or multivalued dependency. A simple proof of the characterization is given which makes use of a result of Sagiv, Delobel, Parker, and Fagin (1981).     

基于XML Schema的XML强多值依赖的推理规则集

XML强多值依赖的推理规则集问题是解决不完全信息环境下XML数据依赖蕴涵问题的基础,是不完全信息环境下XML模式设计理论的关键问题之一。提出了XML Schema、符合XML Schema的不完全XML文档树等概念;基于子树信息等价和子树信息相容的概念提出了XML强多值依赖的定义及性质;给出了相应的推理规则集,并对其正确性和完备性进行了证明。研究成果为不完全信息环境下存在XSMVD的XML Schema设计奠定了基础。