CMS实验中关系数据库的精确关键词查询

在大型强子对撞机(LHC)上紧凑型缪子螺线管探测器(CMS)实验的复杂数据环境下,有多个关系型数据源记录了关于数据组织和分布的信息。为实现数据查询系统的精确关键词查询功能,通过分析数据库模式图的方法,将关键词查询语言动态翻译成SQL语言,设计并实现一个跨数据库平台的关键词查询系统。针对动态翻译过程中存在的二义性问题,提出基于查询实体的模式图分析算法,以及基于最小权重树查找的动态连接算法。实验结果表明,该动态连接算法能为关键词查询正确生成所需数据库表的连接方式,使关键词查询系统具有较高的查询效率,以满足用户实时、精确查询的需求。     

基于q-gram的字符串相似性查询研究

相似性查询在实际应用中用途广泛,例如相似网页检测、相似图像检索、语言识别、数据清理等。而基于q-gram的字符串相似性查询作为主流方法之一．在查询的效率和灵活性上相对于其他方法都有很大的优势。实现基于q-gram的基本过滤器,并构成过滤器组合模型,用来过滤掉不匹配的字符串,得到候选集。实验结果表明,与传统的依靠编辑距离来比较每一对字符串的值相比,基于q-gram的过滤器能在保证相似性查询结果准确的前提下,在效率方面有显著的提升。     

Theory revision with queries: Horn, read-once, and parity formulas

A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered here in the model of learning with equivalence and membership queries. A revision algorithm is considered efficient if the number of queries it makes is polynomial in the revision distance between the initial theory and the target theory, and polylogarithmic in the number of variables and the size of the initial theory. The revision distance is the minimal number of syntactic revision operations, such as the deletion or addition of literals, needed to obtain the target theory from the initial theory. Efficient revision algorithms are given for Horn formulas and read-once formulas, where revision operators are restricted to deletions of variables or clauses, and for parity formulas, where revision operators include both deletions and additions of variables. We also show that the query complexity of the read-once revision algorithm is near-optimal.     

基于内容的多媒体数据查询和检索

多媒体数据具有可表现的视觉和听觉特性，而难于用符号形式来描述。本文介绍基于内容的对多媒体数据进行查询和检索的概念和方法，描述查询和检索的一般系统结构、用户查询类型、索引／过滤机制，以及视频的检索和浏览，并给出基于内容检索研究中值得探索的几个主要问题。     

基于代理的软件设计和软件重用

总结了目前的软件重用方法,指出其不足之处,提出了一种新的软件设计方法,基于代理的软件设计的三层体系结构模型,并给出了在敏捷从应链中的应用实例分析。     

面向对象数据库中的索引实现技术

首先介绍主要的３种嵌套属性上的索引实现技术及其操作算法,并分析和比较了它们的优缺点,然后介绍了面向对象工程数据库管理系统ＯＳＣＡＲ中的索引实现技术。     

Object query optimization through detecting independent subqueries

The problem of query optimization in object-oriented databases is addressed. We follow the Stack-Based Approach to query languages, which employs the naming-scoping-binding paradigm of programming languages rather than traditional database concepts such as relational/object algebras or calculi. The classical environment stack is a semantic basis for definitions of object query operators, such as selection, projection/navigation, dependent join, and quantifiers. We describe a general object data model and define a formalized OQL-like query language SBQL. Optimization by rewriting concerns queries containing so-called independent subqueries. It consists in detecting them and then factoring outside loops implied by query operators. The idea is based on the formal static analysis of scoping rules and binding names occurring in a query. It is more general than the classical pushing selections/projections before joins.     

聚簇索引在数据库查询中的重要作用

本文从数据库查询优化角度,把数据库查３种常规操作细分,进而概括出几乎所有的查询算法都是这些操作的不同组合。然后列举出４种常见的连接查询方法,利用细分的操作为４种查询方法建立模型,量化和分析它们的一些关键参数,从而说明逻辑邻接项的物理聚簇索引会对数据库查询性能产生很大影响。索引对查询性能提高程度的关键取决于是否建立的是聚簇索引。     

基于标记树对象抽取技术的Hidden Web获取研究

目前标准的搜索引擎能够检索的仅仅是WorldWideWeb提供的小部分称为可索引的Web信息。大量的HiddenWeb信息(估计容量是可索引Web的500倍)对这些搜索引擎是不可见的。这些信息隐藏在Web页面的搜索表单后面,保存在大型的动态数据库中。该文提出了一套检索HiddenWeb信息的方法,给出了系统的框架结构,并详细讨论了实现的关键技术。系统采用新的基于标记树的对象抽取(Tag-Tree-basedObjectExtraction)方法自动地从Web页面中抽取HiddenWeb信息,然后在此基础上给出了结构化的HiddenWeb信息查询算法。文章最后对实验结果进行了讨论。     

Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n$n$ items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)$O\left(n\right)$ space where queries require O(1)$O\left(1\right)$ probes and the contention is O(1/n)$O(1/n)$. Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)$O\left(n\right)$ space where each query requires O(logn/loglogn)$O(logn/loglogn)$ probes and the contention is O(logn/(nloglogn))$O(logn/(nloglogn))$. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(loglogn)$\Omega (loglogn)$.