An Infornation-Theoretic Analysis of Relational Databases—Part I: Data Dependencies and Information Metric

Database design is based on the concept of data dependency, which is the interrelationship between data contained in various sets of attributes. In particular, functional, multivalued and acyclic join, dependencies play an essential role in the design of database schemas. The basic definition of an information metric and how this notion can be used in relational database are discussed in this paper. We use Shannon entropy as an information metric to quantify the information associated with a set of attributes. Thus, we prove that data dependencies can be formulated in terms of entropies. These formulas make the numerical computation and testing of data dependencies feasible. Among the different types of data dependencies, the acyclic join dependency is most important to the design of a relational database schema. The acyclic join dependency, with multivalued dependency as a special case, impose a constraint on the information-preserving decomposition of a relation. It is interesting that this constraint on a relation is similar to Gibbs' condition for separating physical systems in statistical mechanics. They both assert that entropy is preserved during the decomposition process. That is, the entropies of the corresponding set of attributes must satisfy the inclusion–exclusion identity.     

SMap:基于语义的关系数据库模式与OWL本体间映射方法

伴随语义网的发展,语义网本体数量激增.然而万维网上绝大多数的数据仍存储在关系数据库中.建立关系数据库模式与语义网本体间的映射是一种实现两者之间互操作性的有效途径.因此,提出了一种基于语义的关系数据库模式与OWL本体间的映射方法SMap,包含简单映射发现和复杂映射学习两个阶段.在简单映射发现阶段,首先通过逆向工程规则将关系数据库模式和本体中的元素对应地分为不同类别,再为每个元素构建虚拟文档并计算它们之间的相似度,其中针对不同类别的元素设计了不同的虚拟文档抽取方案.在复杂映射学习阶段,基于已发现的简单映射以及重叠的数据库记录和本体实例,自动化地生成训练事实数据,然后运用归纳逻辑编程算法学习出多种类型的基于Horn规则的复杂映射.真实数据集上的实验结果表明,SMap在简单映射发现和复杂映射学习上均明显优于现有的关系数据库模式与本体间映射方法.     

关系数据库模式和本体间映射的研究综述

关系数据库模式和本体问映射是语义网研究中的一个重要问题.首先,给出关系数据库模式和本体间映射的形式化定义,并从建模思想和应用场景两个方面分析问题的难点.根据3个不同角度,即模型转换的途径、映射策略的适用范围以及映射结果的表达形式,调研当前存在的多种解决途径.在此基础上,进一步介绍并比较6个具有代表性的关系数据库模式和本体间映射的工具.最后,讨论存在的挑战,并指出未来可能的研究方向.     

一种有效的关系数据库压缩方法

海量关系中经常存在小值域属性,关系不仅在这些属性上的互不相同的值的数量很小,而且在这些属性的组合上的值域也很小.因此,海量关系在这些属性上有很多重复的组合值.一种提高数据库的存储和查询效率的重要方法就是消除这些重复取值.为此,提出了拆分压缩技术,它将海量关系拆分成两种较小的关系,其中一种关系的属性由小值域属性组组成,而另一种关系的属性是海量关系的其他属性.该方法的关键是小值域属性组的识别问题.在证明了这个问题的NP-完全性后,给出了两种在海量关系中识别小值域属性组合的算法,并在此基础上提出了海量关系拆分压缩技术,讨论了压缩关系的查询处理方法.实验结果表明,拆分压缩技术可以取得较好的压缩效果,并可以提高数据库查询处理的整体性能.     

NoSQL数据库与关系数据库的比较分析

介绍了两个具有代表性的NoSQL数据库:Bigtable和Dynamo系统。首先,描述了Bigtable和Dynamo的适用范围及其产生原因。Bigtable和Dynamo可以高效的处理web数据提供相应服务;然后,介绍了Bigtable和Dynamo系统的架构、特性等,以及各自独特的设计方法。最后,将这两个数据库与传统的关系数据库进行比较分析,描述了它们之间的不同点,对比结果表明NoSQL数据库在处理web应用数据时是高效可用的,比传统关系数据库更占优势。     

An annotated bibliography of GRASP–Part II: Applications

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which each GRASP iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Since 1989, numerous papers on the basic aspects of GRASP, as well as enhancements to the basic metaheuristic, have appeared in the literature. GRASP has been applied to a wide range of combinatorial optimization problems, ranging from scheduling and routing to drawing and turbine balancing. This is the second of two papers with an annotated bibliography of the GRASP literature from 1989 to 2008. In the companion paper, algorithmic aspects of GRASP are surveyed. In this paper, we cover the literature where GRASP is applied to scheduling, routing, logic, partitioning, location, graph theory, assignment, manufacturing, transportation, telecommunications, biology and related fields, automatic drawing, power systems, and VLSI design.     

关系数据库理论的与或图等价性分析

关系数据库有着严密的数学基础,但同时也过于抽象,使理论与应用存在较大差距。文章将图论引入关系数据库,利用与或图的形式来表达关系数据库,同时对基于与或图的关系数据库和传统的关系数据库做关系模式、函数依赖理论、规范理论的等价性分析,并由此提出了一种新的更加直观、深刻的关系数据库描述工具,用以实现关系数据库的计算机设计、维护和修改的程序化。     

Information Seeking Spoken Dialogue Systems— Part II: Multimodal Dialogue

For pt.1see ibid., vol. 9, p. 3 (2007). In this paper, the task and user interface modules of a multimodal dialogue system development platform are presented. The main goal of this work is to provide a simple, application-independent solution to the problem of multimodal dialogue design for information seeking applications. The proposed system architecture clearly separates the task and interface components of the system. A task manager is designed and implemented that consists of two main submodules: the electronic form module that handles the list of attributes that have to be instantiated by the user, and the agenda module that contains the sequence of user and system tasks. Both the electronic forms and the agenda can be dynamically updated by the user. Next a spoken dialogue module is designed that implements the speech interface for the task manager. The dialogue manager can handle complex error correction and clarification user input, building on the semantics and pragmatic modules presented in Part I of this paper. The spoken dialogue system is evaluated for a travel reservation task of the DARPA Communicator research program and shown to yield over 90% task completion and good performance for both objective and subjective evaluation metrics. Finally, a multimodal dialogue system which combines graphical and speech interfaces, is designed, implemented and evaluated. Minor modifications to the unimodal semantic and pragmatic modules were required to build the multimodal system. It is shown that the multimodal system significantly outperforms the unimodal speech-only system both in terms of efficiency (task success and time to completion) and user satisfaction for a travel reservation task     

关系数据库中关联规则挖掘的一种高效算法

近年来,关系数据库被越来越多的行业采用,大量的生产、管理、科研等信息被收集存储,因此在关系数据库中进行有效的关联规则挖掘的需求日益增强.文中根据事务数据库中布尔型关联规则挖掘的相关理论和方法,在分析了关系数据库中关联规则挖掘具有的特殊性的基础上,从利用结构化查询语言(SQL)对关系数据库简便而高效的操作出发,提出了一种在关系数据库中挖掘多值型、多维型关联规则的简易算法.实验证明该算法具有较高的执行效率和一定的实用性.     

一种基于关系数据库的模糊关联规则算法

文章针对普通关联规则不能表达挖掘对象中模糊信息的关联性的问题,给出了一系列有关模糊关联规则的定义,并提出了一种基于关系数据库的模糊关联规则挖掘算法(FARMBT)。实验结果表明,FARMBT算法是有效的。同时,关系数据库的广泛应用使FARMBT算法具有广泛的实用前景。     

关系型数据库中树形数据的组织与算法分析

介绍在关系型数据库中采用孩子表示法、双亲表示法以及双亲孩子表示法存储树形数据，讨论不同存储方法下插入删除结点、树的遍历、树的度和深度的计算算法，井分析这些算法的性能。     

关系数据库中关联规则挖掘的一种高效算法

近年来，关系数据库被越来越多的行业采用，大量的生产、管理、科研等信息被收集存储，因此在关系数据库中进行有效的关联规则挖掘的需求日益增强。文中根据事务数据库中布尔型关联规则挖掘的相关理论和方法，在分析了关系数据库中关联规则挖掘具有的特殊性的基础上，从利用结构化查询语言(SQL)对关系数据库简便而高效的操作出发，提出了一种在关系数据库中挖掘多值型、多维型关联规则的简易算法。实验证明该算法具有较高的执行效率和一定的实用性。     

分布式数据库研究新趋势

本文从异构分布式数据库、网络数据库、移动数据库等几个方向，讨论了分布式数据库研究所面临的几个新课题，并对未来分布式数据库的发展前景作了展望。     

基于关系数据库的粗糙集约简改进算法

以粗糙集约简和关系数据库为研究对象,提出了一种带有数据预处理和新启发式信息值的粗糙集约简改进算法.通过应用了该改进算法的DBRuduct工具进行实验,实验数据表明决策表的对象个数和约简计算时间之间成近似线性的关系;以Rosetta中的遗传算法求得的约简作为实验参照,该算法不但可以在含有不一致数据的情况下获得正确的核属性,而且还使约简算法求得的约简更加趋向于最小约简.     

A Fuzzy Temporal Object‐Relational Database: Model and Implementation

In real world, some data have a specific temporal validity that must be appropiately managed. To deal with this kind of data, several proposals of temporal databases have been introduced. Moreover, time can also be affected by imprecision, vagueness, and/or uncertainty, since human beings manage time using temporal indications and temporal notions, which may also be imprecise. For this reason, information systems require appropriate support to accomplish this task. In this work, we present a novel possibilistic valid time model for fuzzy databases including the data structures, the integrity constraints, and the DML. Together with this model, we also present its implementation by means of a fuzzy valid time support module on top of a fuzzy object‐relational database system. The integration of these modules allows to perform queries that combines fuzzy valid time constraints together with fuzzy predicates. Besides, the model and implementation proposed support the crisp valid time model as a particular case of the fuzzy valid time support provided.     

Information systems support for healthcare quality: Part II

In the second and final part of his series of quality management, healthcare information systems consultant Peter Spitzer, M.D., describes how I/S can support quality healthcare services by improving the care-delivery process and by providing the data needed for quality support, monitoring and management.     

Structured Fortran—An Evolution of Standard Fortran

Fortran is 21 years old; many would say that it has not reached adulthood but senility. Yet it remains the language of use in the overwhelming majority of scientific applications of computers and no end to this situation is in sight. Moreover, its evolution through the standards process is very slow, too slow to give any hope that Fortran will ever in this way become a language in which structured programs can be easily and effectively written.     

关系数据库关键字搜索系统Discover的实验与分析

早在2002年,关系数据库中的关键字搜索问题就已经有了很多代表性的研究成果,其中的Discover系统由于其算法经典,在后来的文章中被广泛引用.但是Discover中实验数据并不充分,如关键字个数设定过少、没有给出关键字个数对结果集大小的影响、只在AND语义下进行实验等.由于存在上述问题,使得对关键字搜索问题的研究得不到一些真正有意义的数据.文中实现了Discover中的关键字搜索算法,并对实验进行了进一步的完善,并对实验结果进行了分析和阐述,为关键字搜索提供了更有价值的实验数据和分析结果.