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.     

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.     

Interval-based temporal functional dependencies: specification and verification

In the temporal database literature, every fact stored in a database may be equipped with two temporal dimensions: the valid time, which describes the time when the fact is true in the modeled reality, and the transaction time, which describes the time when the fact is current in the database and can be retrieved. Temporal functional dependencies (TFDs) add valid time to classical functional dependencies (FDs) in order to express database integrity constraints over the flow of time. Currently, proposals dealing with TFDs adopt a point-based approach, where tuples hold at specific time points, to express integrity constraints such as “for each month, the salary of an employee depends only on his role”. To the best of our knowledge, there are no proposals dealing with interval-based temporal functional dependencies (ITFDs), where the associated valid time is represented by an interval and there is the need of representing both point-based and interval-based data dependencies. In this paper, we propose ITFDs based on Allen’s interval relations and discuss their expressive power with respect to other TFDs proposed in the literature: ITFDs allow us to express interval-based data dependencies, which cannot be expressed through the existing point-based TFDs. ITFDs allow one to express constraints such as “employees starting to work the same day with the same role get the same salary” or “employees with a given role working on a project cannot start to work with the same role on another project that will end before the first one”. Furthermore, we propose new algorithms based on B-trees to efficiently verify the satisfaction of ITFDs in a temporal database. These algorithms guarantee that, starting from a relation satisfying a set of ITFDs, the updated relation still satisfies the given ITFDs.     

Generic dependencies and database design

The concept of functional dependencies in databases is generalized and called generic dependencies. Just as a Karnaugh map exhibits all the functional dependencies in a relation, an entropy map represents all the generic dependencies. A generalized normal form useful in database design is defined.     

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.     

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.     

Inferring dependencies from relations: a conceptual clustering approach

In this paper we consider two related types of data dependencies that can hold in a relation: conjunctive implication rules between attribute‐value pairs, and functional dependencies. We present a conceptual clustering approach that can be used, with some small modifications, for inferring a cover for both types of dependencies. The approach consists of two steps. First, a particular clustered representation of the relation, called concept (or Galois ) lattice , is built. Then, a cover is extracted from the lattice built in the earlier step. Our main emphasis is on the second step. We study the computational complexity of the proposed approach and present an experimental comparison with other methods that confirms its validity. The results of the experiments show that our algorithm for extracting implication rules from concept lattices clearly outperforms an earlier algorithm, and suggest that the overall lattice‐based approach to inferring functional dependencies from relations can be seen as an alternative to traditional methods.     

Armstrong databases for functional and inclusion dependencies

An Armstrong database is a database that obeys precisely a given set of sentences (and their logical consequences) and no other sentences of a given type. It is shown that if the sentences of interest are inclusion dependencies and standard functional dependencies (functional dependencies for which the left-hand side is nonempty), then there is always an Armstrong database for each set of sentences. (An example of an inclusion dependency is the sentence that says that every $\text{MANAGER}$ is an $\text{EMPLOYEE}$.) If, however, the sentences of interest are inclusion dependencies and unrestricted functional dependencies, then there need not exist an Armstrong database. This result holds even if we allow only ‘full’ inclusion dependencies. Thus, a fairly sharp line is drawn, in a case of interest, as to when an Armstrong database must exist. These results hold whether we restrict our attention to finite databases (databases with a finite number of tuples), or whether we allow unrestricted databases.     

Exploring into programs for the recovery of data dependenciesdesigned

Data dependencies play an important role in the design of a database. Many legacy database applications have been developed on old generation database management systems and conventional file systems. As a result, most of the data dependencies in legacy databases are not enforced in the database management systems. As such, they are not explicitly defined in database schema and are enforced in the transactions, which update the databases. It is very difficult and time consuming to find out the designed data dependencies manually during the maintenance and reengineering of database applications. In software engineering, program analysis has long been developed and proven as a useful aid in many areas. With the use of program analysis, this paper proposes a novel approach for the recovery of common data dependencies, i.e., functional dependencies, key constraints, inclusion dependencies, referential constraints, and sum dependencies, designed in a database from the behavior of transactions, which update the database. The approach is based on detecting program path patterns for implementing most commonly used methods to enforce these data dependencies     

NF-NR: A practical normal form for nested relations

We propose a normal form for nested relations, called NF-NR, which removes undesirable anomalies from a nested relational database schema. Both functional dependencies and multivalued dependencies are considered. NF-NR reduces to 3NF/4NF if the nested relation considered is actually a flat relation. Especially, NF-NR removes global redundancies among a set of nested relations. Two approaches to NF-NR database design, namely the restructuring rules approach and the ER approach, are discussed. We relate NF-NR to ER-NF, a normal form of ER defined earlier, by defining a simple mapping from an ERD in ER-NF to a set of nested relations in NF-NR. This approach effectively removes ambiguitics and redundancies on a semantic level and hence gives a set of nested relations with clean semantics and yet in good normal form. A set of desirable properties for any normal form for nested relations are described and an evaluation of several existing normal forms is given based on this set of properties. The evaluation shows that NF-NR improves over previously proposed normal forms in various aspects and is a more practical normal form for nested relations.     

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.     

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.     

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.     

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.     

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.     

Polynomial Tests of Normal Forms and Some Related Results

The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is he set of dependencies explicitly given for each relation scheme equivalent to the dependencies implied for that relation sheme?”It is shown that when the everywhere-cover problem has a yes answer,examining only the dependencies explicitly given will suffice to test 3NF, BCNF and 4NF of a database scheme.But this does not hold for 2NF.Consequently,in such cases,tests of BCNF and 4NF all take polynomial time.Then a proof is given that test of 3NF of a database scheme is Co-NP-complete,and from this result it is shown that everywhere-cover is also Co-NP-complete when only functional dependencies are allowed.These results lead to doubt the truth of the well believed conjecture that no polynomial time algorithm for designing a lossless BCNF database scheme is likely to exist.     

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.     

Querying Weak Instances Under Extension Chase Semantics: A Complete Solution

The problem of computing windows using relational expressions has been solved only in certain cases in which the chase semantics and the extension chase semantics of the database coincide. However, the general problem of computing windows under either chase semantics or extension chase semantics, but without restrictions, remained an open problem. In this paper we present a complete solution of the general problem, under extension chase semantics. Our solution is complete in the sense that it does not require any assumption on the database scheme or on the database state. It follows that our approach subsumes previous approaches, and we exhibit cases in which our approach correctly computes the windows, while previous approaches fail to do so. Moreover, the efficiency of our approach lies in the fact that it uses only those relation schemes and only those functional dependencies that are necessary in the computation of windows. The main technique employed by our approach is a least fixpoint construction using the notion of cover (a cover being a set of relation schemes satisfying certain properties). The proposed technique can be implemented using relational algebra plus recursion.     

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|²).     

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”