On the implication problem for cardinality constraints and functional dependencies

In database design, integrity constraints are used to express database semantics. They specify the way by that the elements of a database are associated to each other. The implication problem asks whether a given set of constraints entails further constraints. In this paper, we study the finite implication problem for cardinality constraints. Our main result is a complete characterization of closed sets of cardinality constraints. Similar results are obtained for constraint sets containing cardinality constraints, but also key and functional dependencies. Moreover, we construct Armstrong databases for these constraint sets, which are of special interest for example-based deduction in database design.     

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.     

On the finite controllability of conjunctive query answering in databases under open-world assumption

In this paper we study queries over relational databases with integrity constraints (ICs). The main problem we analyze is OWA query answering, i.e., query answering over a database with ICs under open-world assumption. The kinds of ICs that we consider are inclusion dependencies and functional dependencies, in particular key dependencies; the query languages we consider are conjunctive queries and unions of conjunctive queries. We present results about the decidability of OWA query answering under ICs. In particular, we study OWA query answering both over finite databases and over unrestricted databases, and identify the cases in which such a problem is finitely controllable, i.e., when OWA query answering over finite databases coincides with OWA query answering over unrestricted databases. Moreover, we are able to easily turn the above results into new results about implication of ICs and query containment under ICs, due to the deep relationship between OWA query answering and these two classical problems in database theory. In particular, we close two long-standing open problems in query containment, since we prove finite controllability of containment of conjunctive queries both under arbitrary inclusion dependencies and under key and foreign key dependencies. The results of our investigation are very relevant in many research areas which have recently dealt with databases under an incomplete information assumption: e.g., data integration, data exchange, view-based information access, ontology-based information systems, and peer data management systems.     

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.     

Membership problems for data dependencies in relational expressions

In relational databases, a query can be formulated in terms of a relational algebra expression using projection, selection, restriction, cross product and union. In this paper, we consider a problem, called the membership problem, of determining whether a given dependency d is valid in a given relational expression E over a given database scheme R that is, whether every instance of the view scheme defined by E satisfies d (assuming that the underlying constraints in R are always satisfied).Consider the case where each relation scheme in R is associated with functional dependencies (FDs) as constraints, and d is an FD. Then the complement of the membership problem is NP-complete. However, if E contains no union, then the membership problem can be solved in polynomial time. Furthermore, if E contains neither a union nor a projection, then we can construct in polynomial time a cover for valid FDs in E, that is, a set of FDs which implies every valid FD in E.Consider the case where each relation scheme in R is associated with multivalued dependencies (MVDs) as well as FDs, and d is an FD or an MVD. Even if E consists of selections and cross products only, the membership problem is NP-hard. However, if E contains no union, and each relation scheme name in R occurs in E at most once, then the membership problem can be solved in polynomial time. As a corollary of this result, it can be determined in polynomial time whether a given FD or MVD is valid in $\text{R}{}_1\text{???R}{}_{\mathrm{s}}$, where R₁,…,R_s are relation schemes with FDs and MVDs, and $\text{R}{}_{\mathrm{i}}\text{?R}{}_{\mathrm{j}}$ is the natural join of R_i and R_j.     

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

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

RRDB与FRDB关系的系统研究

以粗糙集理论(Rough Set Theory)和关系数据库理论为基础,从函数依赖、范式理论、Armstrong公理等方面系统地研究了粗糙关系数据库(Rough Relational DataBase,简称RRDB)与模糊关系数据库(Fuzzy Relational DataBase,简称FRDB)之间的关系。结果表明,模糊函数依赖与粗糙函数依赖均为经典函数依赖的泛化,模糊范式理论为经典范式的扩充,而粗糙范式理论自成体系,从推理规则上看,它们都不同程度地符合Armstrong公理。     

一个多时间粒度下时态函数依赖的有限属性闭包算法

为了有效地进行时态数据库设计,支持多时间粒度的时态函数依赖(TFDs)被用于时态模式的规范化.时态模式规范化所要解决的一个关键问题是求解时态函数依赖的有限属性闭包问题.由于多时间粒度的使用,使得有限属性闭包问题变得非常复杂.实际上,TFDs与传统的函数依赖(FDs)之间存在着密切的联系.通过分析这些联系和封闭时态类型集的特性,利用传统FDs的相关算法提出一个有效的求解有限属性闭包的算法.通过分析和与相关算法的实验比较,该算法更加有效.     

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.     

Discovering interesting inclusion dependencies: application to logical database tuning

Inclusion dependencies together with functional dependencies form the most important data dependencies used in practice. Inclusion dependencies are important for various database applications such as database design and maintenance, semantic query optimization and efficient view maintenance of data warehouse. Existing approaches for discovering inclusion dependencies consist in producing the whole set of inclusion dependencies holding in a database, leaving the task of selecting the interesting ones to an expert user.In this paper, we take another look at the problem of discovering inclusion dependencies. We exploit the logical navigation, inherently available in relational databases through workloads of SQL statements, as a guess to automatically find out only interesting inclusion dependencies. This assumption leads us to devise a tractable algorithm for discovering interesting inclusion dependencies. Within this framework, approximate dependencies, i.e. inclusion dependencies which almost hold, are also considered.As an example, we present a novel application, namely self-tuning the logical database design, where the discovered inclusion dependencies can be used effectively.     

Armstrong axioms and Boyce-Codd-Heath Normal Form under bag semantics

The theory of functional dependencies is based on relations, i.e. sets of tuples. Over relations, the class of functional dependencies subsumes the class of keys. Commercial database systems permit the storage of bags of tuples where duplicate tuples can occur. Over bags, keys and functional dependencies interact differently from how they interact over relations.We establish finite ground axiomatizations of keys and functional dependencies over bags, and show a strong correspondence to goal and definite clauses in classical propositional logic. We define a syntactic Boyce-Codd-Heath Normal Form condition, and show that the condition characterizes schemata that will never have any redundant data value occurrences in their instances. The results close the gap between the existing set-based theory of data dependencies and database practice where bags are permitted.     

Empirical evidence for the usefulness of Armstrong relations in the acquisition of meaningful functional dependencies

Armstrong relations satisfy precisely those data dependencies that are implied by a given set of data dependencies. A common perception is that Armstrong relations are useful in the acquisition of data semantics, in particular since errors during the requirements elicitation have the most expensive consequences.     

Discovering functional and inclusion dependencies in relational databases

We consider the problem of discovering the functional and inclusion dependencies that a given database instance satisfies. This technique is used in a database design tool that uses example databases to give feedback to the designer. If the examples show deficiencies in the design, the designer can directly modify the examples. the tool then infers new dependencies and the database schema can be modified, if necessary. the discovery of the functional and inclusion dependencies can also be used in analyzing an existing database. the problem of inferring functional dependencies has several connections to other topics in knowledge discovery and machine learning. In this article we discuss the use of examples in the design of databases, and give an overview of the complexity results and algorithms that have been developed for this problem. © 1992 John Wiley & Sons, Inc.     

时态类型集的封闭集

好的数据库逻辑设计目标是消除数据冗余以及插入和删除异常。对于时态数据库，可以利用具有多时间粒度的时态函数依赖（TFDs）约束对时态数据库进行规范化。要进行有效的数据库设计，需要解决有限属性闭包和成员籍等一些有关TFD的问题。为了方便计算机对时态类型的处理和找到有效的解决TFD的相关问题的算法，该文提出了封闭时态类型集的概念，并且给出了一个求给定TFD集的封闭集的算法。     

Functional and multivalued dependencies in nested databases generated by record and list constructor

The impact of the list constructor on two important classes of relational dependencies is investigated. Lists represent an inevitable data structure whenever order matters and data is allowed to occur repeatedly. The list constructor is therefore supported by many advanced data models such as genomic sequence, deductive and object-oriented data models including XML. The article proposes finite axiomatisations of functional, multivalued and both functional and multivalued dependencies in nested databases supporting record and list constructor. In order to capture different data models at a time, an abstract algebraic approach based on nested attributes is taken. The presence of the list constructor calls for a new inference rule which allows to infer non-trivial functional dependencies from multivalued dependencies. Further differences to the relational theory become apparent when the independence of the inference rules is investigated. The extension of the relational theory to nested databases allows to specify more real-world constraints and increases therefore the number of application domains. * Results of this article were partly presented at the 3rd International Symposium on Foundations of Information and Knowledge Systems (FoIKS), Vienna, Austria, 2004 [58], and the 23rd International Symposium on Principles of Database Systems (PODS), Paris, France, 2004 [54]. ** Sebastian Link was supported by Marsden Funding, Royal Society of New Zealand.     

A note on lossless database decompositions

It is known that under a wide variety of assumptions a database decomposition is lossless if and only if the database scheme has a lossless join. Biskup, Dayal and Bernstein (1979) have shown that when the given dependencies are functional, the database scheme has a lossless join if and only if one of the relation schemes is a key for the universal scheme. In this note we supply an alternative proof of that characterization. The proof uses tools from the theory of embedded join dependencies and the theory of tuple and equality generating dependencies, but is, nevertheless, much simpler than the previously published proof.     

Decidable sentences of Church-Rosser congruences

A decision procedure for a class of true sentences of congruences generated by finite monadic Church-Rosser systems is developed. Using this decision procedure it is shown that if $\text{M}$_T is the monoid presented by such a system T, then (i) it is decidable given T whether $\text{M}$_T is a group, (ii) it is decidable given T and a finite set A whether the submonoid generated by A is a group or a left (right, two-sided) ideal, and (iii) Green's relations for $\text{M}$_T are decidable.     

Fuzzy functional dependencies and Bayesian networks

Bayesian networks have become a popular technique for representing and reasoning with probabilistic information.The fuzzy functional dependency is an important kind of data dependencies in relational databases with fuzzy values,The purpose of this paper is to set up a connection between these data dependencies and Bayesian networks.The connection is done through a set of methods that enable pepople to obtain the most information of independent conditions from fuzzy functional dependencies.     

Characterizations for functional dependency and Boyce-Codd normal form families

A functional dependency (fd) family was recently defined [20] as the set of all instances satisfying some set of functional dependencies. A Boyce-Codd normal form, abbreviated BCNF, family is defined here as an fd-family specified by some BCNF set of functional dependencies. The purpose of this paper is to present set-theoretic/algebraic characterizations relating to both types of families.Two characterizations of $\text{F}$($\text{I}$), the smallest fd-family containing the family $\text{I}$ of instances, are established. The first involves the notion of agreement, a concept related to that of a closed set of attributes. The second describes $\text{F}$($\text{I}$) as the smallest family of instances containing $\text{I}$ and closed under four specific operations on instances. Companion results are also given for BCNF- families.The remaining results concern characterizations involving the well-known operations of projection, join and union. Two characterizations for when the projection of an fd-family is again an fd-family are given. Several corollaries are obtained, including the effective decidability of whether a projection of an fd-family is an fd-family. The problem for BCNF-families disappears since it is shown that the projection of a BCNF-family is always a BCNF-family. Analogous to results for fd-families presented in [20], characterizations of when the join and union of BCNF-families are BCNF-families are given. Finally, the collections of all fd-families and all BCNF-families are characterized in terms of inverse projection operations and intersection.     

XML模式中隐式冗余不存在的充要条件

XML数据库模式规范化设计是产生一组相关联的、能表示数据间依赖关系、而且消除了冗余的XML模式或DTD,以更好地进行信息检索.XML数据库模式中某些数据依赖的存在是冗余存在的原因,因此在XML数据库模式中数据依赖与冗余的关联是其规范化设计研究的关键问题,但对这一问题目前还没有专门的研究.XML数据库模式的数据依赖包括属性间数据依赖和元素间的数据依赖,给出综合了属性间和元素间数据依赖的XML数据库模式数据依赖的定义,分析与之关联的隐式冗余,并论证XML模式中隐式冗余不存在当且仅当该XML模式是规范的,为XML数据库模式规范化设计更深一层的研究奠定理论基础.