九十年代初的数据库技术

进入九十年代以来,人们越来越意识到,站在下世纪初各种信息管理的应用的立场来看,我们对支持这些应用的数据库原理和技术的理解还很肤浅。制造科学、科学形象化、机器人学、光学存储、以及高速通讯等领域的迅速发展已经对现有的数据库理论和实践构成了威胁。可以说,我们现在正处于新旧技术交替的关键点。新技术的研究正在全面铺开。尽管人们对未来一些重要数据库问题的解决办法尚不明瞭,各种技术也很不成熟,但从九一年国际数据库界的研究动     

具有面向对象特征的知识库系统

本文讨论了具有面向对象特征的知识库系统KBASE~ 的数据模型、语言及实现。KBASE~ 的数据模型可以方便地支持对象标识、类层次、多继承等面向对象概念。描述性查询语言KBL是DATALOG针对于非一范式关系模型的扩充。本文重构了KBL的语义理论框架,提出了通过计算相关类的下确界来解决属性继承中的冲突问题,通过在KBL程序中添加规则来实现实例继承的方案,本文说明了KBL程序可以转换成语义等价的DATALOG程序,描述了这种转换的基本思想,探索了知识库和面向对象数据库有机结合的可行途径。     

带否定的DATALOG的语义的不动点特性

带否定子目标的ＤＡＴＡＬＯＧ（称为ＤＡＴＡＬＯＧ~）是ＤＡＴＡＬＯＧ的一种扩充．本文研究ＤＡＴＡＬＯＧ~语义的良基模型的不动点特性．首先，重新考察了稳定性变换，定义了新算子及其不动点．在此基础上，定义了振荡不动点模型论语义．然后，本文证明了振荡不动点模型和良基模型是等同的，说明前者可以看作是后者的构造性定义．     

基于复杂对象的知识库语言

近年来，复杂对象数据模型及其逻辑数据语言的研究引起了人们的广泛的重视．本文提出了一种复杂对象模型ＣＯＭ，描述了该模型上的说明性查询语言ＣＯ－ＤＡＴＡＬＯＧ的语法结构．在语义方面，定义了空间、基、解释、满足、模型等概念；利用ＣＯＭ实例的格性质证明了ＣＯ－ＤＡＴＡＬＯＧ的模型相交定理、最小模型存在定理以及最小模型的不动点性质，从而重构了其语义理论框架．     

Efficient Computation of κ-Medians over Data Streams Under Memory Constraints

In this paper, we study the problem of efficiently computing k-medians over high-dimensional and high speed data streams. The focus of this paper is on the issue of minimizing CPU time to handle high speed data streams on top of the requirements of high accuracy and small memory. Our work is motivated by the following observation: the existing algorithms have similar approximation behaviors in practice, even though they make noticeably different worst case theoretical guarantees. The underlying reason is that in order to achieve high approximation level with the smallest possible memory, they need rather complex techniques to maintain a sketch, along time dimension, by using some existing off-line clustering algorithms. Those clustering algorithms cannot guarantee the optimal clustering result over data segments in a data stream but accumulate errors over segments, which makes most algorithms behave the same in terms of approximation level, in practice. We propose a new grid-based approach which divides the entire data set into cells (not along time dimension). We can achieve high approximation level based on a novel concept called (1-∈)-dominant. We further extend the method to the data stream context, by leveraging a density-based heuristic and frequent item mining techniques over data streams. We only need to apply an existing clustering once to computing k-medians, on demand, which reduces CPU time significantly. We conducted extensive experimental studies, and show that our approaches outperform other well-known approaches.     

LEO:基于序列化的XML文档高效查询处理方法

可扩展标记语言(XML)已经成为互联网上数据表示、存储和交换的标准.在众多研究工作中,作为核心问题之一的XML文档的结构化查询处理一直是研究的热点问题.在已有的许多查询处理方法中,XPath等查询表达式一般是被分解成多个简单路径的查询,最后把部分结果进行连接操作得到最终结果,但是连接操作的时间耗费较大,直接影响到查询性能.因此,基于序列化的查询处理方法被提出以解决前述问题.提出了一种新的基于序列化的查询处理方法:LEO方法,利用文档节点的标记、深度和后序数信息,通过序列匹配的方法完成结构化查询处理.另外,基于磁盘的索引结构与系统整体框架等相关内容也做了简单介绍.理论分析与实验结果都证实了提出的LEO方法是一种准确高效的查询处理方法.     

结构化对等计算系统中的高维相似搜索

对等计算数据管理中的一个重要问题是如何有效地支持高维空间中的相似性搜索．文章采用了一种有效的空间划分策略，提出了一种基于Chord系统的相似搜索方法．首先，利用预先选定的代表点对整个数据空间进行划分，使得每个代表点对应唯一的一个子空间且所有子空间的体积之和等于整个数据空间的体积．然后，将这些代表点映射到一维区间，使得每个代表点被赋予一个唯一的标识．将代表点的标识作为Chord系统中的节点散列值，就构造出一种改进的Chord系统．最后，利用Chord系统的路由协议，以代表点的标识为查找键就可以访问到所有与搜索区域相交的子空间对应的节点．仿真实验表明，在查询处理代价和调节负载均衡方面，与现有的方法相比（如MUCK），义中提出的方法更加有效．     

XML压缩文档上的数值更新方法

近年来，XML已成为Web上信息交流和资源共享的主要载体。但XML自身的自冗余特性限制了它的普遍应用。目前，已经有研究成果提出了XML的压缩方法。压缩的XML文档能够有效利用存储空间，节省网络带宽。在实际应用中，经常需要对压缩存储的XML文档进行更新。对于大的压缩文档，如果先解压再更新，会消耗大量时间，因此，高效的更新方法应该避免解压缩文档，在压缩的XML文档上直接进行更新操作。本文针对压缩XML文档中的数值类型（包括整型和浮点型）数据，研究了在保持压缩状态条件下如何进行有效的数值更新，提出了基于XPRESS实现的Naive数值更新方法，以及修改XPRESS编码方法实现的更为高效的Pivot数值更新方法。通过大量的实验证明，Pivot数值更新方法不仅能够提供高效的更新处理，而且保持了XPRESS的高压缩率。     

基于噪声数据流的高效相似匹配算法

由于在金融分析、环境监测、网络服务等重要领域的良好应用前景,基于数据流的相似匹配算法成为数据库研究的热点之一.在实际应用中,数据流噪声大量存在且难以被完全过滤,因此,处理噪声数据流上的相似匹配问题显得尤其重要.为解决该问题,首先提出了一种新的距离定义,K-Match距离,由于其可以避免噪声数据参与运算,因而具有较强的抗噪性能.在此定义基础上,提出了一种高效的流式匹配算法SKM. SKM通过保留历史信息,能够随着数据流的更新及时返回匹配结果.最后,通过实验进一步证明,该算法能够有效地在噪声数据流中找到相似子序列.     

万维网的链接结构分析及其应用综述

当今万维网的规模已经快速发展到包含大约80亿个网页和560亿个超链接．此外，对万维网的创建进行全局规划显然是不可能的．这些都对万维网的相关研究提出了挑战．另一方面，互联网环境下通过超链连接起来的网页，为人们的日常和商务用途提供了非常丰富的信息资源，但前提是必须掌握有效的办法来理解万维网．链接结构分析在万维网的很多研究领域起着越来越重要的作用．全面介绍了万维网链接分析方面的最新研究进展和应用情况，对链接分析在Web信息搜索、万维网潜在社区发现及万维网建模等方面的研究进展和实际应用进行了综述．