Search

Data bases play an important role in applied Mathematics. Normalization for relational databases is very important to avoid anomalies of relations which may not be in normalized forms of the third normal forms. But, normalization may be a difficult task, since the designers of the databases may not fully understand the domain of each attribute that are contained in the relation schema or they may not have full understanding about the concept of normalization. In this paper an efficient method that checks the possibility of the need of further normalization using stored data in relations is presented based on possible functional dependencies between attributes in the relations. By checking possible functional dependencies, the database designers can determine the need of further normalization, and may improve the structure of the relation schemas. Experiments were performed for an example of relational database that can be found in the organization of tutorial of MySQL which is a representational database management system, and the experiments showed good results.

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.

International audience; Driven by the dominance of the relational model, we investigate how the requirements of applications on the certainty of functional dependencies can improve the outcomes of relational database schema design. For that purpose, we assume that tuples are assigned a degree of possibility with which they occur in a relation, and that functional dependencies are assigned a dual degree of certainty which says to which tuples they apply. A design theory is developed for functional dependencies with degrees of certainty, including efficient axiomatic and algorithmic characterizations of their implication problem. Naturally, the possibility degrees of tuples bring forward different degrees of data redundancy, caused by functional dependencies with the dual degree of certainty. Variants of the classical syntactic Boyce–Codd and Third Normal Forms are established. They are justified semantically in terms of eliminating data redundancy and update anomalies of given degrees, and minimizing data redundancy of given degrees across all dependency-preserving decompositions, respectively. As a practical outcome of our results, designers can simply fix the degree of certainty they target, and then apply classical decomposition and synthesis to the set of functional dependencies whose associated degree of certainty meets the target. Hence, by fixing the certainty degree a designer controls which integrity requirements will be enforced for the application and which data will be processed by the application. The choice of the certainty degree also balances the classical trade-off between query and update efficiency on future database instances. Our experiments confirm the effectiveness of our control parameter, and provide original insight into classical normalization strategies and their implementations.

In Gunungkidul district, there are many tourist destinations that are worth visiting and have become tourist destinations from various regions outside Gunungkidul district. The context of the problem that underlies this research is the growing interest in developing applications through online map services using Google maps. The purpose of building a google map-based tourist destination information application is to make it easier for tourists to get tourist destination information through an integrated map with the web. The method used to gather needs and analysis is a fact-finding method with conducting unstructured interviews. The author also made direct observations on the spot, this method is very effective for analyzing and discovering system functions and gaining direct knowledge about activities, operations, and processes. The results of this study are database design that has been normalized to the 3rd normal form, and the application of travel information on Google maps. Through functional testing, this application has run well using travel data taken directly in Gunungkidul district.

When an attempt is made to modify tables that have not been sufficiently normalized undesirable sideeffects may follow. This can be further specified as an update, insertion or deletion anomaly depending on whether the action that causes the error is a row update, insertion or deletion respectively. If a relation R has more than one key, each key is referred to as a candidate key of R. Most of the practical recent works on database normalization use a restricted definition of normal forms where only the primary key (an arbitrary chosen key) is taken into account and ignoring the rest of candidate keys. In this paper, we propose an algorithmic approach for database normalization up to third normal form by taking into account all candidate keys, including the primary key. The effectiveness of the proposed approach is evaluated on many real world examples.

Magelang District is implementing the tourism development program that consists of: marketing development, tourism destination development, partnership development, and tourism infrastructure development. Data about tourism in Magelang regency has not been stored correctly according to the rules of database normalization, with redudancy data storage, including the data that stored and informed online. A good information system should be supported by accurate data and stored on a database that has been normalized, so that data can be read by the system or a different program with different goals and views. Based on the analysis of data obtained in Magelang District, there are several the same ways and the same and the different way of storing and displaying information tourism objects. Normalization process conduct on the obtained data until the 3rd normal form to eliminate the partial dependencies and transitive dependencies. The result of the reseach is a database model.

In this paper a tool called RDBNorma is proposed, that uses a novel approach to represent a relational database schema and its functional dependencies in computer memory using only one linked list and used for semi-automating the process of relational database schema normalization up to third normal form. This paper addresses all the issues of representing a relational schema along with its functional dependencies using one linked list along with the algorithms to convert a relation into second and third normal form by using above representation. We have compared performance of RDBNorma with existing tool called Micro using standard relational schemas collected from various resources. It is observed that proposed tool is at least 2.89 times faster than the Micro and requires around half of the space than Micro to represent a relation. Comparison is done by entering all the attributes and functional dependencies holds on a relation in the same order and implementing both the tools in same language and on same machine., Comment: 22 pages and international journal

Introduction Designing database is an art process similar to building a house. Database designers always face the problems of designing a relational database that will be free of database anomalies. These anomalies bring repetition of tuples that delay processing time and occupy memory spaces. Suppose that the value of the attribute BUILDER determines values of the attribute MODEL and PRICE, (BUILDER [right arrow] MODEL, PRICE) and that the value for the attribute MODEL determines the value for PRICE, (MODEL [right arrow] PRICE). Grouping these attributes in relation HOUSE(BUILDER, MODEL, PRICE) has several undesirable properties. First the relationship between MODEL and PRICE is repeated in the relation for each BUILDER who builds a particular MODEL of home. This repetition creates difficulties if a BUILDER who happens to be the last BUILDER of a certain MODEL home is deleted from the relation, then the relationship between the MODEL and its PRICE also disappears from the relation. This is called a deletion anomaly. Similarly, if a new builder who happens to be the first BUILDER of a certain MODEL home is added then the relationship between MODEL of a home and its PRICE will also be added. This is called an insertion anomaly. Suppose that the relationship between a MODEL and its PRICE is changed e.g. the price is increased; then the MODEL and PRICE relationship should be affected for every BUILDER of the MODEL. This is called update anomaly. These anomalies are undesirable since the user is not likely to realize the consequence of the insertion, deletion or updating. The user may inadvertently affect a relationship that was not intended to be modified. Consistency, insertion, deletion and updating are not probe effecting all groupings of attributes. If the relation HOUSE(BUILDER, MODEL, PRICE) is normalized then the consistency and anomaly problems disappear. Normalization is a step by step reversible process of replacing a given collection of relations by successive collection in which the relations have a progressively simpler and more regular structure (Date & Darwen, 2000). The reversibility guarantees that the original collection of relations can be recovered and therefore no information has been lost. Codd proposed three normal forms which he called first normal form (1NF), second normal form (2NF) and third normal form (3NF). A stronger definition of 3NF was proposed by Boyce and Codd and is known as Boyce-Codd Normal Form (BCNF). All these normal forms except 1NF are based on the functional dependencies among the attributes of a relation (Elmasri & Navathe, 1994). First normal form relates to the structure of the relation. It requires that every attribute of a relation be based on a simple domain. The database designers have no problem to know if a relation violates first normal form. They can put the relation into first normal form algorithmically by replacing a non-simple domain by its constituent simple domains. In the second (2NF), third (3NF) and Boyce Codd normal form (BCNF), there is a need for the database designers to know the real meaning and application of database keys such as candidate key, primary key, super key, etc,. Problem Statement Database designers always find it difficult to determine these keys from relational database schemas. It has been difficult to motivate students and database designers to derive primary, candidate, alternative and super keys because they think this area is dry and theoretical. There are many algorithms to determine the database keys but they look abstract for students. Many database researchers indicated that relational database model to derive database keys tends to be complex for the average designers. Failure to determine the database keys at times leads to poor design that can generate database anomalies. The database key algorithms often require extensive relational algebraic backgrounds that database designers lack. …

This paper discusses normalization of relations when the candidate keys of a relation have missing information represented by nulls. The paper shows that when the missing information is of the type “not applicable” or “does not exist,” problems and confusion can arise in normalizing relations. Candidate keys with missing information commonly are found in relations that represent information on two entities with a one-to-one relationship between them. The current definition of Boyce-Codd Normal Form (BCNF) is ineffective in identifying poor designs in such relations that may have insertion/deletion anomalies. It is shown that the above problem can be corrected by incorporating the concept of entity integrity rule into the definition of BCNF. This paper also shows that incorporating the entity integrity rule into the definition of either a relation or a candidate key does not provide a satisfactory solution to the problem.

The issue of providing a formal justification for the use of fourth normal form (4NF) in relational database design is investigated. The motivation and formal definitions for three goals of database design are presented. These goals are the elimination of: redundancy, key-based update anomalies and fact-based replacement anomalies. It is then shown that, depending on the type of constraints permitted, either Boyce-Codd normal form (BCNF) or 4NF are the exact conditions needed to ensure most of the design goals. However, it is also shown that the conditions required to ensure the absence of a particular class of key-based update anomaly are new normal forms which have not previously been identified. In particular, for the case where the only constraints are functional dependencies (FDs), it is shown that the required normal form is a new normal form that is stronger than third normal form (3NF) yet weaker than BCNF. Similarly, in the more general case where both FD and multivalued dependencies (MVDs) are present, the required normal form is a new normal form that is weaker than 4NF.

This paper presents a new dynamic dependency and a new normal form. We give the concept of the stability constraint and establish complete axioms for stability constraints. In addition, we propose a stability normal form. A temporal third normal form can be losslessly decomposed into a sequence of stability constraints. Using the decomposition, the storage space can be reduced. The stability constraints allow to fill a suitable value into a null value. Thus, this null value therefore turns into a known value.

In this paper, the adequacy of fifth normal form (5NF) in relational database design is investigated. It is shown that 5NF is inadequate because it does not generalise fourth normal form (4NF) and because it is equivalent to the very stringent requirement that every attribute is a key, a requirement that is effectively impossible to satisfy in practical database design. By restricting the join dependencies (JDs) in the set of constraints to those that do not have superfluous components, the definition of 5NF is then changed to a new normal form, called reduced fifth normal form (5NFR), and it is shown that 5NFR generalises 4NF. It is also shown that 5NFR is a strictly weaker condition than projection-join normal form (PJ/NF), the other normal form that has been proposed for JDs.

In this paper we present some characterizations of relation schemes in second normal form (2NF), third normal form (3NF) and Boyce-Codd normal form (BCNF). It is known [6]that the set of minimal keys of a relation scheme is a Sperner system (an antichain) and for an arbitrary Sperner system there exists a relation scheme the set of minimal keys of which is exactly the given Sperner system. We investigate families of 2NF, 3NF and BCNF relation schemes where the sets of minimal keys are given Sperner systems. We give characterizations of these families. The minimal Armstrong relation has been investigated in the literature [3, 7, 11, 15, 18]. This paper gives new bounds on the size of minimal Armstrong relations for relation schemes. We show that given a relation scheme s such that the set of minimal keys is the Sperner system K, the number of antikeys (maximal nonkeys) of K is polynomial in the number of attributes iff so is the size of minimal Armstrong relation of s. We give a new characterization of relations and relation schemes that are uniquely determined by their minimal keys. From this characterization we give a polynomial-time algorithm deciding whether an arbitrary relation is uniquely determined by its set of all minimal keys. We present a new polynomial-time algorithm testing BCNF property of a given relation scheme.

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.

Three object-oriented analysis techniques: Shlaer & Mellor, Coad & Yourdon, and Document-Driven Analysis were evaluated. Criteria for comparison of analysis techniques were developed. These criteria state that an analysis technique should (1) cover data, transformation, and control perspectives of the problem, (2) address large problems through partitioning, bounding the problem, and supporting prototypes and incremental analysis, (3) provide approaches for verification and validation, and (4) support configuration control. A case study in a software engineering class was conducted using the three OOA techniques. Through the case study we found that (1) identifying objects is affected by notation and flexibility of object models, (2) visualizing global data, transformations, and control are necessary to capture end-user’s processes, (3) emphasizing hierarchical structures and third normal form divert the analyst’s attention from analysis to implementation, (4) an explicit representation of relationships is necessary, (5) peer review is useful in improving selection of objects and methods to support end-user processes, and (6) supporting a standard document from OOA products is not easy.

The problem of database normalization in a parallel environment is examined. Generating relation schemes in third normal form is straightforward when given a set of functional dependencies that is a reduced cover. It is shown that a reduced cover for a set of functional dependencies can be produced in parallel. The correctness of the algorithm is based on two important theorems. it is demonstrated that the companion third normal form algorithm can be easily translated into a parallel version. The performance of the two algorithms is compared to the performance of their serial counterparts. The standard serial algorithms for computing minimal covers and synthesizing third normal form relations are presented. The parallel algorithms and their rationale are discussed. >

This paper is about designing a complete interactive tool, named JMathNorm, for relational database (RDB) normalization using Mathematica. It is an extension of the prototype developed by the same authors [1] with the inclusion of Second Normal Form (2NF), and Boyce-Codd Normal Form (BCNF) in addition to the existing Third normal Form (3NF) module. The tool developed in this study is complete and can be used for real-time database design as well as an aid in teaching fundamental concepts of DB normalization to students with limited mathematical background. JMathNorm also supports interactive use of modules for experimenting the fundamental set operations such as closure, and full closure together with modules to obtain the minimal cover of the functional dependency set and testing an attribute for a candidate key. JMathNorm's GUI interface is written in Java and utilizes Mathematica's JLink facility to drive the Mathematica kernel.

This paper presents a new method for learning Bayesian networks from functional dependencies (FD) and third normal form (3NF) tables in relational databases. The method sets up a linkage between the theory of relational databases and probabilistic reasoning models, which is interesting and useful especially when data are incomplete and inaccurate. The effectiveness and practicability of the proposed method is demonstrated by its implementation in a mobile commerce system.

Classical data dependencies are oblivious to important constraints which may exist between sets of attributes occurring in different relation schemes. The authors study how inclusion dependencies can be used to model these constraints, leading to the design of better database schemes. A normal form called the inclusion normal form (IN-NF) is proposed. Unlike classical normal forms, the IN-NF characterizes a database scheme as a whole rather than the individual relation schemes. It is shown that a database scheme in IN-NF is always in improved third normal form, while the converse is not true. It is demonstrated that the classical relational design framework may be extended to facilitate the design of database schemes in IN-NF. >

In Ref. 8, we introduced a simplifying assumption about entity-relationship diagrams (ERDs), called regularity, and showed that regular ERDs have several desirable properties. One such property is that every relation schema in the ERD's canonical relational scheme can be put into Third Normal Form. We left open there the more basic question: under what conditions would the original relation schemas actually be in Boyce-Codd Normal Form (BCNF)? Since the visible semantics of ERDs determine naturally their associated functional dependencies (fd's), it is important to know when an ERD, as designed, already has this strongest normal form given purely in terms of fd's. We show here a sufficient diagrammatic condition (loop-free) under which a regular ERD will have databases enjoying the benefits of BCNF.

This paper addresses relational database design using the concept of functional dependencies (FDs). The classical synthesis approach processes a given set of functional dependencies to produce one minimal cover. This cover is then used to develop a relational schema; however, a given set of FDs may have more than one minimal cover. In turn, different minimal covers may give rise to different relational schemata. An enhancement is proposed to the traditional synthesis algorithm that aids in efficiently determining all minimal covers for a given set of functional dependencies. We have implemented a tool called SYNTHESIZER that uses the modified synthesis algorithm to produce relations in Third Normal Form. SYNTHESIZER not only preserves dependencies, but also enforces the lossless join property. SYNTHESIZER has been implemented in Turbo Pascal to operate on IBM-PC compatibles. Expert design heuristics have been incorporated into this tool. The tool supports the requirements collection, conceptual and logical design phases of database design. SYNTHESIZER has been extensively validated by designers in more than 10 different database design projects.

We investigate the question of when two entity-relationship diagrams (ERD's) should be considered equivalent, in the sense of representing the same information. This question is very important for a database design process which uses the ERD model, and can be interpreted in various ways. We give three natural and increasingly stricter criteria for developing concepts of equivalence for ERD's. We first give a notion of "domain data compatibility" which ensures that the ERD's in question represent the same universe of data in an aggregate sense. Then we define the set of functional dependencies which are naturally embedded in each ERD, and use it to develop a concept of "data dependency equivalence" which ensures that the ERD's satisfy the same constraints (functional dependencies) among the represented data. Finally, we give our strongest criterion, instance data equivalence, which requires the ERD's to have the same power to represent instances of data. We develop several alternate forms of this third notion, including some giving efficient tableaux tests for its occurrence. Indeed, for each type of equivalence, we give a polynomial-time algorithm to test for it.

Identification and representation of entities and their relationships relevant to an application are some of the key problems in logical data base design. This paper presents an approach to synthesizing logical segments that are representations of such entities and relationships. The major steps in this design are 1) collect all the pertinent functional relations in the application domain; 2) remove redundant relations to obtain a minimal covering set; 3 ) minimize the number of relations in the covering set to obtain an optimal set of relations in the third normal form; and 4) combine relations into logical segments according to prescribed performance requirements and projected information maintenance activities. Synthesis of logical segments for an airline reservations application is used as an illustrative example.

Aggregation is introduced as an abstraction which is important in conceptualizing the real world. Aggregation transforms a relationship between objects into a higher-level object. A new data type, called aggregate, is developed which, under certain criteria of “well-definedness,” specifies aggregation abstractions. Relational databases defined as collections of aggregates are structured as a hierarchy of n-ary relations. To maintain well-definedness, update operations on such databases must preserve two invariants. Well-defined relations are distinct from relations in third normal form. It is shown that these notions are complementary and both are important in database design. A top-down methodology for database design is described which separates decisions concerning aggregate structure from decisions concerning key identification. It is suggested that aggregate types, and other types which support real-world abstractions without introducing implementation detail, should be incorporated into programming languages.

In this paper, we propose the application of formal methods to Software Engineering. The most used data model is the relational model and we present, within the general framework of lattice theory, this analysis of functional dependencies. For this reason, we characterize the concept of f-family by means of a new concept which we call non-deterministic ideal operator (nd.ideal-o). The study of nd.ideal-o.s allows us to obtain results about functional dependencies as trivial particularizations, to clarify the semantics of the functional dependencies and to progress in their efficient use, and to extend the concept of schema. Moreover, the algebraic characterization of the concept of Key of a schema allows us to propose new formal definitions in the lattice framework for classical normal forms in relation schemata. We give a formal definition of the normal forms for functional dependencies more frequently used in the bibliography: the second normal form (2FN), the third normal form(3FN) and Boyce–Codd's normal form (FNBC).

An algorithm is presented that finds K, the set of all keys for a given set A of attribute names and a given set D[0] of functional dependencies, in time polynomial in |A|, |D[0]| and |K|. It is shown that the problem of deciding whether or not there is a key having cardinality not greater than a specified integer is NP-complete. It is also shown that the problem of deciding whether or not a specified attribute name is prime is NP-complete.

The increased administrative burden being placed upon the Fleet increasingly affects ship performance and personnel morale and retention. The Shipboard Non-tactical ADP Program (SNAP) is being instituted in order to alleviate these burdens. However, the "applications approach" being used with SNAP is not sufficient to meet both the functional and management needs of the Fleet. The management environment necessary to satisfy both these needs are discussed. The central theme is that of centralization and standardization of data, its definition, and its control. Fundamental to the above philosophy is the concept of Information Resource Management (IRM). Automation of IRM should be done via a Data Base Management System (DBMS). The critical tool required to transfer IRM results to a DBMS is the Data Dictionary System (DDS). Additionally, two crucial management positions, the IRM manager and the Data Base Administrator (DBA) are essential to the success of the "data base approach". http://archive.org/details/managementprinci1094520249 Lieutenant, United States Navy Approved for public release; distribution is unlimited.