The Experts below are selected from a list of 162 Experts worldwide ranked by ideXlab platform
J. Vandenbulcke - One of the best experts on this subject based on the ideXlab platform.
-
normalization based on fuzzy functional dependency in a fuzzy relational data model
Information Systems, 1996Co-Authors: Guoquing Chen, Etienne E. Kerre, J. VandenbulckeAbstract:Abstract In many cases, classical databases need to be extended in order to represent and manipulate uncertain and imprecise information. In a fuzzy relational data model where attribute values are represented by possibility distributions and domains are associated with closeness relations, the problems of update anomalies and data redundancy may still exist. This paper aims to extend the normalization theory of the classical relational data model so as to provide theoretical guidelines for fuzzy relational database design. Based upon the notion of fuzzy functional dependency (FFD), a number of concepts such as relation keys and normal forms are generalized. As a result, q-keys. Fuzzy First normal form (F1NF), q-Fuzzy Second normal form (q-F2NF), q-Fuzzy Third normal form (q-F3NF), and q-Fuzzy boyce-codd normal form (q-FBCNF) have been formulated. Finally, dependency-preserving and lossless-join decompositions into q-F3NFs are discussed.
-
An extended boyce-codd normal form in fuzzy relational databases
Proceedings of IEEE 5th International Fuzzy Systems, 1996Co-Authors: Guoqing Chen, Etienne E. Kerre, J. VandenbulckeAbstract:If the relation schemes of any fuzzy database are not properly designed certain anomaly problems may occur when the fuzzy database is updated or maintained. This is because some undesired relationships exist among attributes. Based on the notions of fuzzy functional dependency (FFD) and /spl theta/-keys, the boyce-codd normal form is extended to cope with the anomaly problems caused by partial and transitive FFDs of /spl theta/-prime on some /spl theta/-keys, thus resulting in /spl theta/-fuzzy boyce-codd normal form (/spl theta/-FBCNF). Furthermore, the relationship between /spl theta/-FBCNF and other existing fuzzy normal forms is analyzed, showing that /spl theta/-FBCNF reflects the strongest restriction for attributes. Finally an algorithm is provided that can decompose, in a lossless-join manner, any scheme into a number of /spl theta/-FBCNF schemes.
-
Fuzzy normal forms and a dependency-preserving decomposition into /spl theta/-F3NF
Proceedings of 1994 IEEE 3rd International Fuzzy Systems Conference, 1994Co-Authors: Guoqing Chen, Etienne E. Kerre, J. VandenbulckeAbstract:In a fuzzy data model where imprecision of both attribute values and relationships among domain elements is taken into account, problems of data redundancy and update anomalies which are similar to those in classical databases are still found to exist. To cope with these problems, a number of fuzzy normal forms have been defined, based on fuzzy functional dependency, to serve as theoretical guidelines for fuzzy relational database design. This results in the notions of /spl theta/-keys, fuzzy first normal form (F1NF), /spl theta/-fuzzy second normal form (/spl theta/-F2NF), /spl theta/-fuzzy third normal form (/spl theta/-F3NF), and /spl theta/-fuzzy boyce-codd normal form (/spl theta/-FBCNF). Furthermore, the scheme decomposition into /spl theta/-F3NF is discussed in the light of the dependency-preserving property.
Csilla Farkas - One of the best experts on this subject based on the ideXlab platform.
-
Data Dependencies Preserving Shuffle in Relational Database
2019 2nd International Conference on Data Intelligence and Security (ICDIS), 2019Co-Authors: Hatim Alsuwat, Emad Alsuwat, Tieming Geng, Chin-tser Huang, Csilla FarkasAbstract:This paper addresses the problem that database shuffling algorithms do not preserve data dependencies. We introduce an approach for preserving functional dependencies and data-driven associations during database shuffle. We use boyce-codd normal form (BCNF) decomposition for preserving functional dependencies. Given a relation R that is not in BCNF form, we recommend to decompose R into BCNF relations R1, ..., Rn. Each Ri (i = 1, ...,n) is shuffled then rejoined to create the shuffled relation. Our approach guarantees losslessness and preserves functional dependencies. Data-driven associations may also be lost during database shuffling. For this, we generate the transitive closure of attributes that are associated. We require that the associated attributed are shuffled together. We also present our theoretical and empirical results.
-
ICDIS - Data Dependencies Preserving Shuffle in Relational Database
2019 2nd International Conference on Data Intelligence and Security (ICDIS), 2019Co-Authors: Hatim Alsuwat, Emad Alsuwat, Tieming Geng, Chin-tser Huang, Csilla FarkasAbstract:This paper addresses the problem that database shuffling algorithms do not preserve data dependencies. We introduce an approach for preserving functional dependencies and data-driven associations during database shuffle. We use boyce-codd normal form (BCNF) decomposition for preserving functional dependencies. Given a relation R that is not in BCNF form, we recommend to decompose R into BCNF relations R1, ..., Rn. Each Ri (i = 1, ...,n) is shuffled then rejoined to create the shuffled relation. Our approach guarantees losslessness and preserves functional dependencies. Data-driven associations may also be lost during database shuffling. For this, we generate the transitive closure of attributes that are associated. We require that the associated attributed are shuffled together. We also present our theoretical and empirical results.
Sebastian Link - One of the best experts on this subject based on the ideXlab platform.
-
ADC - normalisation in the presence of lists
2020Co-Authors: Sebastian Link, Sven HartmannAbstract:In the relational data model (RDM), normal forms are conditions for relation schemata that a database design should satisfy to ensure an absence of processing difficulties with the database. One prime example of such a normal form is the boyce-codd normal form guaranteeing the absence of redundancies and update anomalies caused by functional dependencies (FDs).Many different data models have been introduced over the years trying to capture data beyond relational structures. The success of those advanced data models will depend, in particular, on the study of normal forms. In fact, finding a unifying framework and extending achievements of relational databases to deal with advanced database features such as complex object types are currently two major challenges in database design (Biskup 1995, Biskup 1998).Such a unifying approach, capturing various different data models at a time, can be based on the type systems underlying the various data models. In the present paper, we study normalisation in the presence of base, record and finite list types. Nested lists are used as a data structure whenever order matters. List types are therefore supported by many advanced data models such as genomic sequence, deductive and object-oriented data models including XML.On the basis of a finite axiomatisation of FDs in the presence of lists the Nested List normal form (NLNF) is proposed as a weaker normal form than BCNF. This proposal is semantically justified by formally proving that NLNF is equivalent to the absence of redundancy. Moreover, NLNF is equivalent to the absence of strong insertion and most forms of replacement anomalies, and sufficient for the absence of all types of update anomalies.
-
SQL schema design: foundations, normal forms, and normalization
Information Systems, 2018Co-Authors: Henning Köhler, Sebastian LinkAbstract:Abstract normalization helps us find a database schema at design time that can process the most frequent updates efficiently at run time. Unfortunately, relational normalization only works for idealized database instances in which duplicates and null markers are not present. On one hand, these features occur frequently in real-world data compliant with the industry standard SQL, and especially in modern application domains. On the other hand, the features impose challenges that make it difficult to extend the existing forty year old normalization framework to SQL, and any current extensions are fairly limited. We introduce a new class of functional dependencies and show that they provide the right notion for SQL schema design. Axiomatic and linear-time algorithmic characterizations of the associated implication problem are established. These foundations enable us to propose a Boyce–Codd normal form for SQL. We justify the normal form by showing that it permits precisely those SQL instances which are free from data redundancy. Unlike the relational case, there are SQL schemata that cannot be converted into Boyce–Codd normal form. Nevertheless, for an expressive sub-class of our functional dependencies we establish a normalization algorithm that always produces a schema in Value-Redundancy free normal form. This normal form permits precisely those instances which are free from any redundant data value occurrences other than the null marker. Experiments show that our functional dependencies occur frequently in real-world data and that they are effective in eliminating redundant values from these data sets without loss of information.
-
SIGMOD Conference - SQL Schema Design: Foundations, normal forms, and normalization
Proceedings of the 2016 International Conference on Management of Data - SIGMOD '16, 2016Co-Authors: Henning Köhler, Sebastian LinkAbstract:normalization helps us find a database schema at design time that can process the most frequent updates efficiently at run time. Unfortunately, relational normalization only works for idealized database instances in which duplicates and null markers are not present. On one hand, these features occur frequently in real-world data compliant with the industry standard SQL, and especially in modern application domains. On the other hand, the features impose challenges that have made it impossible so far to extend the existing forty year old normalization framework to SQL. We introduce a new class of functional dependencies and show that they provide the right notion for SQL schema design. Axiomatic and linear-time algorithmic characterizations of the associated implication problem are established. These foundations enable us to propose a boyce-codd normal form for SQL. Indeed, we justify the normal form by showing that it permits precisely those SQL instances which are free from data redundancy. Unlike the relational case, there are SQL schemata that cannot be converted into boyce-codd normal form. Nevertheless, for an expressive sub-class of our functional dependencies we establish a normalization algorithm that always produces a schema in Value-Redundancy free normal form. This normal form permits precisely those instances which are free from any redundant data value occurrences other than the null marker. Experiments show that our functional dependencies occur frequently in real-world data and that they are effective in eliminating redundant values from these data sets without loss of information.
-
WoLLIC - The boyce-codd-heath normal form for SQL
Logic Language Information and Computation, 2011Co-Authors: Flavio Ferrarotti, Sebastian Link, Henning Köhler, Sven Hartmann, Millist W. VincentAbstract:In the relational model of data the boyce-codd-Heath normal form, commonly just known as boyce-codd normal form, guarantees the elimination of data redundancy in terms of functional dependencies. For efficient means of data processing the industry standard SQL permits partial data and duplicate rows of data to occur in database systems. Consequently, the combined class of uniqueness constraints and functional dependencies is more expressive than the class of functional dependencies itself. Hence, the boyce-codd-Heath normal form is not suitable for SQL databases. We characterize the associated implication problem of the combined class in the presence of NOT NULL constraints axiomatically, algorithmically and logically. Based on these results we are able to establish a suitable normal form for SQL.
Ronald Fagin - One of the best experts on this subject based on the ideXlab platform.
-
ICDT - A normal form for preventing redundant tuples in relational databases
Proceedings of the 15th International Conference on Database Theory - ICDT '12, 2012Co-Authors: Hugh Darwen, C. J. Date, Ronald FaginAbstract:We introduce a new normal form, called essential tuple normal form (ETNF), for relations in a relational database where the constraints are given by functional dependencies and join dependencies. ETNF lies strictly between fourth normal form and fifth normal form (5NF, also known as projection-join normal form). We show that ETNF, although strictly weaker than 5NF, is exactly as effective as 5NF in eliminating redundancy of tuples. Our definition of ETNF is semantic, in that it is defined in terms of tuple redundancy. We give a syntactic characterization of ETNF, which says that a relation schema is in ETNF if and only if it is in boyce-codd normal form and some component of every explicitly declared join dependency of the schema is a superkey.
-
Response to “Remarks on two new theorems of Date and Fagin”
ACM SIGMOD Record, 1993Co-Authors: C. J. Date, Ronald FaginAbstract:In [DF92], we present simple conditions, which we now describe, for guaranteeing higher normal forms for relational databases. A key is simple if it consists of a single attribute. We show in [DF92] that if a relation schema is in third normal form (3NF) and every key is simple, then it is in projection-join normal form (sometimes called fifth normal form), the ultimate normal form with respect to projections and joins. We also show in [DF92] that if a relation schema is in boyce-codd normal form (BCNF) and some key is simple, then it is in fourth normal form (4NF). These results give the database designer simple sufficient conditions, defined in terms of functional dependencies alone, that guarantee that the schema being designed is automatically in higher normal forms.
-
Simple conditions for guaranteeing higher normal forms in relational databases
ACM Transactions on Database Systems, 1992Co-Authors: C. J. Date, Ronald FaginAbstract:A key is simple if it consists of a single attribute. It is shown that if a relation schema is in third normal form and every key is simple, then it is in projection-join normal form (sometimes called fifth normal form), the ultimate normal form with respect to projections and joins. Furthermore, it is shown that if a relation schema is in boyce-codd normal form and some key is simple, then it is in fourth normal form (but not necessarily projection-join normal form). These results give the database designer simple sufficient conditions, defined in terms of functional dependencies alone, that guarantee that the schema being designed is automatically in higher normal forms.
Hatim Alsuwat - One of the best experts on this subject based on the ideXlab platform.
-
Data Dependencies Preserving Shuffle in Relational Database
2019 2nd International Conference on Data Intelligence and Security (ICDIS), 2019Co-Authors: Hatim Alsuwat, Emad Alsuwat, Tieming Geng, Chin-tser Huang, Csilla FarkasAbstract:This paper addresses the problem that database shuffling algorithms do not preserve data dependencies. We introduce an approach for preserving functional dependencies and data-driven associations during database shuffle. We use boyce-codd normal form (BCNF) decomposition for preserving functional dependencies. Given a relation R that is not in BCNF form, we recommend to decompose R into BCNF relations R1, ..., Rn. Each Ri (i = 1, ...,n) is shuffled then rejoined to create the shuffled relation. Our approach guarantees losslessness and preserves functional dependencies. Data-driven associations may also be lost during database shuffling. For this, we generate the transitive closure of attributes that are associated. We require that the associated attributed are shuffled together. We also present our theoretical and empirical results.
-
ICDIS - Data Dependencies Preserving Shuffle in Relational Database
2019 2nd International Conference on Data Intelligence and Security (ICDIS), 2019Co-Authors: Hatim Alsuwat, Emad Alsuwat, Tieming Geng, Chin-tser Huang, Csilla FarkasAbstract:This paper addresses the problem that database shuffling algorithms do not preserve data dependencies. We introduce an approach for preserving functional dependencies and data-driven associations during database shuffle. We use boyce-codd normal form (BCNF) decomposition for preserving functional dependencies. Given a relation R that is not in BCNF form, we recommend to decompose R into BCNF relations R1, ..., Rn. Each Ri (i = 1, ...,n) is shuffled then rejoined to create the shuffled relation. Our approach guarantees losslessness and preserves functional dependencies. Data-driven associations may also be lost during database shuffling. For this, we generate the transitive closure of attributes that are associated. We require that the associated attributed are shuffled together. We also present our theoretical and empirical results.
