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     

关于传递闭包和函数依赖完备公理系统存在问题研究

数据依赖在数据库设计中起着十分重要的作用．自Ｃｏｄｄ提出函数依赖（ＦＤｓ）、Ｆａｇｉｎ引入多值依赖（ＭＶＤｓ）后，近几年来人们又根据设计中的需要引入多种新的依赖，如在工程数据库设计中所引进的传递闭包依赖（ＣＤｓ）等．对这些依赖一般是按其是否具有完备的公理系统而划分为两大类，因为完备性公理系统往往具有有效的判定算法为先决条件．本文对ＣＤｓ和ＦＤｓ的ｋ元完备公理系统存在问题进行了研究，证明了ＣＤｓ和ＦＤｓ不具有共同的ｋ元完备公理系统这一结论．     

Semantic sampling of existing databases through informative Armstrong databases

Functional dependencies (FDs) and inclusion dependencies (INDs) convey most of data semantics in relational databases and are very useful in practice since they generalize keys and foreign keys. Nevertheless, FDs and INDs are often not available, obsolete or lost in real-life databases. Several algorithms have been proposed for mining these dependencies, but the output is always in the same format: a simple list of dependencies, hard to understand for the user. In this paper, we define informative Armstrong databases (IADBs) from databases as being small subsets of an existing database, satisfying exactly the same FDs and INDs. They are an extension of the classical notion of Armstrong databases, but more suitable for the understanding of dependencies, since tuples are real-world tuples. The main result of this paper is to bound the size of an IADB in the case of non-circular INDs. A constructive proof of this result is given, from which an algorithm has been devised. An implementation and experiments against a real-life database were performed; the obtained database contains 0.6% of the initial database tuples only. More importantly, such semantic sampling of databases appear to be a key feature for the understanding of existing databases at the logical level.     

Null Inclusion Dependencies in Relational Databases

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

An Order-Based Theory of Updates for Closed Database Views

The fundamental problem in the design of update strategies for views of database schemata is that of selecting how the view update is to be reflected back to the base schema. This work presents a solution to this problem, based upon the dual philosophies of closed update strategies and order-based database mappings. A closed update strategy is one in which the entire set of updates exhibit natural closure properties, including transitivity and reversibility. The order-based paradigm is a natural one; most database formalisms endow the database states with a natural order structure, under which update by insertion is an increasing operation, and update by deletion is decreasing. Upon augmenting the original constant-complement strategy of Bancilhon and Spyratos – which is an early version of a closed update strategy – with compatible order-based notions, the reflection to the base schema of any update to the view schema which is an insertion, a deletion, or a modification which is realizable as a sequence of insertions and deletions is shown to be unique and independent of the choice of complement. In addition to this uniqueness characterization, the paper also develops a theory which identifies conditions under which a natural, maximal, update strategy exists for a view. This theory is then applied to a ubiquitous example – single-relational schemata constrained by equality-generating dependencies. Within this framework it is shown that for a view defined as a projection of the main relation, the only possibility is that the complement defining the update process is also a projection, and that the reconstruction is based upon functional dependencies.     

一个具有多时间粒度时态函数依赖集的成员籍算法

对于具有函数依赖（FDs)约束的传统关系数据库规范化理论来说，判定一个FD是否被给定FD集所逻辑蕴涵（即成员籍问题）是非常重要的，这有助于设计有效的模式分解算法，而对于具有时态函数依赖（TFDs)约束的时态模式来说，由于多时间粒度的使用使成员籍问题的解决变得更加复杂，由此讨论了时态类型的一些特性，并提出了有限决定集的概念，基于求得属性的有限决定集，对每一个元素的左部属性集是单一属性的TFD集给出了一个有效的成员籍算法和相关的正确性证明。     

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

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

Deciding implication for functional dependencies in complex-value databases

Modern applications increasingly require the storage of data beyond relational structure. The challenge of providing well-founded data models that can handle complex objects such as lists, sets, multisets, unions and references has not been met yet in a completely satisfactory way. The success of such data models will greatly depend on the existence of automated database design techniques that generalise achievements from relational databases. In this paper, we study the implication problem of functional dependencies (FDs) in the presence of records, sets, multisets and lists. Database schemata are defined as nested attributes, database instances as nested relations and FDs are defined in terms of subattributes of the database schema. The expressiveness of FDs deviates fundamentally from previous approaches in different data models including the nested relational data model and XML.     

基于闭包的3NF模式综合算法

文中基于属性集关于函数依赖集的闭包，并采用模式矩阵，给出了一个从函数依赖集综合出３ＮＦ模式的算法。该算法不用Ａｒｍｓｔｒｏｎｇ公理进行烦琐的推导，与Ｂｅｒｎｓｔｅｉｎ算法相比，较为简单且易于实现。     

XML schema refinement through redundancy detection and normalization

As XML becomes increasingly popular, XML schema design has become an increasingly important issue. One of the central objectives of good schema design is to avoid data redundancies: redundantly stored information can lead not just only to a higher data storage cost but also to increased costs for data transfer and data manipulation. Furthermore, such data redundancies can lead to potential update anomalies, rendering the database inconsistent. One strategy to avoid data redundancies is to design redundancy-free schema from the start on the basis of known functional dependencies. We observe that XML databases are often “casually designed” and XML FDs may not be determined in advance. Under such circumstances, discovering XML data redundancies from the data itself becomes necessary and is an integral part of the schema refinement (or re-design) process. We present the design and implementation of the first system, DiscoverXFD, for efficient discovery of XML data redundancies. It employs a novel XML data structure and introduces a new class of partition-based algorithms. The XML data redundancies are defined on the basis of a new notion of XML functional dependency (XML FD) that (1) extends previous notions by incorporating set elements into the XML FD specification, and (2) maintains tuple-based semantics through the novel concept of Generalized Tree Tuple (GTT). Using this comprehensive XML FD notion, we introduce a new normal form (GTT-XNF) for XML documents, and provide comprehensive comparisons with previous studies. Given the set of data redundancies (in the form of redundancy-indicating XML FDs) discovered by DiscoverXFD, we describe a normalization algorithm for converting any original XML schema into one in GTT-XNF.     

Global extensional assertions and local integrity constraints in federated schemata

Integrated access to multiple data sources requires a homogeneous interface provided by a federated schema. Such a federated schema should correctly reflect the semantics of the component schemata of which it is composed. Since the semantics of a database schema is also determined by a set of semantic integrity constraints, a correct schema integration has to deal with integrity constraints existing in the different component schemata. Traditionally, most schema integration approaches solely concentrate on the structural integration of given database schemata. Local integrity constraints are often simply neglected. Their relationship to global extensional assertions, which form the basic integration constraints, are even ignored completely. In this paper, we discuss the impact of global extensional assertions and local integrity constraints on federated schemata. In particular, we point out the correspondence between local integrity constraints and global extensional assertions. The knowledge about the correspondences between the given integrity constraints and extensional assertions can then be utilized for an augmented schema integration process.     

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.     

基于模式图的规范化XML模式设计*

在给定关系模式的属性集及其函数依赖最小覆盖集的基础上,提出一种基于模式图的规范化XML模式设计方法。定义了模式图,在模式图中增加了Keys的描述信息,给出由函数依赖集构造模式图的算法。该模式图独立于具体的XML模式语言,经分析证明,所设计的模式满足XNF。     

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.     

Comparable dependencies over heterogeneous data

To study the data dependencies over heterogeneous data in dataspaces, we define a general dependency form, namely comparable dependencies (CDS), which specifies constraints on comparable attributes. It covers the semantics of a broad class of dependencies in databases, including functional dependencies (FDS), metric functional dependencies (MFDS), and matching dependencies (MDS). As we illustrated, comparable dependencies are useful in real practice of dataspaces, such as semantic query optimization. Due to heterogeneous data in dataspaces, the first question, known as the validation problem, is to tell whether a dependency (almost) holds in a data instance. Unfortunately, as we proved, the validation problem with certain error or confidence guarantee is generally hard. In fact, the confidence validation problem is also NP-hard to approximate to within any constant factor. Nevertheless, we develop several approaches for efficient approximation computation, such as greedy and randomized approaches with an approximation bound on the maximum number of violations that an object may introduce. Finally, through an extensive experimental evaluation on real data, we verify the superiority of our methods.     

Functional dependencies among Boolean dependencies

In this paper, we consider functional dependencies among Boolean dependencies (BDs, for short). Armstrong relations are defined for BDs (called BD-Armstrong relations). For BDs, two necessary and sufficient conditions for the existence of BD-Armstrong relations are given. A necessary and sufficient condition for the existence of Armstrong relations for functional dependencies (FDs, for short) is given, which in some sense is more convenient than the condition given in [3]. We give an algorithm that solves the problem of deciding if two BDs imply the same set of functional dependencies. If the BDs are given in perfect disjunctive normal form, then the algorithm requires only polynomial time. Although Mannila and Räihä have shown that for some relations exponential time is needed for computing any cover of the set of FDs defined in this relation, as a consequence, we show that the problem of deciding if two relations satisfy the same set of FDs can be solved in polynomial time. Another consequence is a new correspondence of the families of functional dependencies to the families of Sperner systems. By this correspondence, the estimate of the number of databases given previously in [6] is improved. It is shown that there is a one-to-one correspondence between the closure of the FDs that hold in a BD and its so-calledbasic cover. As applications of basic covers, we obtain a representation of a key, the family of minimal keys and a representation of canonical covers.This research was supported by the Hungarian Foundation for Scientific Research, Grant Nos. OTKA 2575, 2149.     

Design by example for SQL table definitions with functional dependencies

A database is C-Armstrong for a given set of constraints in a class C if it satisfies every constraint of the set and violates every constraint in C not implied by the set. Therefore, Armstrong databases are test data that perfectly illustrate the current perceptions about the semantics of a schema. We extend the existing theory of Armstrong relations to a toolbox of Armstrong tables. That is, we investigate structural and computational properties of Armstrong tables for the class of functional dependencies (FDs) over SQL tables. Relations are special instances of SQL tables with no duplicate rows and no null value occurrences. While FDs do not enjoy Armstrong tables, the combined class of standard FDs and NOT NULL constraints does enjoy Armstrong tables. The problem of finding an Armstrong table is shown to be precisely exponential for this combined class. However, we establish an algorithm that computes Armstrong tables with a size at most quadratic in that of a minimum-sized Armstrong table. Our resulting toolbox of Armstrong tables can be applied by data engineers to concisely visualize constraints on SQL data. Such support can lead to designs that guarantee efficient data management in practice.     

An improvement on the automatic tool for relational database design

This paper corrects some misconceptions regarding an automatic tool for relational database design. A modified algorithm (SYNTHESIZER+) from the synthesis algorithm SYNTHESIZER is presented. For a given set of FDs, it can produce a third normal form (3NF) relational database schema with a minimum number of relations.     

Information-based distance measures and the canonical reflection of view updates

For the problem of reflecting an update on a database view to the main schema, the constant-complement strategies are precisely those which avoid all update anomalies, and so define the gold standard for well-behaved solutions to the problem. However, the families of view updates which are supported under such strategies are limited, so it is sometimes necessary to go beyond them, albeit in a systematic fashion. In this work, an investigation of such extended strategies is initiated for relational schemata. The approach is to characterize the information content of a database instance, and then require that the optimal reflection of a view update to the main schema embody the least possible change of information. The key property is identified to be strong monotonicity of the view, meaning that view insertions may always be reflected as insertions to the main schema, and likewise for deletions. In that context it is shown that for insertions and deletions, an optimal update, entailing the least change of information, exists and is unique up to isomorphism for wide classes of constraints.