一种基于概率模型的预测性时空区域查询处理

提出了一种基于概率模型的预测性时空区域查询处理方法.该方法采用Filter-Refinement方式来处理查询.首先,从数据库中选择所有可能满足查询的候选移动对象;然后,根据概率模型中定义的方法来计算候选移动对象满足查询的概率;最后,根据查询中指定的最小概率阈值过滤候选移动对象并返回查询结果.该概率模型将移动对象未来可能出现的位置定义为一个随机变量,并给出了计算移动对象在两种不同的运动模式下满足查询的概率值的方法.还提出了一种通过对大量历史轨迹抽样来获得概率密度函数(probability density function,简称PDF)的轨迹分析算法,并设计了概率密度函数索引STP-Index(spatio-temporal PDF-index).该索引能够有效地提高轨迹分析算法和概率计算的效率.实验结果表明,该查询处理方法能够有效地支持预测性时空区域查询的处理,提高查询结果的正确性,特别适合于具有较小的空间区域和长时间范围的预测性时空区域查询.     

一种移动对象数据库全时态区域查询处理方法

全时态区域查询方法是可以同时支持对于移动对象过去、现在以及预测性未来信息区域查询处理的方法,是移动对象数据管理的一个重要方面.在移动对象数据库领域,大量技术被提出以支持历史信息查询或未来信息预测,但是缺乏对于全时态区域查询方法的研究.提出一个可以支持精确区域查询的移动对象全时态查询方法,并支持对于历史信息的轨迹查询.为提高查询效率,提出索引结构PPF-index.在PPF-index中,首先在移动对象信息到达时,利用提出的TB_TPR-tree结构来索引移动对象现在以及预测性未来信息;其次,历史轨迹信息经过轨迹切分后利用3D R-tree进行索引;最后,提出基于PPF-index索引结构的全时态区域查询算法.全时态区域查询算法中的时间范围不同,需要访问的索引结构也不同.实验结果表明,PPF-index可以高效支持全时态查询,并具有很高的更新效率.     

空间数据库中全局最近邻查询处理方法

空间数据库中基于层次化索引结构的全局最近邻(all-nearest-neighbor, All-NN)计算采用单节点展开策略的嵌套循环技术来降低计算开销.在同一数据集合的全局最近邻计算中,基于索引结构带来的对象空间位置临近性特点,抛弃传统理论距离裁剪规则和嵌套循环技术来减少计算和索引节点访问开销.提出了采用局部计算和完备计算两阶段的计算模型来获得全局最近邻结果.首先以叶节点为单位,采用扫描线算法获得节点内部所有对象的局部最近邻结果,然后根据计算结果得到启发式裁剪距离.在第2阶段采用层次化过滤的范围查询算法来获取外部的(可能的)最近邻对象.实验与分析表明该方法可以很好地支持不同种类、大小、分布的数据集合All-NN查询处理,具有良好的实用价值.     

一种面向动态连续查询的查询索引

针对当前面向连续查询的查询索引不适应查询动态变化的问题,提出一种能承受频繁更新的动态连续查询索引。为实现该索引,设计一种基于网格和树的索引结构,该索引结构继承了网格结构的高效更新性能的优点,并通过继承树的特性,克服网格结构高空间开销的问题。实验结果表明,该连续查询索引比基于网格的连续查询索引节省空间开销约一个数量级;比基于树的连续查询索引更新效率提高约70%,查询性能提高约25%。     

RB树:一种支持空间近似关键字查询的外存索引

空间近似关键字查询包含一个空间条件和一组关键字相似性条件,这种查询在空间数据库中返回同时满足以下条件的对象:1)对象的位置信息满足查询中的空间条件;2)对于查询中的任何一个关键字,对象中至少包含一个关键字与其相似度大于给定阈值.随着当前数据的爆炸性增长,空间数据库无法完整地存放在内存中,因此空间数据库需要支持空间近似关键字查询的外存索引.目前,还没有在外存中支持精确的空间近似关键字查询的索引结构.设计了一种新型的外存索引RB树,在外存中支持精确的空间近似关键字查询.RB树支持的空间近似关键字查询包括多种空间条件,如范围查询、NN查询,同时支持多种关键字相似性度量,包括编辑距离、规范化编辑距离等.通过真实数据中的性能测试验证了RB树的效率.     

一种中文数据库查询语言的优化处理方法

本文介绍一种中文数据库查询语言的优化处理方法。该方法能将用户输入的查询条件自动分解成ＳＱＬ语言中条件子句ＷＨＥＲＥ和分类条件子句ＨＡＶＩＮＧ，以提高查询效率。     

一种基于CHORD系统的多维相似查询处理方法

如何在对等计算环境下处理多维空间中的相似查询是目前学术界的研究热点之一。本文通过基于代表点的多维空间划分策略,提出了一种对等计算环境下的分布式多维索引技术,实现了一种基于CHORD系统的多维相似查询处理。仿真实验证明了本文提出的方法的有效性。     

一种支持对象代理数据库高效查询处理的索引结构

文中为对象代理数据库提出了一种新的索引结构--路径导航索引(Path Navigation Index,PNI),能够克服路径表达式计算开销大的缺点,使对象代理数据库跨类查询与代理对象查询具备高效的查询性能.PNI索引建立在代理层次的路径实例之上,包括Path-Instance-Table,Identity-Index和Attribute-Index 3个组成部分.Path-Instance-Table能够物化存储路径实例,避免查询处理过程中冗余的对象导航遍历.Identity-Index与Attribute-Index用于对路径实例进行关联检索,能够避免对象导航过程中的条件判断.通过实验分析了影响路径表达式计算的不同因素,实验结果表明,利用PNI索引计算路径表达式的方法在多数情况下性能要优于现有计算方法,尤其适用于带谓词的路径表达式计算.     

一种密文数据库的查询方法

本文在密文索引的基础上,提出了一种“分散索引机制”及其查询方法,并对分散索引查询和集中索引查询作了详尽的比较和分析,说明了“分散索引机制”及其查询方法的优越性。     

Query Processing Techniques for Multimedia Presentations

A multimedia presentation is a synchronized, and possibly interactive, delivery of multimedia data to users. We expect that, in the future, multimedia presentations will be stored into and queried from multimedia databases. In an earlier work, we have designed a graphical query language, called GVISUAL, that allows users to query multimedia presentations based on content information. In this paper, we discuss GVISUAL query processing techniques for multimedia presentations. More specifically, we discuss the translation of GVISUAL queries into an operator-based language, called O-Algebra, with three new operators, and efficient implementations of the new O-Algebra operators using a coding system called nodecodes.     

Continuous Query Processing of Spatio-Temporal Data Streams in PLACE

The tremendous increase in the use of cellular phones, GPS-like devices, and RFIDs results in highly dynamic environments where objects as well as queries are continuously moving. In this paper, we present a continuous query processor designed specifically for highly dynamic environments (e.g., location-aware environments). We implemented the proposed continuous query processor inside the PLACE server (Pervasive Location-Aware Computing Environments); a scalable location-aware database server developed at Purdue University. The PLACE server extends data streaming management systems to support location-aware environments. These environments are characterized by the wide variety of continuous spatio-temporal queries and the unbounded spatio-temporal streams. The proposed continuous query processor includes: (1) New incremental spatio-temporal operators to support a wide variety of continuous spatio-temporal queries, (2) Extended semantics of sliding window queries to deal with spatial sliding windows as well as temporal sliding windows, and (3) A shared-execution framework for scalable execution of a set of concurrent continuous spatio-temporal queries. Experimental evaluation shows promising performance of the continuous query processor of the PLACE server. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

一种新的面向集合的空间关键字查询方法

面向集合的空间关键字查询处理是数据库领域近年来的热点研究课题.针对已有查询的不足,定义一种新的描述集合质量的Cost函数,提出一种新的面向集合的空间关键字查询方法,并证明基于该Cost函数的查询问题是NP完全问题.对于给定的对象数据集D={o1,o2,…,on},q为包含位置信息和关键字集合的查询点,查询返回的是在对象数据集D中,既满足查询点q的全部关键字,又能成为q的近邻且较紧凑的对象集合.为处理该查询,利用最小圆覆盖包含全部关键字的对象集合,并采用有效的裁剪策略分别实现了该查询的近似查询算法和精确查询算法.最后通过实验验证了所提算法的有效性.     

Top-Down Query Processing in First-Order Deductive Databases under the DWFS

A top-down query-processing method for first-order deductive databases under the disjunctive well-founded semantics (DWFS) is presented. The method is based on a characterization of the DWFS in terms of the Gelfond–Lifschitz transformation and employs a hyperresolution-like operator and quasi-cyclic trees to handle minimal model processing. The method is correct and complete and can be guaranteed to terminate given certain mild constraints on the format of database rules. The efficiency of the method is enhanced by the fact that large parts of the search tree are naturally grounded, even for first-order queries and databases. In the case of a grounded yes/no answer, the search tree becomes nongrounded only if processing enters the definite part of the database. For finite propositional databases the method runs in polynomial space. Efficiency may be enhanced by the application of partial compilation.     

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.     

云计算中面向隐私保护的查询处理技术研究

在云计算环境中既能同时保护数据隐私和用户查询隐私,又能提供给用户满足需求的查询结果是云计算中面向隐私保护的查询处理的关键问题。对云计算中面向隐私保护的查询处理技术的若干关键问题进行了全面的调研,包括数据库索引技术与查询优化、基于加密的隐私保护技术、基于安全多方计算的隐私保护技术以及查询结果完整性验证技术。分析了云计算中面向隐私保护的查询处理技术的挑战性问题,指明了未来研究方向。     

Duality for Goal-Driven Query Processing in Disjunctive Deductive Databases

Bottom-up query-answering procedures tend to explore a much larger search space than what is strictly needed. Top-down processing methods use the query to perform a more focused search that can result in more efficient query answering. Given a disjunctive deductive database, DB, and a query, Q, we establish a strong connection between model generation and clause derivability in two different representations of DB and Q. This allows us to use a bottom-up procedure for evaluating Q against DB in a top-down fashion. The approach requires no extensive rewriting of the input theory and introduces no new predicates. Rather, it is based on a certain duality principle for interpreting logical connectives. The duality transformation is achieved by reversing the direction of implication arrows in the clauses representing both the theory and the negation of the query. The application of a generic bottom-up procedure to the transformed clause set results in top-down query answering. Under favorable conditions efficiency gains are substantial, as shown by our preliminary testing. We give the logical meaning of the duality transformation and point to the conditions and sources of improved efficiency. We show how the duality approach can be used for refined query answering by specifying the minimal conditions (weakest updates) to DB under which Q becomes derivable. This is shown to be useful for view updates in disjunctive deductive databases as well as for other interesting applications.     

路网中空间关键字连续范围查询算法研究

空间关键字查询相对传统的位置相关查询而言更能满足实际查询处理的需要。着重探讨路网中结合距离和关键字相似度两个因素的空间关键字查询处理问题,提出解决路网中空间关键字连续范围查询(CRSKQ)的有效方法。提出了一个综合考虑了路网上的道路、对象和路网的连通性的路网模型以支持CRSKQ查询的处理。为了实现连续监控,所提出的算法包括两个阶段,即初始结果获取和查询结果连续监控。初始结果监控阶段,通过路网扩展和关键字匹配寻找满足要求的结果对象;在连续监控阶段,充分利用前面时刻的查询结果来减小连续监控的代价。模拟实验表明,所提出的算法是有效的。     

网内查询处理中的一种基于数据流共享的过滤查询算法

网内查询处理需要让网络中各个节点共同承担查询任务,其基本问题是如何采取合适的策略将各个查询映射到网络节点上,以使得网络传输数据量和网络延迟达到最小.基于在查询间共享数据流的思想,提出了基于查询包含和查询合并的数据流共享策略,并建立了相应的收益模型,最后通过实验分析对比了两种策略的运行效果.