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

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

基于语义贴近度的模糊数据依赖

本文基于语义贴近度的概念给出了模糊函数依赖（ＦＦＤ）、模糊多值依赖（ＦＭＶＤ）和模型联接依赖（ＦＪＤ）的定义。本文得到一组类似于Ａｒｍｓｔｒｏｎｇ公理的正确、完备的ＦＦＤ和ＦＭＶＤ的推理规则。进一步，我们证明了经典数据依赖满足模糊数据依赖的定义，ＦＦＤ是ＦＭＶＤ的特例，而ＦＭＶＤ又是ＦＪＤ的特例。     

关于依赖性完备公理存在问题研究

数据依赖在数据库设计中起着十分重要的作用。自Codd提出函数依赖,Fagin引入多值依赖后,近年来人们又根据设计中的需要引入了许多种新的依赖。然而对这些依赖可从原则上控是否具备完备的公理系统划分为两大类,因为完备公理系统往往是具有有效判定算法为先决条件。本文给出了一种具有完备公理系统的充要条件,并利用它来证明几种依赖(嵌入型多值依赖、嵌入型联接依赖、包含依赖与函数依赖)不具备完备的公理系统。     

ODBC技术在工程CAD系统中的应用

该文为了解决工程ＣＡＤ系统中数据处理效率低的问题，提出了采用ＯｐｅｎＤａｔａｂａｓｅＣｏｎｎｅｃｔｉｖｉｔｙ（开放式数据库联接，ＯＤＢＣ）的技术把不同类型的输入、输出数据定向于数据库管理系统中，同时利用了ＭＦＣ（ＭｉｃｒｏｓｏｆｔＣ基本类库）中的ＤＡＯ（数据库存取对象）技术对数据库进行管理和查询，从而提高了整个ＣＡＤ系统的集成化程度。并以一个基于ＯＤＢＣ的轻钢厂房ＣＡＤ系统为例子进行深入的阐述。     

为C语言增加两个直接读写FoxBase＋库文件的接口函数

本文在较为详细地分析了ＦｏｘＢａｓｅ＋（ＤｂａｓｅⅢ）的ＤＢＦ文件结构的基础上，利用ＴＵＲＢＯＣ２．０编写了两个在Ｃ语言程序中可直接读写ＦｏｘＢａｓｅ＋的库文件的函数Ｌｏａｄ（）和Ｓａｖｅ（）。它使得Ｃ语言与Ｆｏｘｂａｓｅ＋数据库可以混合编程。     

VisualC 5.0数据库功能的实现

在ＶｉｓｕａｌＣ＋＋５．０平台上开发数据库应用程序的方法。该方法基于表的ＭｉｃｒｏｓｏｆｔＦｏｕｎｄａｔｉｏｎＣｌａｓｓＬｉｂｒａｒｙ和ＯＤＢＣ（开放数据库互联），具有编写方便、可移植性强等优点。     

C~k连续的保形插值2k次样条函数

Ｃ~ｋ连续的保形插值２ｋ次样条函数方逵（国防科技大学，长沙）ＡＣ~ｋ－ＳＨＡＰＥ－ＰＲＥＳＥＲＶＩＮＧＩＮＴＥＲＰＯＬＡＴＩＮＧＳＰＬＩＮＥＦＵＮＣＴＩＯＮＯＦＤＥＧＲＥＥ２ｋ￥ＦａｎｇＫｕｉ（ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅ...     

基于MFC的ODBC数据库访问与编程

本文介绍了在ＶｉｓｕａｌＣ＋＋（５．０）环境下,利用ＭＦＣ通过ＯＤＢＣ接口访问ＶｉｓｕａｌＦｏｘｐｒｏ数据库的方法和编程。     

Cialdea一阶模态归结系统的不完备性及其改进

Ｃｉａｌｄｅａ的－阶模态Ｄ逻辑归结系统具有符号冗余较少和机器上较容易实现等优点，但它是不完备的。本文中，我们改进了Ｃｉａｌｄｅａ归结系统，引入了两个可能算子约束的公式间的归结规则，得到了一种新的一阶模态Ｄ逻辑的归结系统，记为ＦＭＲＤ．ＦＭＲＤ很好地保持了Ｃｉａｌｄｅａ归结系统的优点，同时，我们证明了ＦＭＲＤ的可靠性与完备性。     

基于客户/服务器模式的电力系统管理及故障诊断专家系统的开发

介绍一种基于客户／服务器的电子系统管理及故障诊断专家系统。该系统以Ｗｉｎ－ｄｏｗｓＮＴ为平台，采用客户／服务器网络结构，在服务器端由数据库服务器——ＳＱＬＳｅｒｖｅｒ统一管理数据库，并利用开放的数据库连接（ＯＤＢＣ）和ＶｉｓｕａｌＦｏｘＰｒｏ３．０开发客户端应用程序。     

The complexity of embedded axiomatization for a class of closed database views

It is well known that the complexity of testing the correctness of an arbitrary update to a database view can be far greater than the complexity of testing a corresponding update to the main schema. However, views are generally managed according to some protocol which limits the admissible updates to a subset of all possible changes. The question thus arises as to whether there is a more tractable relationship between these two complexities in the presence of such a protocol. In this paper, this question is addressed for closed update strategies, which are based upon the constant-complement approach of Bancilhon and Spyratos. The approach is to address a more general question – that of characterizing the complexity of axiomatization of views, relative to the complexity of axiomatization of the main schema. For schemata constrained by denial or consistency constraints, that is, statements which rule out certain situations, such as the equality-generating dependencies (EGDs) or, more specifically, the functional dependencies (FDs) of the relational model, a broad and comprehensive result is obtained in a very general framework which is not tied to the relational model in any way. It states that every such schema is governed by an equivalent set of constraints which embed into the component views, and which are no more complex than the original set. For schemata constrained by generating dependencies, of which tuple-generating dependencies (TGDs) in general and, more specifically, both join dependencies (JDs) and inclusion dependencies (INDs) are examples within the relational model, a similar result is obtained, but only within a context known as meet-uniform decompositions, which fails to recapture some important situations. To address the all-important case of relational schemata constrained by both FDs and INDs, a hybrid approach is also developed, in which the general theory regarding denial constraints is blended with a focused analysis of a special but very practical subset of the INDs known as fanout-free unary inclusion dependencies (fanout-free UINDs), to obtain results parallel to the above-mentioned cases: every such schema is governed by an equivalent set of constraints which embed into the component views, and which are no more complex than the original set. In all cases, the question of view update complexity is then answered via a corollary to this main result. Parts of this paper are based upon work reported in [21].     

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.     

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.     

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

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

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.     

Computing unique canonical covers for simple FDs via transitive reduction

Although there is a rich body of research on dependency theory, only few results concerning simple functional dependencies (FDs) have been published. In this paper, the following key results regarding simple FDs are shown. First, given an acyclic set F of simple FDs there exists exactly one canonical cover for F. Second, this uniquely determined canonical cover can be computed via transitive reduction. Third, it is shown how a uniquely determined canonical cover can be fixed in case of arbitrary simple FDs via transitive reduction.     

Mining functional dependencies from data

In this paper, we propose an efficient rule discovery algorithm, called FD_Mine, for mining functional dependencies from data. By exploiting Armstrong’s Axioms for functional dependencies, we identify equivalences among attributes, which can be used to reduce both the size of the dataset and the number of functional dependencies to be checked. We first describe four effective pruning rules that reduce the size of the search space. In particular, the number of functional dependencies to be checked is reduced by skipping the search for FDs that are logically implied by already discovered FDs. Then, we present the FD_Mine algorithm, which incorporates the four pruning rules into the mining process. We prove the correctness of FD_Mine, that is, we show that the pruning does not lead to the loss of useful information. We report the results of a series of experiments. These experiments show that the proposed algorithm is effective on 15 UCI datasets and synthetic data.     

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

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

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

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