一种基于关系模型的模糊数据库系统模型

数据库管理系统的广泛应用，使得数据库的研究也随之快速发展，如何表达模糊数据，如何执行模糊查询越来越成为数据库研究的重要课题之一，提出一个基于关系模型的模糊数据库系统的理论模型，利用模糊集的方法表达模糊数据，模糊查询和模糊关系，最后给出了一个模糊数据库系统实现的例子。     

SESQ系统的一种查询优化策略

随着web上信息的快速增长，如何能够准确快速地找到相关信息已经成为一个挑战．sEsQ系统是一个面向特定领域的web数据引擎，它可以通过领域Ontology实现对特定领域web数据的搜索、提取、集成和存储．与搜索引擎和传统的数据库系统相比，SESQ系统在数据模型和底层数据存储策略等方面有着诸多不同．SESQ系统根据自身特点提出了一种新的查询优化策略，这种优化策略可以适用于不同的底层存储方法，它可以有效地去除那些对最终查询结果没有用的数据．     

一种轻型关系型数据源包装器的设计

包装器是自治异构数据源集成系统中的重要组成部分。随着与XML有关的标准不断制定和完善,越来越多的数据被用XML表示,同时必须注意的一个事实是,目前和在一个可以预见的未来,大部分应用系统,甚至是新的基于Web的应用系统,仍然将关系数据库系统作为数据存储和查询的首选。关系数据库系统的可靠性、技术的成熟性、丰富的工具、高性能等,都决定了这一点。本文探讨在自治异构数据源集成系统情境下,如何将XML查询翻译成SQL查询,如何将关系数据转换为XML数据表示。     

基于SQL Server 2000的通用模糊查询工具设计

本文设计并实现了一个基于SQL Server 2000的通用模糊查询工具,该工具可以把带权重的模糊查询转换为标准的SQL语句。用户可以对SQL Server中建立的任何数据库表进行模糊查询。系统提供了以下功能：定义模糊谓词及其隶属函数;定义模糊算子;构造带权重的模糊的、精确的或混合的查询语句,权重和阈值可以由用户给出。满足查询条件的记录将根据匹配度的降序输出。本系统的设计方法也可以推广到其他的数据库系统,如Oracle,Access等。     

一种在KNN查询处理中预估剪枝阈值的方法

KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一。与范围查询不同,KNN查询过程中缺乏固定的剪枝阈值。为达到剪枝的目的KNN算法使用保守的KNN距离剪枝,通常把到当前访问过的第K个最近点的距离作为剪枝阈值。传统的KNN查询处理算法在找到K个候选查询结果之前无法生成剪枝阈值,使得在此期间所有访问到的节点都被置入待访问节点队列。文中提出了在KNN查询处理中预估剪枝阈值的方法,该方法在找到K个候选查询结果前通过分析当前所访问过的页区域来预估剪枝阈值,试验表明使用预估剪枝阈值进行剪枝可有效缩短待访问节点队列的长度。     

分布式数据库知识

一、引言前二讲中,已向读者介绍了分布式数据库系统的基本概念和结构等方面的知识,本讲主要介绍分布式数据库的并发控制问题。分布式数据库的并发控制问题是分布式数据库设计和实现中的难题之一,它已越来越多地引起国内外许多人的重视,提出了许多解决这一问題的方法。首先,让我们看一下什么是数据库系统的并发控制。在一个数据库系统中,对数据库的查询与更新換     

一种在KNN查询处理中预估剪枝阈值的方法

KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一。与范围查询不同，KNN查询过程中缺乏固定的剪枝阈值。为达到剪枝的目的KNN算法使用保守的KNN距离剪枝，通常把到当前访问过的第K个最近点的距离作为剪枝阈值。传统的KNN查询处理算法在找到K个候选查询结果之前无法生成剪枝阈值，使得在此期间所有访问到的节点都被置入待访问节点队列。文中提出了在KNN查询处理中预估剪枝阈值的方法，该方法在找到K个候选查询结果前通过分析当前所访问过的页区域来预估剪枝阈值，试验表明使用预估剪枝阈值进行剪枝可有效缩短待访问节点队列的长度。     

非一致数据库的查询研究

提出的方法能灵活地进行数据库SQL查询,它可以干扰一系列的约束条件,并且这种方法能够允许用户假定一组约束和查询一起。系统重写这个查询去查找相应的与约束一致的数据。这个重写是SQL,以便能被商业数据库系统有效地优化和执行。使用TPC-H基准的数据和查询比较脏数据多粒度的执行性能,实验显示该方法是可行的。     

Web数据引擎的查询表达

当前Web的发展越来越快,Web上的信息也越来越丰富。如何能够快速准确地查找到有价值的信息成为一个人们普遍关心的问题,虽然目前有一些工具,例如各种搜索引擎,可以解决这个问题,但是结果都不太令人满意。另外,在数据库领域中,数据库技术可以支持复杂的查询请求,并且能够返回精确的查询结果。可否将数据库技术应用到Web上呢?从模型化的观点来看,在Web的某个局部的特定领域当中,数据库技术与搜索引擎技术有望结合起来实现更加精确的查询。为此,作者展开了相关的研究,设计并实现了一个原型系统WebView。论文主要介绍了该系统的查询表达部分的设计方法,通过采用三层模式框架和概念复合技术,使得用户可以很方便地表达比较复杂的查询请求。     

多媒体数据库查询技术研究

图像、声音、数字视频等是多媒体的基本要素。随着计算机技术的发展,多媒体数据库得到日益广泛的应用。文中对多媒体数据库系统的一个重要特性———查询进行了探讨,包括:在多媒体数据库中查询技术遇到的新问题、用户查询需求的描述方法,重点介绍了示例型查询系统和查询结果的表示方法,以及目前多媒体数据库应用的一个实例。     

Efficiently Querying Large XML Data Repositories: A Survey

Extensible markup language (XML) is emerging as a de facto standard for information exchange among various applications on the World Wide Web. There has been a growing need for developing high-performance techniques to query large XML data repositories efficiently. One important problem in XML query processing is twig pattern matching, that is, finding in an XML data tree D all matches that satisfy a specified twig (or path) query pattern Q. In this survey, we review, classify, and compare major techniques for twig pattern matching. Specifically, we consider two classes of major XML query processing techniques: the relational approach and the native approach. The relational approach directly utilizes existing relational database systems to store and query XML data, which enables the use of all important techniques that have been developed for relational databases, whereas in the native approach, specialized storage and query processing systems tailored for XML data are developed from scratch to further improve XML query performance. As implied by existing work, XML data querying and management are developing in the direction of integrating the relational approach with the native approach, which could result in higher query processing performance and also significantly reduce system reengineering costs.     

Domain independence and the relational calculus

Several alternative semantics (or interpretations) of the relational (domain) calculus are studied here. It is shown that they all have the same expressive power, i.e., the selection of any of the semantics neither gains nor loses expressive power.Since the domain is potentially infinite, the answer to a relational calculus query is sometimes infinite (and hence not a relation). The following approaches which guarantee the finiteness of answers to queries are studied here:output-restricted unlimited interpretation, domain independent queries, output-restricted finite andcountable invention, andlimited interpretation. Of particular interest is the output-restricted unlimited interpretation—although the output is restricted to the active domain of the input and query, the quantified variables range over the infinite underlying domain. While this is close to the intuitive interpretation given to calculus formulas, the naive approach to evaluating queries under this semantics calls for the impossible task of examining infinitely many values. We describe here a constructiion which, given a queryQ under the output-restricted unlimited interpretation, yields a domain independent queryQ, with length no more than exponential in the length ofQ, such thatQ andQ (under their respective semantics) express the same function.This work supported in part by NSF grants IST-85-11541 and IRI-87-19875Work by this author was also supported in part by NSF grant IRI-9109520     

Approximate query processing using wavelets

Approximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today's decision support systems (DSS). Most work in this area, however, has so far been limited in its query processing scope, typically focusing on specific forms of aggregate queries. Furthermore, conventional approaches based on sampling or histograms appear to be inherently limited when it comes to approximating the results of complex queries over high-dimensional DSS data sets. In this paper, we propose the use of multi-dimensional wavelets as an effective tool for general-purpose approximate query processing in modern, high-dimensional applications. Our approach is based on building wavelet-coefficient synopses of the data and using these synopses to provide approximate answers to queries. We develop novel query processing algorithms that operate directly on the wavelet-coefficient synopses of relational tables, allowing us to process arbitrarily complex queries entirely in the wavelet-coefficient domain. This guarantees extremely fast response times since our approximate query execution engine can do the bulk of its processing over compact sets of wavelet coefficients, essentially postponing the expansion into relational tuples until the end-result of the query. We also propose a novel wavelet decomposition algorithm that can build these synopses in an I/O-efficient manner. Finally, we conduct an extensive experimental study with synthetic as well as real-life data sets to determine the effectiveness of our wavelet-based approach compared to sampling and histograms. Our results demonstrate that our techniques: (1) provide approximate answers of better quality than either sampling or histograms; (2) offer query execution-time speedups of more than two orders of magnitude; and (3) guarantee extremely fast synopsis construction times that scale linearly with the size of the data. Received: 7 August 2000 / Accepted: 1 April 2001 Published online: 7 June 2001     

Providing quality responses with natural language interfaces: thenull value problem

An underlying relational database model and the database query language SQL are assumed, and methods are presented for responding with appropriate answers to null value responses. This is done by using a knowledge base based on RM/T, an extended relational model. The advantages of this approach are described. To demonstrate the utility of the knowledge base model, a simple knowledge base is constructed. The algorithms that provide additional information when a null answer is returned are detailed     

Evaluating refined queries in top-k retrieval systems

In many applications, users specify target values for certain attributes/features without requiring exact matches to these values in return. Instead, the result is typically a ranked list of "top k" objects that best match the specified feature values. User subjectivity is an important aspect of such queries, i.e., which objects are relevant to the user and which are not depends on the perception of the user. Due to the subjective nature of top-k queries, the answers returned by the system to an user query often do not satisfy the users need right away, either because the weights and the distance functions associated with the features do not accurately capture the users perception or because the specified target values do not fully capture her information need or both. In such cases, the user would like to refine the query and resubmit it in order to get back a better set of answers. While there has been a lot of research on query refinement models, there is no work that we are aware of on supporting refinement of top-k queries efficiently in a database system. Done naively, each "refined" query can be treated as a "starting" query and evaluated from scratch. We explore alternative approaches that significantly improve the cost of evaluating refined queries by exploiting the observation that the refined queries are not modified drastically from one iteration to another. Our experiments over a real-life multimedia data set show that the proposed techniques save more than 80 percent of the execution cost of refined queries over the naive approach and is more than an order of magnitude faster than a simple sequential scan.     

Answers to queries concerning uncertain and imprecise information in fuzzy relational databases

A model of an extended fuzzy relational database was proposed to accommodate uncertain and imprecise information. We use two supplementary measurements, satisfactory degree and extra degree, for determining the quality of answers to Select‐Project‐Join (SPJ) queries. The method of measurement determines how much satisfactory information is provided and how much truth information is required for a query. The answers to the query thus contain sure answers and maybe answers. The core of this study is the detailed discussion on the quality of answers in an extended fuzzy relation to query processing. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 647–668, 2005.     

Scalable keyword search on large data streams

It is widely recognized that the integration of information retrieval (IR) and database (DB) techniques provides users with a broad range of high quality services. Along this direction, IR-styled m-keyword query processing over a relational database in an rdbms framework has been well studied. It finds all hidden interconnected tuple structures, for example connected trees that contain keywords and are interconnected by sequences of primary/foreign key relationships among tuples. A new challenging issue is how to monitor events that are implicitly interrelated over an open-ended relational data stream for a user-given m-keyword query. Such a relational data stream is a sequence of tuple insertion/deletion operations. The difficulty of the problem is related to the number of costly joins to be processed over time when tuples are inserted and/or deleted. Such cost is mainly affected by three parameters, namely, the number of keywords, the maximum size of interconnected tuple structures, and the complexity of the database schema when it is viewed as a schema graph. In this paper, we propose new approaches. First, we propose a novel algorithm to efficiently determine all the joins that need to be processed for answering an m-keyword query. Second, we propose a new demand-driven approach to process such a query over a high speed relational data stream. We show that we can achieve high efficiency by significantly reducing the number of intermediate results when processing joins over a relational data stream. The proposed new techniques allow us to achieve high scalability in terms of both query plan generation and query plan execution. We conducted extensive experimental studies using synthetic data and real data to simulate a relational data stream. Our approach significantly outperforms existing algorithms.     

Probabilistic query answering over inconsistent databases

This paper presents a framework for querying inconsistent databases in the presence of functional dependencies. Most of the works dealing with the problem of extracting reliable information from inconsistent databases are based on the notion of repair, a minimal set of tuple insertions and deletions which leads the database to a consistent state (called repaired database), and the notion of consistent query answer, a query answer that can be obtained from every repaired database. In this work, both the notion of repair and query answer differ from the original ones. In the presence of functional dependencies, tuple deletions are the only operations that are performed in order to restore the consistency of an inconsistent database. However, deleting a tuple to remove an integrity violation potentially eliminates useful information in that tuple. In order to cope with this problem, we adopt a notion of repair, based on tuple updates, which allows us to better preserve information in the source database. A drawback of the notion of consistent query answer is that it does not allow us to discriminate among non-consistent answers, namely answers which can be obtained from a non-empty proper subset of the repaired databases. To obtain more informative query answers, we propose the notion of probabilistic query answer, that is query answers are tuples associated with probabilities. This new semantics of query answering over inconsistent databases allows us to give a measure of uncertainty to query answers. We show that the problem of computing probabilistic query answers is FP ^#P -complete. We also propose a technique for computing probabilistic answers to arbitrary relational algebra queries.     

APPROXIMATE-a query processor that produces monotonically improvingapproximate answers

APPROXIMATE, a query processor that makes approximate answers available if part of the database is unavailable, or if there is not enough time to produce an exact answer, is described. The processor implements approximate query processing, and the accuracy of the approximate result produced improves monotonically with the amount of data retrieved to produce the result. The monotone query processing algorithm of APPROXIMATE works within a standard relational algebra framework. APPROXIMATE maintains semantic information for approximate query processing at an underlying level, and can be implemented on a relational database system with little change to the relational architecture. It is shown how APPROXIMATE is implemented to make effective use of the semantic support. The additional overhead required by APPROXIMATE is described