Justification for inclusion dependency normal form

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. In this paper, we address the issue of normalization in the presence of FDs and INDs and, in particular, the semantic justification for an inclusion dependency normal form (IDNF), which combines the Boyce-Codd normal form with the restriction on the INDs that they be noncircular and key-based. We motivate and formalize three goals of database design in the presence of FDs and INDs: noninteraction between FDs and INDs, elimination of redundancy and update anomalies, and preservation of entity integrity. We show that (as for FDs), in the presence of INDs, being free of redundancy is equivalent to being free of update anomalies. Then, for each of these properties, we derive equivalent syntactic conditions on the database design. Individually, each of these syntactic conditions is weaker than IDNF and the restriction that an FD is not embedded in the right-hand side of an IND is common to three of the conditions. However, we also show that, for these three goals of database design to be satisfied simultaneously, IDNF is both a necessary and a sufficient condition     

Polynomial Tests of Normal Forms and Some Related Results

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

Dependency-preserving normalization of relational and XML data

Having a database design that avoids redundant information and update anomalies is the main goal of normalization techniques. Ideally, data as well as constraints should be preserved. However, this is not always achievable: while BCNF eliminates all redundancies, it may not preserve constraints, and 3NF, which achieves dependency preservation, may not always eliminate all redundancies. Our first goal is to investigate how much redundancy 3NF tolerates in order to achieve dependency preservation. We apply an information-theoretic measure and show that only prime attributes admit redundant information in 3NF, but their information content may be arbitrarily low. Then we study the possibility of achieving both redundancy elimination and dependency preservation by a hierarchical representation of relational data in XML. We provide a characterization of cases when an XML normal form called XNF guarantees both. Finally, we deal with dependency preservation in XML and show that like in the relational case, normalizing XML documents to achieve non-redundant data can result in losing constraints.     

Identifying extended entity-relationship object structures inrelational schemas

Relational schemas consisting of relation-schemes, key dependencies and key-based inclusion dependencies (referential integrity constraints) are considered. Schemas of this form are said to be entity-relationship (EER)-convertible if they can be associated with an EER schema. A procedure that determines whether a relational schema is EER-convertible is developed. A normal form is proposed for relational schemas representing EER object structures. For EER-convertible relational schemas, the corresponding normalization procedure is presented. The procedures can be used for analyzing the semantics of existing relational databases and for converting relational database schemas into object-oriented database schemas     

消除结构冗余的XML数据库模式规范化设计

XML数据库模式规范化设计是给出一个能很好地表示数据间依赖关系并消除了冗余的XML模式或DTD的集合．目前这一领域的研究并没有对XML数据库模式中的数据依赖和冗余进行专门的分析．引人标识符分别表示XML模式中的元素和属性，分析XML数据库模式的结构冗余：局部冗余、传递冗余和不规则；并在此基础上，定义XML数据库模式第3范式(3NF)，给出并验证其规范化设计算法．     

一种理性的数据库模式设计方法--范式方法

介绍了一种理论性较强的数据库模式设计方法———范式方法。范式方法基于函数依赖及范式理论。最终的数据库模式必须满足BCNF模式集或3NF模式集、无损联接和保持函数依赖这三个特性才是一个可用的数据库,才不会出现各种操作异常(插入、删除)并且能大大地减少数据冗余。     

具有多时间粒度的时态数据库初等关键字、简单范式分解问题研究

一个好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异常．对于时态数据库也是如此．提出了时态初等函数依赖、时态初等关键字、时态简单关键字等概念,在此基础上利用具有多时间粒度的时态函数依赖（TFD）约束对时态数据库进行了规范化研究,提出了规范程度高于时态三范式低于时态Boyce—Code范式的时态初等关键字范式（TEKNF）及时态简单范式（TSNF）,并研究了时态初等关键字范式和时态简单范式的分解问题,给出了相关分解算法,并对算法的可终止性、正确性进行了证明,对时间复杂度进行了分析．     

Micro: A normalization tool for relational database designers

Normalization is a major task in relational database design. Although normalization algorithms have been developed, very few commercial design tools are available to assist the normalization satisfactorily. In this paper, we present a prototype system Micro for automatic normalization. We have developed a simple algorithm for 2NF normalization, and used the abstract algorithms reported in the literature for 3NF and BCNF normalization. We employ efficient data structures on functional dependencies and relation schemes to improve the performance of these algorithms. Micro enforces a certain fixed order among functional dependencies to deal with the non-deterministic feature that is associated with the original algorithms. Micro provides a windowing user interface through which the database designer can specify functional dependencies easily and generate real normalized tables. Through Micro, we wish to demonstrate that the automation of normalization is practical.     

NF-NR: A practical normal form for nested relations

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

Propagating XML constraints to relations

We present a technique for refining the design of relational storage for XML data. The technique is based on XML key propagation: given a set of keys on XML data and a mapping (transformation) from the XML data to relations, what functional dependencies must hold on the relations produced by the mapping? With the functional dependencies one can then convert the relational design into, e.g. 3NF, BCNF, and thus develop efficient relational storage for XML data. We provide several algorithms for computing XML key propagation. One algorithm is to check whether a functional dependency is propagated from a set of XML keys via a predefined mapping; this allows one to determine whether or not the relational design is in a normal form. The others are to compute a minimum cover for all functional dependencies that are propagated from a set of XML keys and hold on a universal relation; these provide guidance for how to design a relational schema for storing XML data. These algorithms show that XML key propagation and its associated minimum cover can be computed in polynomial time. Our experimental results verify that these algorithms are efficient in practice. We also investigate the complexity of propagating other XML constraints to relations. The ability to compute XML key propagation is a first step toward establishing a connection between XML data and its relational representation at the semantic level.     

多时间粒度约束的时态简单范式的分解

数据库逻辑设计的目的是消除数据冗余、插入和删除异常。为使时态模式满足某种范式的要求，要对时态模式进行分解，保持函数依赖和无损连接性是对算法最基本的要求。但对具有多时间粒度的时态模式进行分解时，把TBCNF作为最终目标很难实现保持函数依赖性，把T3NF作为最终目标，又很难达到规范化要求。该文提出了时态简单范式TSNF的概念及相应的分解算法，来弥补以上两点不足。     

Compact scheme forests in nested normal form

In the context of data base design for nested relational structures, update anomalies can be avoided if the nested scheme forest composed of scheme trees is in nested normal form (NNF) with respect to the associated set of data dependencies. In practice, minimizing the number of normal scheme trees in the nested scheme forest, which is in NNF, will also be an important design goal. This is because the number of computationally expensive join operations that are required in order to answer a given query is related to the number of normal scheme trees that must be used in the query expression.

We prove that the problem of finding a succinct NNF scheme forest is NP-complete for a subclass of the class of split-free sets of multivalued dependencies.     

Extracting a largest redundancy-free XML storage structure from an acyclic hypergraph in polynomial time

Given a hypergraph and a set of embedded functional dependencies, we investigate the problem of determining the conditions under which we can efficiently generate redundancy-free XML storage structures with as few scheme trees as possible. Redundancy-free XML structures guarantee both economy in storage space and the absence of update anomalies, and having the least number of scheme trees requires the fewest number of joins to navigate among the data elements. We know that the general problem is intractable. The problem may still be intractable even when the hypergraph is acyclic and each hyperedge is in Boyce–Codd normal form (BCNF). As we show here, however, given an acyclic hypergraph with each hyperedge in BCNF, a polynomial-time algorithm exists that generates a largest possible redundancy-free XML storage structure. Successively generating largest possible scheme trees from among hyperedges not already included in generated scheme trees constitutes a reasonable heuristic for finding the fewest possible scheme trees. For many practical cases, this heuristic finds the set of redundancy-free XML storage structures with the fewest number of scheme trees. In addition to a correctness proof and a complexity analysis showing that the algorithm is polynomial, we also give experimental results over randomly generated but appropriately constrained hypergraphs showing empirically that the algorithm is indeed polynomial.     

Exploring into programs for the recovery of data dependenciesdesigned

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

具有全序时态类型集时态函数依赖集的研究

好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异常.对于时态数据库,可以通过具有多时间粒度的时态函数依赖(TFDs)约束对时态数模式进行规范化.但是由于时间维的引入和多时间粒度的使用而给数据库设计带来巨大的复杂性.一般来说,系统所能处理的和相当多的应用所涉及到的时态类型集满足全序关系,并且具有全序时态类型集的TFD集的推导规则与传统函数依赖(FDs)的Armstrong公理有着紧密的联系.通过分析TFDs与FDs之间存在的联系,利用传统FD集的相应算法,提出了成员籍、有限属性闭包等TFD集的一些重要算法.这些算法是时态数据库进一步规范化的基础.     

Investigating a domain-key scheme of a relational database

A new approach to the synthesis of the domain-key normal form (DK/NF) for an arbitrary domain is used to analyze some criticized publications. A detailed comparison between various anomalies in database schemas, between different approaches to the design of schemas, and between the framework design method and classical and new design methods is made. The coincidence with the results of other studies is shown to be a subsequence of the strict soundness of the method proposed.     

A comparative study of various nested normal forms

As object-relational databases (ORDBs) become popular in the industry, it is important for database designers to produce database schemes with good properties in these new kinds of databases. One distinguishing feature of an ORDB is that its tables may not be in first normal form. Hence, ORDBs may contain nested relations along with other collection types. To help the design process of an ORDB, several normal forms for nested relations have recently been defined, and some of them are called nested normal forms. In this paper, we investigate four nested normal forms, which are NNF [20], NNF [21], NNF [23], and NNF [25], with respect to generalizing 4NF and BCNF, reducing redundant data values, and design flexibility. Another major contribution of this paper is that we provide an improved algorithm that generates nested relation schemes in NNF [20] from an a-acyclic database scheme, which is the most general type of acyclic database schemes. After presenting the algorithm for NNF [20], the algorithms of all of the four nested normal forms and the nested database schemes that they generate are compared. We discovered that when the given set of MVDs is not conflict-free, NNF [20] is inferior to the other three nested normal forms in reducing redundant data values. However, in all of the other cases considered in this paper, NNF [20] is at least as good as all of the other three nested normal forms     

复杂对象嵌套结构的规范化

本文将关系模型中的函数依赖、多值依赖、规范化等概念扩展到具有嵌套结构的复杂对象模型,并在函数依赖和多值依赖中融进了实体联系的语义,给出了规范化的方法和步骤.在最后的范式中,不存在不完全嵌套,在嵌套结构的每一层上,仅存在单属性的关键字,相当于关系模型中的BCNF范式.这样的范式可消除冗余,避免更新异常,提高查询效率,保证嵌套结构可简洁而正确地表达实体联系,且不存在平面式的联系类.     

Approximate dependencies in database systems

Functional dependencies are the most commonly used approach for capturing real-word integrity constraints which are to be reflected in a database. There are, however, many useful kinds of constraints, especially approximate ones, that cannot be represented correctly by functional dependencies and therefore are enforced via programs which update the database, if they are enforced at all. This tends to make such constraints invisible since they are not an explicit part of the database, increasing maintenance problems and the likelihood of inconsistencies. We propose a new approach, cluster dependencies, as a way to enforce approximate dependencies. By treating equality as a fuzzy concept and defining appropriate similarity measures, it is possible to represent a broad range of approximate constraints directly in the database by storing and accessing cluster definitions. We discuss different interpretations of cluster dependencies and describe the additional data structures needed to enforce them. We also contrast them with an existing approach, fuzzy functional dependencies, which are much more limited in the kind of approximate constraints they can represent.     

The theory of functional and subset dependencies over relational expressions

A formal system for reasoning about functional dependencies (FDs) and subset dependencies (SDs) defined over relational expressions is described. An FD e:X → Y indicates that Y is functionally dependent on X in the relation denoted by expression e; an SD e ? f indicates that the relation denoted by e is a subset of that denoted by f. The system is shown to be sound and complete by resorting to the analytic tableaux method. Applications of the system include the problem of determining if a constraint of a subschema is implied by the constraints of the base schema and the development of database design methodologies similar to normalization.