基于自动机的XML数据流查询处理技术

XML已成为Internet上数据表示和交换的标准,在许多涉及 海量数据交换的重要应用系统中,XML数据是以流的形式存在的,如何在XML数据流上有效地 执行大量的XPath查询,成为数据流应用中一个迫切需要解决的关键问题.针对XML数据 流的特点,分析了基于确定有穷自动机DFA和非确定有穷自动机NFA的XML数据流查询处理技术,总结了两种查询处理技术的特点并给出了下一步研究目标.     

一种数据流块查询操作符的设计与实现

为了使块操作符和状态操作符有效处理连续到达的数据流元组,研究了基于Punctuation的数据流连续查询处理技术.描述了分组操作符Group-by和状态操作符Join的处理规则,设计了相关的数据结构,给出了基于Punctuation的块操作符Group-by和状态操作符Join的处理过程,并对执行结果进行了分析和测试.结果表明,使用基于Punctuation的查询处理技术有助于提高块操作符和状态操作符对数据流的查询处理性能.     

数据流窗口语义及查询引擎的实现

数据流窗口主要采用了基于时间、元组和分组的3种驱动形式,如果仅采用一种驱动形式难以正确表达数据流查询语义,因此,针对数据流查询语义的不完备性,从窗口的查询级、数据级和系统级定义了一个完整的窗口语义框架来解决语义差异,并提出了基于主存数据库的分组窗口驱动的实现,最后通过实验验证了该方法.     

RFID数据流管理关键技术

新一代传感器和RFID（无线射频识别）技术为人们提供了强大的感知、理解并管理世界的能力,同时RFID数据具有不确定性、冗余性、蕴含时空性、需要在线处理等特点,也为数据管理提出了许多挑战.本文回顾了RFID数据管理的研究发展现状,从数据流连续查询、物化视图推导规则、复杂事件处理等角度分析了RFID数据管理涉及到的几种关键技术,最后介绍一种数据流驱动的RFID复杂事件处理系统（GodEye Event Processor）的设计思想,将RFID事件查询设计成复杂连续查询,能够有效捕捉并处理复杂RFID事件.     

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

分布式处理是数据流管理系统发展的必然趋势.研究了分布式数据流系统中的基于滑动窗口的连接操作,提出了DMS-Join算法.通过将多连接操作中的子操作分解置于不同的网络节点上,以减少数据的传输.分析与实验结果表明,DMS-Join算法具有较高的查询性能.     

数据流滑动窗口连接查询降载策略研究

主要研究了在有限内存条件下数据流滑动窗口的近似连接查询,即数据流滑动窗口连接查询的降载问题。通过对连接属性域的划分,根据数据元组的连接属性值在属性域中的数据分布来决定每个数据元组进入参加连接运算的滑动窗口的概率,给出了一种面向数据流滑动窗口连接查询的语义降载策略。与已有的语义降载策略相比,文中给出的降载策略所需的数据统计信息较少,连接运算的结果数据元组便于进一步进行其它查询处理,并且对于各种倾斜(skew)参数的数据分布和不同程度的系统超载都有较好的适应性。理论分析和实验结果表明,该降载策略对数据流滑动窗口连接查询的降载处理具有较高的有效性和实用性。     

数据流上基于遗传算法的并行查询优化技术

传统数据库中存储的是相对静态的记录集,这些记录没有预先定义的时间概念,除非时间属性被显示地加上去.虽然这个模型能够较好地表示商业数据库和个人信息存储库,然而它对快速变化的数据流进行在线分析的支持存在很多限制.因此,需要对已有技术进行扩展研究,构建出新的管理系统来管理数据流.数据流的高速性和无限性以及计算机资源的有限性使得提高数据处理速度成为数据流管理系统（DSMS）的关键;本文主要讨论了DSMS的核心技术———查询优化;着重研究了在shared-nothing机群并行系统中,通过并行查询处理技术来提高数据流处理速度的新方法.     

一类数据流连续查询的降载策略研究

在数据流系统中,输入数据流速增大会产生连续查询过载问题.针对输入数据流存在重要性差别情况,对过载引发的降载问题进行了专门研究.基于数据流和连续查询网络的特点,给出了问题的定义及约束条件,分析了现有的降载方法,提出了关于不等权输入数据流连续查询的降载策略.理论分析和试验结果表明了策略的有效性.     

基于频繁密度分布模式的不确定数据流查询方法

针对当前不确定数据流相似性查询问题中不确定对象建模不准确的问题,提出了一种面向不确定数据流的相似性查询方法 HB-UTS。利用非参数估计方法对不确定数据流中的对象建模,得到不确定对象的密度函数。通过谱聚类方法挖掘密度函数的频繁模式,将挖掘后的模式抽象为语义表示的不确定数据流序列。在相似性查询阶段,通过高阶Markov的状态转移矩阵模型构建不确定数据流的索引结构,它在记录不确定数据流存储地址的同时还记录序列元素的存储概率,可有效提高数据流的分步输入查询效率。本文进行了真实与仿真相结合的方法,通过在随机化处理后的真实数据集上的实验以及与其他相似性查询方法的比较,验证了HB-UTS在处理大规模不确定数据流时较好处理能力以及实施效果。     

数据流上并行查询优化技术

主要讨论了DSMS的核心技术——查询优化;并讨论在高速数据流上的查询优化技术。着重致力于在shared-nothing网络并行环境下,探讨适合流的新型查询处理技术。     

Continuous query scheduler based on operators clustering

Data stream management system (DSMS) provides convenient solutions to the problem of processing continuous queries on data streams.Previous approaches for scheduling these queries and their operators assume that each operator runs in separate thread or all operators combine in one query plan and run in a single thread.Both approaches suffer from severe drawbacks concerning the thread overhead and the stalls due to expensive operators.To overcome these drawbacks,a novel approach called clustered operators sc...     

小型关系数据库管理系统的研究和实现

数据库管理系统主要讨论如何对数据库的信息内容进行创建、存储、访问、处理及维护。该文主要侧重于对关系数据库管理系统的关键技术的研究和实现，集中体现在缓冲区管理、记录管理和索引管理三方面。在此基础上给出关键技术的实现方案，构造并实现了小型关系数据库管理系统R＆ISQL。R＆ISQL实现了数据定义功能和数据操纵功能，支持索引机制用以加快查询速度，同时实现数据完整性约束保证了数据的完整性和一致性。     

Load Shedding Strategy Based on Combined Feed-Forward Plus Feedback Control over Data Streams

In data stream management systems (DSMSs), how to maintain the quality of queries is a difficult problem because both the processing cost and data arrival rates are highly unpredictable. When the system is overloaded, quality degrades significantly and thus load shedding becomes necessary. Unlike processing overloading in the general way which is only by a feedback control (FB) loop to obtain a good and stable performance over data streams, a feedback plus feed-forward control (FFC) strategy is introduced in DSMSs, which have a good quality of service (QoS) in the aspects of miss ratio and processing delay. In this paper, a quality adaptation framework is proposed, in which the control-theory-based techniques are leveraged to adjust the application behavior with the considerations of the current system status. Compared to previous solutions, the FFC strategy achieves a good quality with a waste of fewer resources.     

XML更新流的XQuery查询

针对在XML流上执行XQuery查询处理,精确输出查询结果的问题,给出了一种基于XML更新流的解决方案.在XML流中动态地插入更新事件,得到XML更新流,以达到获取连续精确的结果.XQuery查询语言在XPath路径查询的基础上使用FLWOR表达式实现XML数据流的复杂查询.将主Xpath式进行提取,分出绝对路径和相对路径,把有依赖关系的路径进行合并,重写FLWOR表达式,提高XQuery的查询效率.实验结果表明,提出的方法能够提高执行效率,得到精确的查询结果.     

事件约束的时间不确定事件流查询处理

提出两种事件约束的时间不确定事件流查询处理方法.基于可能世界的查询处理方法,根据事件约束的不确定事件查询语义,通过对可能世界的遍历获取查询结果.基于事件约束优先的查询处理方法中,根据事件约束计算其所涉及事件发生时间的联合分布律,进而获得复合查询所涉及事件的边缘分布律,最后利用时间不确定事件查询处理技术进行后续的查询处理.实验证明了2种方法对时间不确定约束事件查询有效.基于事件约束优先查询处理方法的可能世界集规模更小,比基于可能世界的查询处理方法更高效.     

面向CryptDB的用户身份验证方案

CryptDB是一种典型的云密文数据库,由中间代理充当媒介,允许用户在前端发出明文语义查询请求,后端直接在加密数据上执行数据库操作。针对CryptDB系统代理服务器明文存储密钥未验证用户身份的问题,提出了使用用户口令加密密钥信息的方案,实现了增强密钥管理安全及代理间接验证用户身份的目的。实验结果证明了该方案的安全性和有效性。