多数据类型的数据流查询处理及优化

摘要

数据流作为一种新型的数据模型，在许多应用，如：网络流量管理、金融数据分析、电子商务、交通治理、网站信息的发布和订阅、版权保护以及环境和工业监控中扮演着重要的角色。基于数据流模型的查询处理以及优化技术也得到了广泛的研究。数据流无限、快速的特性和数据流应用系统资源有限、要求快速响应的特点打破了传统查询处理技术的很多假设，需要我们重新研究基础的数据库查询处理技术。
　　 由于数据流是动态的，数据流上的查询通常是连续、大量的。而系统只能处理或者保存与查询相关的数据。因此对查询的特性进行统计分析并设计有效的索引结构来将查询组织起来，是查询优化的关键所在。同时，众多应用所面向的数据类型是多种多样的。而在数据流系统查询处理及优化的研究中，大多面向结构化和半结构化的数据对象。因此，本文针对各种数据类型(结构化数据集中和分布式、多媒体数据以及RDF图数据)上的连续查询问题设计新颖的系统框架和有效的优化算法。同时，本文还对每个所提出的技术及其相关工作进行大量、深入的实验分析，实验结果都充分证明了这些技术的有效性和高效性。本文主要贡献如下：
　　 1.设计了有效且准确的集中式结构化数据k-NN监控方案：有效的处理数据流上连续的k最近邻(k-NN)查询在许多应用领域都是一个重要的问题。通常并非数据流上所有数据都可以存放在内存中。因此，大多数已存在的解决方案仅把有代表性的数据放入索引中，而丢弃一些数据。这些解决方案都是近似的。在本文中，通过对查询而非流数据建立索引结构，将与查询相关的数据存放在Skyline数据结构中以及有效的延迟技术来处理结构化数据准确的k-NN查询。
　　 2.提出一个新颖的基于划分的连接操作模式PMJoin，以优化分布式结构化数据的连接查询计划、减少传输代价：数据流的应用中，数据源通常分散在不同地方。因此，处理多条不同数据源数据流连接操作查询的时候，不可避免的产生巨大的数据传输代价。对于连续的连接查询来说，如果不进行查询优化处理，宝贵的带宽资源会被大量浪费。本文提出一个启发式的算法来合理安排多数据流连续查询计划，使得系统总体传输代价最小化。
　　 3.设计了基于数据流算法的多媒体数据流上拷贝检测查询处理和优化算法：数字视频被越来越广泛的应用在众多的多媒体应用中，并通常以视频流的形式被广播和传送。为了从内容上来进行版权管理，连续监控高速、持续的视频流上的视频拷贝问题得到越来越多的关注。有效的数据流算法是处理大量连续拷贝检测查询所必需的。本章首先定义了在视频被改动后仍然有效的视频序列的相似性。同时采用基于哈希的视频梗概(Sketch)来有效的计算视频序列的相似性。然后，设计了巧妙的位向量签名(Signature)来达到CPU和内存两方面优化的目标。最后，为了同时处理多个连续查询，设计了一个索引结构来组织查询序列。
　　 4.基于图特性的语义网上静态和流式RDF图数据查询处理：有效的RDF查询处理正在成为一个把语义网技术(Semantic Web)应用到真实世界的重要因素。正因为如此，许多研究工作致力于怎样用特殊的模式在关系数据库中进行存储和查询。本文提出一个在三元组方式下存储、索引和查询RDF数据的新颖模式。该模式优化两部分查询处理：对于静态数据的即时查询和对流式RDF数据的连续查询。主要创新点在于把RDF数据的图形特性考虑进来，有助于减少在垂直数据库里面连接操作的代价。在静态查询优化算法的基础上再提出RDF流上连续查询优化策略：(1)根据连续查询的特征，对流进系统的RDF三元组进行分组。(2)每个查询维护相关的记录列表。(3)每个连续查询定期的在相关数据组中进行查询处理，进而提高了查询效率并节省存储空间。
　　 本文通过巧妙的设计查询优化算法和连续查询索引结构，并且将数据流技术和不同数据类型的特点相结合，使得原来无法处理的查询变成可行、原来只能得到近似结果的查询变成准确、原来效率低下的查询效率提高3到4个数量级。这些技术不仅可以在上述具体应用中发挥重要的作用，而且可以扩展应用在更多数据类型上的连续查询中。