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.     

Approximate dependencies in database systems

Functional dependencies are the most commonly used approach for capturing real-word integrity constraints which are to be reflected in a database. There are, however, many useful kinds of constraints, especially approximate ones, that cannot be represented correctly by functional dependencies and therefore are enforced via programs which update the database, if they are enforced at all. This tends to make such constraints invisible since they are not an explicit part of the database, increasing maintenance problems and the likelihood of inconsistencies. We propose a new approach, cluster dependencies, as a way to enforce approximate dependencies. By treating equality as a fuzzy concept and defining appropriate similarity measures, it is possible to represent a broad range of approximate constraints directly in the database by storing and accessing cluster definitions. We discuss different interpretations of cluster dependencies and describe the additional data structures needed to enforce them. We also contrast them with an existing approach, fuzzy functional dependencies, which are much more limited in the kind of approximate constraints they can represent.     

Decomposition for a new kind of imprecise information system

In this paper, we first propose a new kind of imprecise information system, in which there exist conjunctions (∧’s), disjunctions (∨’s) or negations (¬’s). Second, this paper discusses the relation that only contains ∧’s based on relational database theory, and gives the syntactic and semantic interpretation for ∧ and the definitions of decomposition and composition and so on. Then, we prove that there exists a kind of decomposition such that if a relation satisfies some property then it can be decomposed into a group of classical relations (relations do not contain ∧) that satisfy a set of functional dependencies and the original relation can be synthesized from this group of classical relations. Meanwhile, this paper proves the soundness theorem and the completeness theorem for this decomposition. Consequently, a relation containing ∧’s can be equivalently transformed into a group of classical relations that satisfy a set of functional dependencies. Finally, we give the definition that a relation containing ∧’s satisfies a set of functional dependencies. Therefore, we can introduce other classical relational database theories to discuss this kind of relation.     

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”     

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.     

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.     

Weakly independent database schemes

Independent database schemes are best known to have constraints enforced globally by enforcing them locally in individual relations, and therefore are highly desirable in an updates-busy and distributed environment. However, independence excludes all database schemes with interrelational functional dependencies and therefore is too strong a condition. In this paper, a natural generalization of independent schemes along this line, called weakly independent schemes, is defined. A database scheme is weakly independent with respect to a set of embedded functional dependencies if the constraints can be enforced globally by enforcing local as well as interrelational functional dependencies. (a) A characterization of the weak independence and an exponential time test (in the number of functional dependencies) are presented. (b) Two polynomial time conditions are also presented, one is necessary and the other is sufficient for a database scheme to be weakly independent. (c) It is shown that a certain acyclicity of the database scheme implies weak independence. Extension to the case of embedded functional dependencies plus the join dependency is also considered. Received: 18 July 1991 / 28 September 1995     

Database Lexicography

This paper introduces database lexicography, a metadata analysis discipline that applies lexical graph theory to data design. Database lexicography proposes a formal design criterion for data dependencies, and it provides metrics to evaluate the conformance of designs to this criterion. It treats the data dictionary as a first class object encoding design concepts, and its benefits include identification of database dependency architecture; quantification of interdependent data elements' sensitivity to change; categorization of core and peripheral data elements; model integration; and figures of merit by which to fortify data architectures to withstand design fossilization and guide their evolution amidst changing requirements.     

Extending existing dependency theory to temporal databases

Normal forms play a central role in the design of relational databases. Several normal forms for temporal relational databases have been proposed. These definitions are particular to specific temporal data models, which are numerous and incompatible. The paper attempts to rectify this situation. We define a consistent framework of temporal equivalents of the important conventional database design concepts: functional dependencies, primary keys, and third and Boyce-Codd normal forms. This framework is enabled by making a clear distinction between the logical concept of a temporal relation and its physical representation. As a result, the role played by temporal normal forms during temporal database design closely parallels that of normal forms during conventional database design. These new normal forms apply equally well to all temporal data models that have timeslice operators, including those employing tuple timestamping, backlogs, and attribute value timestamping. As a basis for our research, we conduct a thorough examination of existing proposals for temporal dependencies, keys, and normal forms. To demonstrate the generality of our approach, we outline how normal forms and dependency theory can also be applied to spatial and spatiotemporal databases     

Database sampling with functional dependencies

During the development of information systems, there is a need to prototype the database that the applications will use when in operation. A prototype database can be built by sampling data from an existing database. Including relevant semantic information when extracting a sample from a database is considered invaluable to support the development of data-intensive applications. Functional dependencies are an example of semantic information that could be considered when sampling a database. This paper investigates how a database relation can be sampled so that the resulting sample satisfies precisely a given set of functional dependencies (and its logical consequences), i.e. is an Armstrong relation.     

XML函数依赖研究综述

函数依赖作为数据库规范化的基础在关系理论中起着重要的作用。近年来，XML得到广泛应用并已成为互联网上数据传输和交换的标准。由于XML半结构化的特性，使得如何定义XML函数依赖使其具有更强的描述能力，以及如何解决相应的逻辑蕴涵问题成为当今学术界所面临的挑战。针对这些问题，系统地描述了目前关于XML函数依赖的研究现状，特别是把分析的重点放在如何定义函数依赖、判断其蕴涵关系以及从XML文档中发现函数依赖等问题上。最后讨论了诸如类型化函数依赖关系等一些相关的研究方向。     

A New Approach to Database Auto-Design by Logic

The database auto-design is an important problem in database research.In this paper we propose some new ideas and an approach called “logic approach” to implement the database auto-design.Given a relational scheme and a set of the functional dependencies for the relation we can obtain all of the functional dependencies and key for the relation and determine the normal form the relation satisfies.     

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.     

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.     

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.     

Deriving support threshold values and membership functions using the multiple-level cluster-based master–slave IFG approach

Today, development of e-commerce has provided many transaction databases with useful information for investigators exploring dependencies among the items. In data mining, the dependencies among different items can be shown using an association rule. The new fuzzy-genetic (FG) approach is designed to mine fuzzy association rules from a quantitative transaction database. Three important advantages are associated with using the FG approach: (1) the association rules can be extracted from the transaction database with a quantitative value; (2) extracting proper membership functions and support threshold values with the genetic algorithm will exert a positive effect on the mining process results; (3) expressing the association rules in a fuzzy representation is more understandable for humans. In this paper, we design a comprehensive and fast algorithm that mines level-crossing fuzzy association rules on multiple concept levels with learning support threshold values and membership functions using the cluster-based master–slave integrated FG approach. Mining the fuzzy association rules on multiple concept levels helps find more important, useful, accurate, and practical information.     

XML弱函数依赖及其推理规则

XML函数依赖问题是进行XML数据库后续研究的基础。首先基于M.Arenas等人给定的XML中DTD和XML树的定义,提出空值、不完全树元组、数据值偏序、最小扩展树等概念,在此基础上,给出弱函数依赖及其满足性的定义;其次研究了XML弱函数依赖的逻辑蕴含问题,提出一组适合XML空值模型的函数依赖推理规则集;最后给出推理规则集的正确性和完备性证明。     

Characterizing functional dependencies in formal concept analysis with pattern structures

Computing functional dependencies from a relation is an important database topic, with many applications in database management, reverse engineering and query optimization. Whereas it has been deeply investigated in those fields, strong links exist with the mathematical framework of Formal Concept Analysis. Considering the discovery of functional dependencies, it is indeed known that a relation can be expressed as the binary relation of a formal context, whose implications are equivalent to those dependencies. However, this leads to a new data representation that is quadratic in the number of objects w.r.t. the original data. Here, we present an alternative avoiding such a data representation and show how to characterize functional dependencies using the formalism of pattern structures, an extension of classical FCA to handle complex data. We also show how another class of dependencies can be characterized with that framework, namely, degenerated multivalued dependencies. Finally, we discuss and compare the performances of our new approach in a series of experiments on classical benchmark datasets.     

分布式数据库中冲突检测技术研究

数据冲突是数据库中数据质量中心问题之一。在集中式数据库中,基于SQL技术可以有效地检测出违背给定条件函数依赖集的元组。然而,当数据库中数据被水平或垂直划分且分布在不同站点时,检测数据冲突将面临更大的挑战,常常需要将数据从一个站点移动到另外一个站点。提出了分布式数据库中条件函数依赖冲突检测算法,该算法不仅能有效地检测出水平划分数据中条件函数依赖冲突,而且能减少数据传输。实验结果证实算法是有效的。     

On the equivalence between FDs in XML and FDs in relations

With the growing use of the eXtensible Markup Language (XML) in database technology as a format for the permanent storage of data, the topic functional dependencies in XML (XFDs) has assumed increased importance because of its central role in database design. Recently, two different approaches have been proposed for defining an XFD. The first uses the concept of a ‘tree tuple’, whereas the second uses the concept of a ‘closest node’. In general, the two approaches are not comparable, but are comparable when a Document Type Definition is present and there is no missing information in the XML document. The first contribution of this article shows that when the two XFD definitions are comparable, the definitions are equivalent, and so there is essentially a common definition of an XFD in complete XML documents. The second contribution is to provide justification for the definition of a ‘closest node’ XFD. We show that if a complete flat relation is mapped to an XML document by an arbitrary sequence of nest operations, the XML document satisfies a ‘closest node’ XFD if and only if the relation satisfies the corresponding functional dependency. The class of XML documents generated in this fashion is a subset of the class of XML documents for which the two definitions of XFDs coincide. Hence ‘tree tuple’ and ‘closest node’ XFDs both capture the semantics of FDs when a complete relation is mapped to an XML document via arbitrary nesting.