分布式数据流连接查询算法

分布式处理是数据流管理系统发展的必然趋势。文章研究了分布式数据流的连接查询，提出DM3Join算法，它由2部分组成：一是通过分解并发的连接请求，合并相同的连接谓词，形成分布式查询操作算子；二是数据流在各分布式代理(Agent)中流转实现部分连接，并在查询引擎处组合成最终结果。DM3Join算法采用了一种类似路由表的结构执行窗口连接，由于可以共享中间结果，算法只需扫描数据1遍。分析和实验证明，该连接算法是高效的。     

数据流多连续查询优化技术

根据数据流连续达到、大小无界和实时性强的特点,引出数据流多连续查询的基本概念.针对多连续查询的特点和用户的需求,将多连续查询优化技术分为单流多查询和多流多查询.详细论述了单流过滤型多连续查询优化技术和基于共享的多流多连续查询优化技术,通过全面系统地分析每种优化算法的基本思想,得出每种查询技术的优缺点及适用场合.     

滑动窗口数据流上多极值查询资源共享策略研究

为了提高在同一数据流上同时计算多个连续极值查询(MAX或MIN)时的处理能力,对查询间资源共享技术进行了研究.提出了一种称为"关键点集"的裁剪策略,系统仅需保存少量数据即可满足所有查询的需要.发掘多个查询间的相似性和可共享的计算存储资源,提出了一个多极值查询处理算法MCEQP.采用链表结构实现的该算法,当一个新数据到达时最多需要O(M K)时间即可更新全部K个查询的结果,其中M为关键点集包含数据的个数.MCEQP采用触发器驱动的方式,只在某些特定时刻才需要计算因数据失效引起的查询结果变化,更新K个查询结果所需时间为O(K).理论分析和实验证明,对于滑动窗口数据流上的多个极值查询,MCEQP算法在降低存储开销和提高性能方面均优于现有的通用方法.     

XML数据磁盘存储结构LDF&B及其查询处理方法

提出了一种基于F&B索引的XML数据磁盘存储结构LDF&B,并给出其上的一系列查询处理算法.一方面,它摒除了传统存储方法中相同的值信息重复存储带来大量冗余的问题;另一方面,引入的同带索引与反向索引结构大大减少了树的遍历操作和中间结果集的大小,提高了查询处理效率.理论分析与实验结果均表明,提出的算法高效地实现了disk-based F&B中无法处理的含值的查询,分支查询处理效率也得到显著提高,并具有较好的伸缩性.     

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

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

一种空间更优的数据流查询包含编码区间索引

给出一种基于CEI(containment-encoded intervals)的存储优化的数据流查询区间索引结构.在数据流处理中涉及到大量的数值型区间查询操作,构造一个基于主存并支持快速查询的区间索引结构十分必要.对CEI索引结构而言,虽然支持高速查询,但存储利用率较低.针对该问题,提出了索引结构ACEI(advanced-CEI).在CEI索引结构的基础上,通过数据结构调整和参数优化,ACEI可在保持原有查询速度的前提下将CEI的空间复杂度由O(R+N(W/L+N(log(L))降为O(sqrt(R(N)+N(sqrt(W)).实验结果表明,ACEI结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.     

RFID事件流上一种扩展意义的子查询共享方法

提出一种扩展意义的子查询共享方法.该方法针对多复合事件查询共享后存储的问题,提出了复合事件图作为查询的内部表示;针对操作符不同、操作数相同的子查询共享不足的问题,通过分析不同复合事件查询、分析各种操作符之间的关系,提出了小事件的概念、并基于此给出了复合事件查询改写的规则和性质、小事件共享的方法以及共享的实现策略,实现了扩展意义的子查询共享.最后通过与典型算法的对比实验验证了本文所提方法的有效性.     

多查询共享技术研究综述

传统的数据库系统围绕单次查询的模型构建,独立地执行并发查询.由于该模型的限制,传统数据库无法一次对多个查询进行优化.多查询共享技术旨在共享查询之间的公共部分,从而达到提高系统整体响应时间和吞吐量的目的.将多查询执行模式分为两类,介绍了各自的原型系统——基于全局查询计划的多查询原型系统和以运算符为中心的多查询原型系统,并且讨论了两种系统的优势以及所适用场景.在之后的内容中,将多查询共享技术按照查询的各个阶段分为查询编译阶段中的多查询共享技术以及查询执行阶段中的多查询共享技术两大类.以这两个方向为线索,梳理了多查询计划的表示方法、多查询表达式合并、多查询共享算法、多查询优化等各种方向的研究成果.在此基础上,还介绍了共享查询技术在关系数据库和非关系数据库中的应用.最后,分析了共享查询技术面临的机遇和挑战.     

列存储数据仓库查询执行中重用缓冲区调度算法

查询的中间结果重用是提高查询效率的重要手段.现有列存储系统主要关注多查询计划间的中间结果重用,忽略了单一查询计划执行过程中大量可重复访问的中间结果.单一查询中的中间结果具有确定性高、结果大小可估计的特征,非常适合作为重用的对象.为此,针对列存储数据仓库单一查询计划执行过程中的中间结果重用问题,提出了一个重用缓冲区空间的...     

存储容量可扩展区块链系统的高效查询模型

区块链技术是目前计算机领域的研究热点,其实现了去中心化,并且能够安全地存储数字信息,有效降低现实经济的信任成本.提出一种区块链存储容量可扩展模型的高效查询方法——ElasticQM.此查询模型由用户层、查询层、存储层和数据层这4个模块组成.在用户层,模型将查询结果缓存,加快再次查询相同数据时的查询速度;在查询层,模型采用容量可扩展区块链模型的全局查询优化算法,增加了查询超级节点、查询验证节点和查询叶子节点这3种节点角色,提高了查询效率;在存储层,模型改进了区块链的容量可扩展模型ElasticChain的数据存储过程,实现了存储的可扩展性,并减少了占用的存储空间;在数据层,提出一种基于B-M树的区块链存储结构,并给出了B-M树的建立算法和基于B-M树的查找算法,基于B-M树的存储结构,区块链会在进行块内局部查找时提高区块链的查询速度.最后,通过在多节点不同数据量的区块链中查询的实验结果表明,ElasticQM查询方法具有高效的查询效率.     

P2P环境下数据管理系统上的Top-k查询

目前大多数P2P系统只提供文件的共享,缺乏数据管理能力.基于关系数据库上的关键搜索,本文提出了一种在P2P环境下共享数据库的新框架,其中每个节点上的数据库被看成是一个文档集,用户不用考虑数据库的模式结构信念,简化了不同节点数据库模式间的映射过程,能更好地适应P2P的分散和动态特性.将基于直方图的分层Top-k查询算法扩展到P2P环境下的数据库管理系统上,文档集和数据库的查询被统一起来,一致对待.在查询处理期间,直方图可以自动更新,同时根据查询结果,邻居节点可以自调整,具有自适应性.实验结果表明,基于关键词的数据库共享突破了传统的数据库共享模式,简化了数据访问方式,而基于直方图的Top-k查询算法提高了查询效率.     

主存OLAP系统中what-if查询处理策略

What-If分析能够提供比传统的OLAP(on-line analysis processing)分析更加有意义的决策支持信息.基于历史数据的应用场景假设分析需要更加有效的what-if数据视图生成机制的支持.在传统的delta表合并算法的基础上,提出了基于内存记录指针的deltaMap算法来提高what-if数据视图的合并性能.根据OLAP分析的应用特点,提出了pre-merge算法来处理支持分布式计算的聚集运算.根据不同的假设更新类型,对查询重写算法和△cube算法作了详细的性能测试并进行了全面的性能分析对比,在此基础上提出了what-if分析的代价模型,以应用场景模式、假设更新率、假设更新复杂度、查询结果集的基数作为参数,有效地描述系统what-if查询处理策略,为what-if分析的解决方案提供了一个可行的框架结构.     

基于XQuery的异构数据源查询处理

异构数据源的集成问题是当前数据处理领域内研究的热点,它能更有效地利用信息资源,更好地实现数据共享。介绍一种基于Mediator-Wrapper中间层的异构数据源集成系统框架,对XQuery查询处理过程及其关键问题,如查询分解和优化技术进行深入研究,并结合实例进一步说明异构数据源中查询分解和优化的具体实现。     

传感器网络中一种支持多分辨率区域查询的数据存储方法

在传感器网络中,考虑到节点的通信开销在节点总能量开销中的比重大,以及用户由粗到细分辨率的不同查询需求,有必要在传感器网络中建立支持多分辨率的数据存储机制.首先提出了一种支持多分辨率的数据压缩存储策略 MDCS,节点基于 MDCS在网内产生多分辨率的近似结果;其次,给出了一种基于 MDCS的区域查询处理方法,根据用户给定的分辨率阈值去网内作区域查询处理,并将结果返回给用户.模拟实验表明,基于 MDCS的区域查询处理方法能够高效、低能耗地支持多分辨率的区域查询操作.     

布隆过滤器研究综述

布隆过滤器（BF）是一种基于哈希策略的二进制向量数据结构,凭借分摊哈希碰撞的思想、存在单向误判性的特点以及极小常数查询时间复杂度,常用于表示集合元素并作为进行集合元素查询操作的“加速器”。作为计算机工程中解决集合元素查询问题最好的数学工具,BF在网络工程、存储系统、数据库、文件系统、分布式系统等领域得到了广泛的应用和发展。近几年来,为了适用于各种硬件环境和应用场景,BF出现了大量基于改变结构、优化算法等思想的变种方案。随着大数据时代的发展,对BF自身特点和操作逻辑进行改进已经成为现有集合元素查询研究的一个重要方向。     

不确定数据流上的并行Skyline查询算法

不确定数据流上的Skyline查询技术逐步引起研究者的关注,传统的集中式流处理算法难以满足海量数据的查询需求,并且云计算所提供的海量计算资源和有效的存储管理模式,为研究并行Skyline查询技术提供了充足的条件。基于上述事实,提出了一种不确定数据流上的并行Skyline查询算法(parallel Skyline over uncertain data streams,PSUDS)。该算法通过交叉划分滑动窗口的方式,将集中式流查询转化为并行处理,以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明,该算法具有较好的并行可扩展性。     

基于图数据库的在线族谱编录系统

针对目前国内族谱系统中数据共享度不高、扩展性不好、编录效率较低等问题,提出并实现了一种基于浏览器/服务器(B/S)架构和图数据库的在线族谱编录系统.首先,该系统采用B/S架构,支持多人在线协同录入,提高了数据录入效率;其次,系统使用数据库存储数据,便于集中管理和统计检索,提高了数据的共享程度;然后,考虑到族谱数据具有图的结构特性,在系统中采用图数据库进行管理,大大提高了数据处理效率;最后,使用真实族谱数据进行了系统的效率对比,验证了系统的有效性.在实验中,使用了约20万人的刘氏族谱数据,对关系数据库PostgreSQL和图数据库Neo4j管理数据进行了存储和查询的效率对比.实验结果表明,Neo4j比PostgreSQL节省约50%的存储空间,而在人物后代查询、人物祖先查询、人物亲缘关系查询以及人物后代性别统计4种常见查询中,使用Neo4j的平均响应时间约为基于PostgreSQL数据库的20%、80%、16%和15%.由此可知,基于图数据库的在线族谱编录系统可用于高效处理大量族谱数据,并且支持多用户在线协同编录.     

RFID数据仓库上的多时空粒度近似聚集查询

随着物联网的发展,以RFID为代表的物联网传感器数据的存储、查询、处理等课题正成为研究的热点。结合数据仓库时空维度和列存储的思想,建立了一种列式RFID数据仓库,并根据RFID的时空特性,设计了一种支持连续聚集查询的多时空粒度数据结构和快速更新算法。它去除了传统聚集查询的部分冗余操作,适合处理大规模RFID数据仓库上的连续实时聚集查询。通过实验证明,该模型与算法在一些典型的物联网应用中取得了较高的效率,可广泛地适用于海量RFID数据仓库上的OLAP分析。     

Adaptive workload allocation in query processing in autonomous heterogeneous environments

The increasing prevalence of networked storage and computational resources, along with middleware for managing resource access and sharing, raises the prospect that queries can be run over resources obtained on demand, rather than on dedicated infrastructures. However, the movement of query processing into non-dedicated environments means that it is necessary to take account of the partial information and unstable conditions that characterise autonomous, shared, distributed settings. Thus, query processing on grid platforms needs to be adaptive, revising evaluation strategies at query runtime in response to the evolving environment, such as changes to machine load and availability. To address this challenge, adaptive techniques are described that: (i) balance load across plan partitions supporting intra-operator parallelism; (ii) remove bottlenecks in pipelined plans supporting inter-operator parallelism; and (iii) combine the two aforementioned techniques. The approach has been empirically evaluated in a grid-enabled adaptive query processor.