Null Inclusion Dependencies in Relational Databases

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. We introduce null inclusion dependencies (NINDs) to cater for the situation when a database is incomplete and contains null values. We show that the implication problem for NINDs is the same as that for INDs. We then present a sound and complete axiom system for null functional dependencies (NFDs) and NINDs, and prove that the implication problem for NFDs and NINDs is decidable and EXPTIME-complete. By contrast, when no nulls are allowed, this implication problem is undecidable. This undecidability result has motivated several researchers to restrict their attention to FDs and noncircular INDs in which case the implication problem was shown to be EXPTIME- complete. Our results imply that when considering nulls in relational database design we need not assume that NINDs are noncircular.     

A new approach to generate weighted fuzzy rules using genetic algorithms for estimating null values

In this paper, we present a new method to generate weighted fuzzy rules using genetic algorithms for estimating null values in relational database systems, where there are negative functional dependency relationships between attributes. The proposed method can get higher average estimated accuracy rates than the method presented in [Chen, S. M., & Huang, C. M. (2003). Generating weighted fuzzy rules from relational database systems for estimating null values using genetic algorithms. IEEE Transactions on Fuzzy Systems, 11(4), 495–506].     

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.     

A NEW METHOD TO GENERATE FUZZY RULES FROM RELATIONAL DATABASE SYSTEMS FOR ESTIMATING NULL VALUES

Fuzzy decision trees can be used to generate fuzzy rules from training instances to deal with forecasting and classification problems. We propose a new method to construct fuzzy decision trees from relational database systems and to generate fuzzy rules from the constructed fuzzy decision trees for estimating null values, where the weights of attributes are used to derive the values of certainty factors of the generated fuzzy rules. We use the concept of "coefficient of determination" of the statistics to derive the weights of the attributes in relational database systems and use the normalized weights of the attributes to derive the values of certainty factors of the generated fuzzy rules. Furthermore, we also use regression equations of the statistics to construct a complete fuzzy decision tree for generating better fuzzy rules. The proposed method obtains a higher average estimated accuracy rate than the existing methods for estimating null values in relational database systems.     

GENERATING FUZZY RULES FROM RELATIONAL DATABASE SYSTEMS FOR ESTIMATING NULL VALUES

This paper presents a new algorithm for constructing fuzzy decision trees from relational database systems and generating fuzzy rules from the constructed fuzzy decision trees. We also present a method for dealing with the completeness of the constructed fuzzy decision trees. Based on the generated fuzzyrules, we also present a method for estimating null values in relational database systems. The proposed methods provide a useful way to estimate null values in relational database systems.     

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

An efficient method for estimating null values in relational databases

Generally, a database system containing null value attributes will not operate properly. This study proposes an efficient and systematic approach for estimating null values in a relational database which utilizes clustering algorithms to cluster data, and a regression coefficient to determine the degree of influence between different attributes. Two databases are used to verify the proposed method: (1) Human resource database; and (2) Waugh's database. Furthermore, the mean of absolute error rate (MAER) and average error are used as evaluation criteria to compare the proposed method with other methods. It demonstrates that the proposed method is superior to existing methods for estimating null values in relational database systems. Jia-Wen Wang was born on September 5, 1978, in Taipei, Taiwan, Republic of China. She received the M.S. degree in information management from the National Yunlin University of Science and Technology, Yunlin, Taiwan, in 2003. Since 2003, she has been a PhD degree student in Information Management Department at the National Yunlin University of Science and Technology. Her current research interests include fuzzy systems, database systems, and artificial intelligence. Ching-Hsue Cheng received the B.S. degree in mathematics from Chinese Military Academy, Taiwan, in 1982, the M.S. degree in applied mathematics from the Chung Yuan Christian University, Taiwan, in 1988, and the Ph.D. degree in system engineering and management from National Defence University, Taiwan, in 1994. Currently, he is a professor of the Department of Information Management, National YunLin University of Technology & Science. His research interests are in decision science, soft computing, software reliability, performance evaluation, and fuzzy time series. He has published more than 120 refereed papers in these areas. He has been a principal investigator and project leader in a number of projects with government, and other research-sponsoring agencies.     

Estimating null values in relational database systems using automatic clustering and multiple regression techniques

In this paper, we present a new method for estimating null values in relational database systems using automatic clustering and multiple regression techniques. First, we present a new automatic clustering algorithm for clustering numerical data. The proposed automatic clustering algorithm does not need to determine the number of clusters in advance and does not need to sort the data in the database in advance. Then, based on the proposed automatic clustering algorithm and multiple regression techniques, we present a new method to estimate null values in relational database systems. The proposed method estimating null values in relational database systems only needs to process a particular cluster instead of the whole database. It gets a higher average estimation accuracy rate than the existing methods for estimating null values in relational database systems.     

A new approach for estimating null value in relational database

In general, a database system will not operate properly if it exist some null values of attributes in the system. In this paper, we propose a new approach to estimate null values in relational database, which utilize other clustering algorithm to cluster data, and use fuzzy correlation and distance similarity to calculate the correlation of different attribute. For verifying our method, this paper utilize mean of absolute error rate (MAER) as evaluation criterion to compare with other methods; it is shown that our proposed method proves importance than the existing methods for estimating null values in relational database systems.     

On characterizing boundedness of database schemes with bounded dependencies

We investigate the effect of bounded dependencies on the boundedness of database schemes. The following results are proved. A database scheme with only bounded equality-generating dependencies is always bounded with respect to dependencies; a lossless database scheme with bounded full implicational dependencies is bounded w.r.t. dependencies if and only if the implicational dependencies are equivalent to a single join dependency and some equality-generating dependencies. By a known method, this condition can be tested effectively. These results are relevant in database theory in that they determine in a rather general case whether queries under the representative instance approach can be expressed in relational algebra.     

Null values in nested relational databases

Summary The desire to extend the applicability of the relational model beyond traditional data-processing applications has stimulated interest in nested or non-first normal form relations in which the attributes of a relation can take on values which are sets or even relations themselves. In this paper, we study the role of null values in the nested relational model using an open world assumption. We extend the traditional theory and study the properties of extended operators for nested relations containing nulls. The no-information, unknown, and non-existent interpretation of nulls are discussed and the meaning of empty set is clarified. Finally, contrary to several previous results, we determine that the traditional axiomatization of functional and multivalued dependencies is valid in the presence of nulls.Currently with the Air Force Institute of Technology, AFIT/ENG, Wright-Patterson AFB, OH 45433, USAResearch partially supported by an IBM Faculty Development A ward and NSF grant DCR-8507224     

A new method to estimate null values in relational database systems based on automatic clustering techniques

In this paper, we present a new method for estimating null values in relational database systems based on automatic clustering techniques. The proposed method clusters data in advance, such that it only needs to process the most proper clusters instead of all the data in the relational database system for estimating null values. The average estimated accuracy rate of the proposed method is better than the existing methods for estimating null values in relational database systems.     

Fuzzy data compression based on data dependencies

In this article, we focus on the issues of fuzzy data dependencies. After introducing the notion of semantic equivalence degree, fuzzy functional and multivalued dependencies are defined. A set of sound and complete inference rules, similar to Armstrong's axioms for classic cases, for fuzzy functional dependencies (FFDs) and fuzzy multivalued dependencies (FMVDs) are proposed. The strategies and approaches for compressing fuzzy values by FFDs and FMVDs are investigated. By such processing, the unnecessary elements are eliminated from a fuzzy value and its range is compressed. © 2002 Wiley Periodicals, Inc.     

A data model and algebra for probabilistic complex values

We present a probabilistic data model for complex values. More precisely, we introduce probabilistic complex value relations, which combine the concept of probabilistic relations with the idea of complex values in a uniform framework. We elaborate a model-theoretic definition of probabilistic combination strategies, which has a rigorous foundation on probability theory. We then define an algebra for querying database instances, which comprises the operations of selection, projection, renaming, join, Cartesian product, union, intersection, and difference. We prove that our data model and algebra for probabilistic complex values generalizes the classical relational data model and algebra. Moreover, we show that under certain assumptions, all our algebraic operations are tractable. We finally show that most of the query equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniques for classical relational algebra can easily be applied to optimize queries on probabilistic complex value relations.     

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.     

Null values in fuzzy databases

Since in the real world, it often occurs that information is missing, database systems clearly need some facilities to deal with missing data. With respect to traditional database systems, the most commonly adopted approach to this problem is based on null values and three valued logic. This paper deals with the semantics and the use of null values in fuzzy databases. In dealing with missing information a distinction is made between incompleteness due to unavailability and incompleteness due to inapplicability. Both the database modelling and database querying aspects are described. With respect to attribute values, incompleteness due to unavailability is modelled by possibility distributions, which is a commonly used technique in the fuzzy databases. Domain specific null values, represented by a bottom symbol, are used to model incompleteness due to inapplicability. Extended possibilistic truth values are used to formalize the impact of data manipulation and (flexible) querying operations in the presence of these null values. The different cases of appearances of null values in the handling of selection conditions of flexible database queries are described in detail.     

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.     

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.     

Learning indistinguishability from data

 In this paper we revisit the idea of interpreting fuzzy sets as representations of vague values. In this context a fuzzy set is induced by a crisp value and the membership degree of an element is understood as the similarity degree between this element and the crisp value that determines the fuzzy set. Similarity is assumed to be a notion of distance. This means that fuzzy sets are induced by crisp values and an appropriate distance function. This distance function can be described in terms of scaling the ordinary distance between real numbers. With this interpretation in mind, the task of designing a fuzzy system corresponds to determining suitable crisp values and appropriate scaling functions for the distance. When we want to generate a fuzzy model from data, the parameters have to be fitted to the data. This leads to an optimisation problem that is very similar to the optimisation task to be solved in objective function based clustering. We borrow ideas from the alternating optimisation schemes applied in fuzzy clustering in order to develop a new technique to determine our set of parameters from data, supporting the interpretability of the fuzzy system.