Search

We establish a principled schema design framework for data with missing values. The framework is based on the new notion of an embedded functional dependency, which is independent of the interpretation of missing values, able to express completeness and integrity requirements on application data, and capable of capturing redundant data value occurrences that may cause problems with processing data that meets the requirements. We establish axiomatic, algorithmic, and logical foundations for reasoning about embedded functional dependencies. These foundations enable us to introduce generalizations of Boyce-Codd and Third normal forms that avoid processing difficulties of any application data, or minimize these difficulties across dependency-preserving decompositions, respectively. We show how to transform any given schema into application schemata that meet given completeness and integrity requirements, and the conditions of the generalized normal forms. Data over those application schemata are therefore fit for purpose by design. Extensive experiments with benchmark schemata and data illustrate the effectiveness of our framework for the acquisition of the constraints, the schema design process, and the performance of the schema designs in terms of updates and join queries.

This article is about automated algorithm that analyzes the structure of reporting documentation from local educational organizations that provide primary and secondary education. Many types of school’s documentation are not standardized. Because of that, there is a need to develop a solution that could match many kinds of table data from reporting documentation and create an appropriate database structure in third normal form (3NF) with a view to further analysis by local education department’s managers.

Relational database normalization is a formal data organization process that seeks to make the database more flexible by eliminating data redundancy and inconsistencies. Informally, a relational database relationship is often described as "normalized" if it conforms to the third normal form. Most relationships in 3NF are free of insert, update, and delete anomalies. In this work the design of a normalization assistant is presented. The purpose of the presented proposal is to support the teaching and learning process of relational database normalization, making the user take his universal data table to third normal form in an agile and simple way.

We present new algorithms to compute candidate keys and third normal form design of a relational database schema, using strategic port graph rewriting. More precisely, we define port graph rewriting rules and strategies that implement a candidate key definition and Ullman’s algorithm to decompose a relation schema into lossless 3NF schemata. We show the correctness of the resulting database schema by proving soundness, completeness and termination of our strategic graph programs. These rules and strategies provide a declarative and visual description of the algorithms, and permit a fine-grained analysis of the computation steps involved in the normalisation process. The algorithms have been implemented in Porgy, a visual, interactive modelling tool.

The task of designing relational databases has always been the subject of scientific research, as it is associated with a number of interrelated steps. The result of each step is the development of models for presenting the future database with further refinement and, finally, the creation of an adequate relational database as a set of relations with the corresponding links between them. The article focuses on the normalization of databases, as one of the steps to create a datalogical model, namely, the use of the first three Normal Forms. As a result of the analysis carried out in the article, it was concluded that the definition of the Second Normal Form can be modernized and thus achieve two goals: to ensure the correct creation of potential primary keys and, thereafter, the correct external connections between relations, even before creating the data schema in a specific relational database. Moreover, to reconsider the necessity of applying the so-called “strengthened” or a higher version of the Third Normal Form, which speaks of mutual dependencies between key and non-key attributes.

Government WeChat matrix, which has played an important role in the openness of government affairs, public opinion supervision and public services, is one of the main forms of e-government in contemporary China. We took prefecture-level city WeChat public account as the core research object, analyzed the matrix operation mode of government affairs WeChat public account, and proposed a star matrix model. In the meantime, we also designed the corresponding information management system, using first normal form and third normal form mixed database design mode, using dynamic generated static web page as the front-end user interface, to ensure the stability and security of the system, as far as possible to reduce the waiting time for system access, improve the efficiency of implementation. This matrix structure construction and information system implementation method proposed in this paper has certain reference value for the research of related fields.

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.

The purpose of the article is to develop a method for reengineering relational databases, taking into account the presence of implicit interrelated functionally dependent data that affect the structure of the logical model. The following results are obtained: the article proposes an approach to detecting previously unknown functional dependences, based on the analysis of a set of relational database. Classes of relational databases reengineering problems are singled out; the stage of forming the target logical scheme, common to the problems of adaptation and refactoring, is investigated. The sub-task of verification of the relational database logical scheme correspondence to the third normal form within the framework of this stage is considered using the synthesis method; it is shown that its solution involves a number of difficulties, in particular, the need to find the set of functional dependences being performed using the current data instance of some relational database. An approach is proposed for finding a set of functional dependencies from the relational structure data instance. As a direction for further research, one can highlight the implementation of empty values support at the stage of detection of functional dependences, as well as issues of data transfer without loss from the original structure of the database to the target one, obtained as a result of applying the reengineering methods.

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.

This paper compares different levels of database normalization process in terms of anomalies removal and storage reduction. Several databases have been normalized up to Third Normal Form (1NF, 2NF and 3NF) in order to investigate the influence of the normalization on the database performance. They are implemented separately with different database systems such as MS Access, SQL Server and Oracle. The percentage of storage reduction and data anomalies are investigated for every normal form and database system. The results show that the data storage is significantly reduced over unnormalized database, approximately between 20 to 30% for 1NF flattening tables and 1NF decomposing table, and between (15% - 22%) and (9% - 22%) for 2NF and 3NF, respectively. The removal of the majority of anomalies is observed in the first normal form while fewer anomalies are removed in the next higher normal forms. For the same database implemented, the comparison between three different database systems shows approximately the same results with slight differences. These differences may be due to the nature, the size of the constraints and metadata on each database system.

The library database design needs to accord certain rules, in relational database, this rule is paradigm. Paradigm is in line with a certain level of relational schema collections. Relational database relationship must meet certain requirements, namely to meet the different paradigms. At present, there are six kinds of relationship database paradigm: the first normal form (1NF), the second normal form (2NF), the third normal form (3NF), BC normal form (BCNF), the fourth normal form (4NF), the fifth normal form (5NF) and the sixth Normal Form (6NF). The 1NF is the minimum paradigm for requirement. Basing on the 1NF, further meeting more requirements is the 2NF and a higher level paradigm, in practical design application, you only need to reach the 3NF.

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

Normalisation discusses the traditional normalisation approach to database design — if only because its terminology is required knowledge for anyone who uses databases. This decompositional approach typically begins with a set of business documents that present views of the database. These views become potential table schemas. The potential schemas are examined for redundancies, such as transitive, partial, and Boyce-Codd dependencies. The appendix describes algorithms that remove them and yield 3rd normal form schemas.

This chapter covers the process of transforming an ER diagram into a well-designed relational database. For each normal norm, the chapter presents the rules that relations must meet to reach that normal form, and the design problems that may remain. It also covers the process for transforming relations into higher normal forms, including relational algebra operations, where appropriate.

The traditional relational database model may be extended into a fuzzy database model based on the mathematical framework of fuzzy set theory to process imprecise or uncertain information. While designing such a fuzzy relational database model that does not suffer from data redundancy and anomalies, the present authors have defined several fuzzy normal forms in ref [1]. However, as one decomposes an unnormalized relation into a desired normal form, it should also satisfy the essential properties of dependency preservation and lossless join of relation schemes which take a significant role in the design theory of a relational database. We have concentrated on these two important issues in this paper and have designed algorithms that confirm dependency preservation and lossless join decomposition of an unnormalized relation into the fuzzy third normal form or fuzzy Boyce Codd normal form. The algorithms have been tested and validated with examples.

The proliferation of Windows-based programs for PCs, together with the requirement of many business managers for faster responses to their information needs, has led many business end-users to create, maintain, and query their own databases. These individuals use the output of these queries as the basis for operational, tactical, and strategic decisions. To maximize the benefit of end-users' time, querying these databases must be as efficient as possible. Of even greater importance, the effectiveness of managers' decision-making is directly related to the quality of the information extracted. Because end-user querying is error prone, characterizing the sources of query errors and using that knowledge to improve the effectiveness of end-user query development can improve the quality of information available for decision-making. IS professionals typically design databases in third normal form. End-user databases designed with the help of IS professionals are also likely to be in third normal form. Although third normal form is better for data capture, prior research indicates third normal form is not necessarily the most appropriate normal form for querying. This paper reports the results of an in-depth experiment into the effects of normalization level on the efficiency and effectiveness of end-user querying. The results confirm earlier findings that end-users querying first normal form data structures were both more efficient and more effective than those querying third normal form data structures. This research extends prior research by examining the specific areas where first normal end-users outperform third normal form end-users. In particular, the experiment revealed that first normal form end-users made significantly fewer errors in relation to attribute selection, table selection, and row restriction.

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.

As a result of the shortage of professional programmers to extract timely information from databases, end-users are increasingly developing their own database queries. Because end-user querying is error-prone, characterizing the sources of query errors and using that knowledge to improve the effectiveness of end-user query development can improve the quality of information used for decision making. This paper reports the results of an experiment that investigated the effect of normalization level on query errors. The results show that query errors vary with the normalization level of the database structure and confirm previous findings about query errors increasing with task complexity. End-users querying a first normal form data structure make fewer errors than end-users querying an unnormalized data structure or a third normal form data structure. Furthermore, end-users querying a third normal form data structure make fewer errors than end-users querying an unnormalized data structure.

Although there has been a vast amount of research in the area of relational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satifies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If F only satisfies the intersection property then this problem is NP-complete, as in the general case. Moreover, we show that when F either satisfies the intersection property or the split-freeness property then deciding whether an attribute is prime can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. Assume that a relation schema R is an appropriate normal form with respect to a set of FDs F. We show that when F satisfies the intersection property then the notions of second normal form and third normal form are equivalent. We also show that when R is in Boyce-Codd Normal Form (BCNF), then F is monodependent if and only if either there is a unique key for R, or for all keys X for R, the cardinality of X is one less than the number of attributes associated with R. Finally, we tackle a long-standing problem in relational database theory by showing that when a set of FDs F over R satisfies the intersection property, it also satisfies the split-freeness property (i.e., is monodependent), if and only if every lossless join decomposition of R with respect to F is also dependecy preserving. As a corollary of this result we are able to show that when F satisfies the intersection property, it also satisfies the intersection property, it also satisfies the split-freeness property(i.e., is monodependent), if and only if every lossless join decomposition of R, which is in BCNF, is also dependency preserving. Our final result is that when F is monodependent, then there exists a unique optimum lossless join decomposition of R, which is in BCNF, and is also dependency preserving. Furthermore, this ultimate decomposition can be attained in polynomial time in the size of F.

Several approaches have been proposed for the generation of application ontologies from relational databases. Most of these approaches, propose a fully automatic process based on unrealistic assumption, where the input database is well designed, up-to the third normal form (3NF). Real-World databases may contain irrelevant, missing or erroneous information to the ontology learning process. Preparing databases before ontology learning is quite rare. We propose in this paper a methodology for Database Preparation (DBP), composed of three sub-processes: the extraction of a Business Database (BDB), the cleaning of the BDB, and the enrichment of the cleaned BDB. A proof-theoretical case study shows that the proposed methodology is feasible and useful.

The purpose of good database logical design is to eliminate data redundancy and isertion and deletion anomalies. In order to achieve this objective for temporal databases, the notions of temporal types , which formalize time granularities, and temporal functional dependencies (TFDs) are intrduced. A temporal type is a monotonic mapping from ticks of time (represented by positive integers) to time sets (represented by subsets of reals) and is used to capture various standard and user-defined calendars. A TFD is a proper extension of the traditional functional dependency and takes the form X → μ Y, meaning that there is a unique value for Y during one tick of the temporal type μ for one particular X value. An axiomatization for TFDs is given. Because a finite set TFDs usually implies an infinite number of TFDs, we introduce the notion of and give an axiomatization for a finite closure to effectively capture a finite set of implied TFDs that are essential of the logical design. Temporal normalization procedures with respect to TFDs are given. Specifically, temporal Boyce-Codd normal form (TBCNF) that avoids all data redundancies due to TFDs, and temporal third normal form (T3NF) that allows dependency preservation, are defined. Both normal forms are proper extensions of their traditional counterparts, BCNF and 3NF. Decompositition algorithms are presented that give lossless TBCNF decompositions and lossless, dependency-preserving, T3NF decompositions.

This paper is intended to present an application system which can facilitate users in converting from Excel spreadsheet to database structure by using data normalization technique. It provides users with an automated system that can develop a database in its third normal form (3NF) from an Excel spreadsheet. There are two major problems of Excel spreadsheet that are emphasized in this project which are data redundancy and update anomaly. Prototyping-based methodology is used in order to develop this system. The system just creates the SQL codes for creating the database structure and populating the database; however, how the users make use of it such as interface for database interaction is not covered at this stage of project. Based on its functionalities, accuracy and performance, this system is able to bring more benefit and convenience for its users.

Relational model is the most essential database model for decades and is examined in various ways. A very important concept in the relational modeling is the concept of dependencies. Particularly a set of functional dependencies and its equivalent minimal cover are discussed here for synthesizing third normal form relations. A traditional synthesis algorithm have been used to reduce the set of functional dependencies, F, into an equivalent minimal cover. This cover is then used to develop a relational schema; however, a given set of functional dependencies may have more than one minimal covers. In turn, different minimal covers may give rise to different relational schema. Database designers had already been agreed upon the use of popular inference rules of Armstrong to obtain minimal covers from the set F of functional dependencies. Despite the frequent use of the traditional synthesis algorithm, there is still a lack of formality and simplicity support in that algorithm to produce a minimum cover, especially; the step(s) of the algorithm in which the set of functional dependencies of F are used to make left-irreducible remain informal. In this paper, an extension is proposed to the synthesis algorithm that aids in to produce an optimal minimal cover more systematically from the given set of functional dependencies. The optimal minimal cover obtained by this extension would be appropriate for synthesizing third normal form relational schema from the universal 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.

This paper proposes a new line-based approach for the detection of code clones using syntactic and lexical information. A customized compiler writes a source code representation that contains syntactic and lexical information. A new clone detection tool called LePalex reads the source code representation, and converts it to three types of code: first normal form, second normal form, and third normal form. The first normal form is used to detect the exact match of code clones. The second normal form is used to detect the syntactic match of code clones. The third normal form is used to check for syntactically correct segments of code clones. This paper demonstrates the advantage of this approach in achieving programming language independence using syntactic and lexical information.

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.

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

Logic data modeling is a set of procedures that examines an entity to ensure that its component attributes (data elements) should reside in that entity, rather than being stored in another or new entity. Therefore, LDM focuses solely on the stored data model. The LDM process is somewhat controversial and subject to various opinions; however, listed below are the common steps used by many professionals in the industry: 1. identify major entities 2. select primary and alternate keys 3. determine key business rules 4. apply normalization to 3rd normal form 5. combine user views 6. integrate with existing models (legacy interfaces) 7. determine domains and triggering operations 8. de-normalize carefully

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.

It is shown that it is possible to automatically generate all valid answers to a query on a relational data base such that the user need not be aware of the relations used to form the answer, but can express queries simply in terms of attribute names. If the data base is in a covering, reconstructible Codd third normal form, then algorithms can be given to generate the data base joins necessary to answer such a query.

If it has been said once, it has been said a million times: “This database is in the Third Normal Form, and that is good enough!” In this chapter, you’ll look at one additional very important method for normalization, and you’ll be introduced to a few others. The additional methods of normalization aren’t commonly used because of perceived drawbacks in terms of both the time taken to implement them, and the cost in performance of the resulting database. In the previous chapter, you looked at some of the different programming anomalies that the Third Normal Form deals with, but as you’ll see, there may still be some problems remaining in your logical design, mostly caused by the presence of nonbinary relationships. In essence, while most people think they have completed the normalization process after having reached the Third Normal Form, what they really should be concerned with is at least reaching the Third Normal Form in their logical model. A degree of judgment is required in physically implementing a design and determining what level of normalization is appropriate. However, as a general guide, the designer should always attempt to normalize all entities to as high a form as possible.

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

Logical data modeling is a set of procedures that examines an entity to ensure that its component attributes (data elements) should reside in that entity rather than be stored in another or new entity. Therefore, LDM focuses solely on the stored data model. The LDM process is somewhat controversial and subject to various opinions; however, listed below are the common steps used by many professionals in the industry: 1. identify major entities; 2. select primary and alternate keys; 3. determine key business rules; 4. apply normalization to 3rd normal form; 5. combine user views; 6. integrate with existing models (legacy interfaces); 7. determine domains and triggering operations; 8. de-normalize carefully.

The identification and searching problems are because of the fact that some information repeats for a given programmer: a programmer has many skills and this causes the programmer information to be repeated for each such skill. Such repeated information is called a “repeating group.― To avoid the problems, one should avoid repeating groups. When tables contain no repeating groups any more, they are in first normal form. “First normal form― is a basic requirement of the relational model. Tables that are in first normal form and in which all attributes depend on the whole key, are in “second normal form.― Tables that are in second normal form and in which all attributes depend only on the key or upon an alternate key, are in “third normal form.― “Fourth normal form― is a problem only for relations that are all key. If such relations have attributes, then either the attribute depends on the whole key, and the table is in fourth normal form, or the attribute does not depend on the whole key so that the table is not in second normal form and must be split according to that criterion. When anomalous tables have been split as indicated, they are in “fifth normal form.―

In order to eliminate redundant information in a database one usually uses decomposition or special database design methods to achieve Third Normal Form (or some other normal form like Boyce-Codd Normal Form). This method of database design assumes that the real world satisfies very strong constraints like functional dependencies (fds), without any exceptions. Most databases in "Whatever" Normal Form still contain a large amount of duplicated information, because the real world satisfies very few constraints, but a lot of "almost" constrains. Horizontal Fragments (resulting from Horizontal Decomposition) can be used to separate information with different properties. The different constraints that hold in these fragments can be used to eliminate redundant information in the fragments. We focus on the horizontal decomposition for eliminating exceptions to fds. We show how to update such horizontally decomposed databases in an efficient way. Generating separate horizontal fragments for all desired fds that do not hold in the real world may not be possible (although for every fd there will be a fragment for its exceptions, but the fragments for a number of fds may coincide). The number of fds for which a separate exception fragment can be generated depends on the choice of fds and the order in which they are used. We show that it is possible to find (in polynomial time) the order which leads to the "optimal" decomposition of a relation into horizontal fragments.

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.

A new type of dependency, which includes the well-known functional dependencies as a special case, is defined for relational databases. By using this concept, a new (“fourth”) normal form for relation schemata is defined. This fourth normal form is strictly stronger than Codd's “improved third normal form” (or “Boyce-Codd normal form”). It is shown that every relation schema can be decomposed into a family of relation schemata in fourth normal form without loss of information (that is, the original relation can be obtained from the new relations by taking joins).

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.

In a multiattribute relation or, equivalently, a multicolumn table a certain collection of the projections can be shown to be independent in much the same way as the factors in a Cartesian product or orthogonal components of a vector. A precise notion of independence for relations is defined and studied. The main result states that the operator which reconstructs the original relation from its independent components is the natural join, and that independent components split the full family of functional dependencies into corresponding component families. These give an easy-to-check criterion for independence.

A new method for computing minimal covers is presented using a new type of closure that allows significant reductions in the number of closures computed for normalizing relations. Benchmarks are reported comparing the new and the standard techniques.

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.