基于聚类的非一致性数据库查询重写

在非一致性数据库上,以元组匹配技术所产生的聚类和概率数据库的元组概率为基础,提出了可信聚类概率和可重写查询判断方法.考虑了最普通的IC情况（key-to-key和nonkey-to-key）,给出了无连接和有连接的查询重写方法.连接查询重写方法缩小了用于连接的中间结果集中可信聚类的元组数量,有效地提高了查询性能.实验使用TPC-H决策支持基准的数据和查询进行性能研究,分析了聚类基数和数据库尺寸等相关因素的影响,结果显示方法是有效的.     

基于聚类的非一致性数据库聚集查询重写

在聚类和非一致性数据库无聚集查询基础上提出聚集查询重写方法.通过聚集值范围限定了最值和期望值,给出无连接和有连接的聚集查询重写策略.聚集重写查询通过分析聚类中可能元组和分组属性来过滤聚类,计算初始分组属性的最值和期望值.实验使用TPC-H决策支持基准进行性能研究,分析了聚类基数和数据库尺寸等因素的影响.结果显示尽管重写查询显著地比初始查询的执行时间长,但还是可以接受的,表明方法是有效的.     

基于聚类的非清洁数据库的聚集查询处理算法

现实数据库中的不完整数据、不一致数据、重复数据等非清洁数据为数据库的有效使用带来了影响,从包含非清洁数据的数据库中得到满足清洁度要求的统计分析结果,为数据库研究带来了新的挑战,聚集查询是统计分析的基础.面向非清洁数据,提出了有清洁度保证的聚集查询处理算法,用于处理包含group by子句的聚集查询.考虑到在非清洁数据中,同一个元组可能属于不同的分组,提出的方法是利用可重叠聚类的方法将数据库中的元组加以分组,从而得到考虑数据非清洁性的分组,以及基于这些分组计算得到的聚集结果及其以概率表达的清洁度.提出的方法适用于多种聚集函数以及包含选择条件的聚集查询.通过实验验证了方法的效率.     

滑动窗口模型下的概率数据流聚类

提出一种基于滑动窗口的概率数据流聚类方法PWStream。PWStream采用聚类特征指数直方图保存最近数据元组的信息摘要,在允许的误差范围内删除过期的数据元组;并针对数据流上概率元组提出强簇、过渡簇和弱簇的概念,设计了一种基于距离和存在概率的簇选择策略,从而可以发现更多的强簇。理论分析和实验结果表明,该方法具有良好的聚类质量和较快的数据处理能力。     

采用元组聚类的增量式数据分区方法

数据分区是提升数据库可扩展能力的有效方法。在事务查询密集的系统中,合理的分区策略可减少分布式事务查询数量,并提高事务查询响应速度。提出了一种基于元组聚类的增量式分区方法,通过将元组聚簇和采用分区感知的数据筛选策略来降低算法的复杂度。首先依据时间窗口模型聚类元组,并构建簇节点图,然后利用分区感知策略对图进行删减,最后采用图划分算法对图进行子图划分来得到分区。与现有方法相比,该方法减少了分区响应时间,保证了较少的分布式事务数量,并提高了分区事务查询速度。     

基于改进决策树算法的Web数据库查询结果自动分类方法

为了解决Web数据库多查询结果问题,提出了一种基于改进决策树算法的Web数据库查询结果自动分类方法.该方法在离线阶段分析系统中所有用户的查询历史并聚合语义上相似的查询,根据聚合的查询将原始数据划分成多个元组聚类,每个元组聚类对应一种类型的用户偏好.当查询到来时,基于离线阶段划分的元组聚类,利用改进的决策树算法在查询结果集上自动构建一个带标签的分层分类树,使得用户能够通过检查标签的方式快速选择和定位其所需信息.实验结果表明,提出的分类方法具有较低的搜索代价和较好的分类效果,能够有效地满足不同类型用户的个性化查询需求.     

脏数据库的查询方法研究

对于给定的约束,多个数据源分别是一致的,但是在它们集成时可能是脏的.已经存在的技术能够通过特别的方法识别出数据集成环境下的脏数据,但是不能进行有效处理.分析查询对应的连接图是否为有向连接图,判断查询是否可重写,并且给出了元组概率计算和基本查询重写方法.使用TPC-H基准的数据和查询比较脏数据多粒度的执行性能,实验显示方法是可行的.     

基于x-tuple的概率阈值top-k查询算法

不确定数据库中的概率阈值top-k查询是计算元组排在前k位的概率和,返回概率和不小于p的元组,但现有的查询语义没有将x-tuple内的元组进行整体处理.针对该情况,定义一种新的查询语义——概率阈值x-top-k查询,并给出查询处理算法.在该查询语义下采用动态规划方法求取x-tuple内每个元组排在前k位的概率和,对其进行聚集后做概率阈值top-k查询,并利用观察法、最大上限值等剪枝方法进行优化.实验结果表明,该算法平均扫描全体数据集中60％的数据即可返回正确结果集,证明其查询处理效率较高.     

基于非一致性数据库的概率查询策略与算法

完整性约束是保证关系型数据库中数据确定性的重要条件,现实中存在大量不确定、不满足完整约束条件,但仍具有使用价值。结合概率数据库理论,提出了一种新的针对非一致性数据库的查询策略,利用并、交、差、选择、投影、连接等约束方法,对非一致性数据进行修复,四元组概率计算方法和概率查询重写技术弥补了非一致性数据库查询的不足,减少了数据冲突的发生机率。     

基于相似度的粗关系数据库的近似查询

基于数据库理论和粗集方法研究了粗关系数据库中不确定数据的存储、索引和检索。提出了分别采用邻接表和十字链表实现粗关系数据库中属性值等价类和元组数据的存储;借助汉明距离和聚类方法,提出了实现粗关系数据库索引的方法;提出一种基于Rough集中的上、下近似计算数据间的相似度,并基于相似度给出了对粗关系数据库进行查询的模型,设计了相应的查询算法。最后,通过一个具体实例说明了查询算法的可行性和有效性。     

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.     

Combining intensional with extensional query evaluation in tuple independent probabilistic databases

In this paper, we prove that a query plan is safe in tuple independent probabilistic databases if and only if its every answer tuple is tree structured in probabilistic graphical models. We classify hierarchical queries into core and non-core hierarchical queries and show that the existing methods can only generate safe plans for core hierarchical queries. Inspired by the bucket elimination framework, we give the sufficient and necessary conditions for the answer relation of every candidate sub-query to be used as a base relation. Finally, the proposed algorithm generates safe plans for extensional query evaluation on non-boolean hierarchical queries and invokes the SPROUT algorithm [24] for intensional query evaluation on boolean queries. A case study on the TPC-H benchmark reveals that the safe plans of Q7 and Q8 can be evaluated efficiently. Furthermore, extensive experiments show that safe plans generated by the proposed algorithm scale well.     

About yes/no queries against possibilistic databases

This article is concerned with the handling of imprecise information in databases. The need for dealing with imprecise data is more and more acknowledged in order to cope with real data, even if commercial systems are most of the time unable to manage them. Here, the possibilistic setting is taken into consideration because it is less demanding than the probabilistic one. Then, any imprecise piece of information is modeled as a possibility distribution intended for constraining the more or less acceptable values. Such a possibilistic database has a natural interpretation in terms of a set of regular databases, which provides the basic gateway to interpret queries. However, if this approach is sound, it is not realistic, and it is necessary to consider restricted queries for which a calculus grounded on the possibilistic database, that is, where the operators work directly on possibilistic relations, is feasible. Extended yes/no queries are dealt with here, where their general form is: “to what extent is it possible and certain that tuple t (given) belongs to the answer to Q,” where Q is an algebraic relational query. A strategy for processing such queries efficiently is proposed under some assumptions as to the operators appearing in Q. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 691–721, 2007.     

基于属性相关度的Web数据库大小估算方法

提出了一种基于词频统计的方法以估算Web数据库的规模.通过分析Web数据库查询接口中属性之间的相关度来获取某个属性上的一组随机样本;并对该属性分别提交由前k位高频词形成的试探查询以估算Web数据库中记录的总数.通过在几个真实的Web数据库上进行实验验证,说明该方法可以准确地估算出Web数据库的大小.     

PrDB: managing and exploiting rich correlations in probabilistic databases

Due to numerous applications producing noisy data, e.g., sensor data, experimental data, data from uncurated sources, information extraction, etc., there has been a surge of interest in the development of probabilistic databases. Most probabilistic database models proposed to date, however, fail to meet the challenges of real-world applications on two counts: (1) they often restrict the kinds of uncertainty that the user can represent; and (2) the query processing algorithms often cannot scale up to the needs of the application. In this work, we define a probabilistic database model, PrDB, that uses graphical models, a state-of-the-art probabilistic modeling technique developed within the statistics and machine learning community, to model uncertain data. We show how this results in a rich, complex yet compact probabilistic database model, which can capture the commonly occurring uncertainty models (tuple uncertainty, attribute uncertainty), more complex models (correlated tuples and attributes) and allows compact representation (shared and schema-level correlations). In addition, we show how query evaluation in PrDB translates into inference in an appropriately augmented graphical model. This allows us to easily use any of a myriad of exact and approximate inference algorithms developed within the graphical modeling community. While probabilistic inference provides a generic approach to solving queries, we show how the use of shared correlations, together with a novel inference algorithm that we developed based on bisimulation, can speed query processing significantly. We present a comprehensive experimental evaluation of the proposed techniques and show that even with a few shared correlations, significant speedups are possible.     

Integrated Video and Text for Content-based Access to Video Databases

This paper introduces a new approach to realize video databases. The approach consists of a VideoText data model based on free text annotations associated with logical video segments and a corresponding query language. Traditional database techniques are inadequate for exploiting queries on unstructured data such as video, supporting temporal queries, and ranking query results according to their relevance to the query. In this paper, we propose to use information retrieval techniques to provide such features and to extend the query language to accommodate interval queries that are particularly suited to video data. Algorithms are provided to show how user queries are evaluated. Finally, a generic and modular video database architecture which is based on VideoText data model is described.     

ArchIS: an XML-based approach to transaction-time temporal database systems

Effective support for temporal applications by database systems represents an important technical objective that is difficult to achieve since it requires an integrated solution for several problems, including (i) expressive temporal representations and data models, (ii) powerful languages for temporal queries and snapshot queries, (iii) indexing, clustering and query optimization techniques for managing temporal information efficiently, and (iv) architectures that bring together the different pieces of enabling technology into a robust system. In this paper, we present the ArchIS system that achieves these objectives by supporting a temporally grouped data model on top of RDBMS. ArchIS’ architecture uses (a) XML to support temporally grouped (virtual) representations of the database history, (b) XQuery to express powerful temporal queries on such views, (c) temporal clustering and indexing techniques for managing the actual historical data in a relational database, and (d) SQL/XML for executing the queries on the XML views as equivalent queries on the relational database. The performance studies presented in the paper show that ArchIS is quite effective at storing and retrieving under complex query conditions the transaction-time history of relational databases, and can also assure excellent storage efficiency by providing compression as an option. This approach achieves full-functionality transaction-time databases without requiring temporal extensions in XML or database standards, and provides critical support to emerging application areas such as RFID.     

Discovering Interesting Relationships among Deep Web Databases: A Source-Biased Approach

The escalation of deep web databases has been phenomenal over the last decade, spawning a growing interest in automated discovery of interesting relationships among available deep web databases. Unlike the “surface” web of static pages, these deep web databases provide data through a web-based query interface and account for a huge portion of all web content. This paper presents a novel source-biased approach to efficiently discover interesting relationships among web-enabled databases on the deep web. Our approach supports a relationship-centric view over a collection of deep web databases through source-biased database analysis and exploration. Our source-biased approach has three unique features: First, we develop source-biased probing techniques, which allow us to determine in very few interactions whether a target database is relevant to the source database by probing the target with very precise probes. Second, we introduce source-biased relevance metrics to evaluate the relevance of deep web databases discovered, to identify interesting types of source-biased relationships for a collection of deep web databases, and to rank them accordingly. The source-biased relationships discovered not only present value-added metadata for each deep web database but can also provide direct support for personalized relationship-centric queries. Third, but not least, we also develop a performance optimization using source-biased probing with focal terms to further improve the effectiveness of the basic source-biased model. A prototype system is designed for crawling, probing, and supporting relationship-centric queries over deep web databases using the source-biased approach. Our experiments evaluate the effectiveness of the proposed source-biased analysis and discovery model, showing that the source-biased approach outperforms query-biased probing and unbiased probing.