近似查询处理(数据库)

时间：2022-12-29 18:30:01 | 来源：信息时代

时间：2022-12-29 18:30:01 来源：信息时代

    近似查询处理 : 允许查询结果具有一定误差的查询处理技术。查询所获得的结果不要求是精确结果,而是在一定的误差允许范围内的结果。传感器节点的物理特点导致节点感知的数据多具有一定的误差值,在很多情况下,人们并不需要知道节点的精确数据,而只需要通过一些近似查询处理技术就可以完成查询。
近似查询处理主要利用感知数据间的关联性,通过上传给基站的部分数据推测整体数据的情况,从而缩减传递的数据量,减少能量的消耗。无线传感器网络中的主要的近似查询处理涉及到: 通过邻居节点或节点的历史数据来近似估计实际情况,以及利用一些统计学技术来估算查询结果。基于模型分析、基于概要技术和数据卸载等方法是常用的近似查询处理方法。
1.基于模型分析的近似查询处理方法
传感器网络收集的感知数据只表示在采样点上的一些离散信息。模型认为所有传感器节点感知的不同类型的数据之间都存在一定的关系。给定一个模型,某个节点产生的某种类型的数据可以用来估计出其他节点产生的其他类型的数据。例如,一个节点的温度采样很有可能会提高对附近节点的感知的湿度数据的估计的可信度。另外,从通信代价的角度来讲,接收近距离节点的数据要比接收远距离节点的数据节省能量。
模型可以用来对传感器读数进行更好地分析,帮助解决采样值在空间上的不均衡问题,帮助确认提供错误信息的节点,并且推断出坏死节点或即将坏死节点的采样数据。另外,模型提供了一个框架,可以优化传感器的数据接收——只有在当前模型不能够推断出一个符合精度的数据时,才允许传感器采集数据。常用的模型包括概率模型和线性模型。
查询处理引擎使用概率模型(probabilistic model)来回答关于传感器网络当前状态的查询。使用一个概率密度函数p(X₁,X₂,X₃,…,X_n)来表示这个模型,X_i是某个传感器上的某个属性(例如,5号节点上的温度)。通常每个传感器的某种类型只能对应一个属性。
用户提出感知查询后,这些查询被翻译成基于模型的概率运算。错误容忍度(error tolerance)和目标可信度(target confidence)表明了用户对于近似性的要求。如果用模型估计出的概率满足或超出用户定义的可信度,概率模型可以直接给出估计出的数值。如果概率模型的可信度比较低,概率模型就需要在回答查询之前从传感器网络中获得可以帮助提高精度的采样值。选择哪些节点的采样值是一个优化的问题,通过优化可以选择最好的一组属性来观察,尽量在满足用户提出的可信度的同时将这个过程耗费的能量代价减小到最少。
线性模型假设节点与邻居节点间具有一定程度的感知数据空间关联性,即线性相关性。线性模型可以被应用于“区域快照查询”中。这种查询以尽量缩小查询访问节点个数为目的。区域快照是由一组被选定的代表节点和一个阈值T构成的。通过这些代表节点的地理位置以及节点采样值可以得到网络中数值分布的梗概。线性模型需要不断地学习来提高准确度,学习的过程是: 在节点的缓存中不断读取新的有价值的数据,来确保节点感知的数据始终能与一个代表节点感知的数据相似。节点需要周期性的检测代表节点是否称职,如果发现代表节点能量不足或者坏死,节点会重新发出邀请,重新选择代表节点。
线性模型假设地理位置相邻的节点产生的数据满足线性关系,如室内声音监控应用。但在很多应用中,空间上相邻的节点产生的数据通常并不十分满足线性关系,而很可能是随机数据或者是满足一定概率相关性的数据。
2.基于概要技术的近似查询处理方法
概要技术(sketch)的核心思想是利用哈希函数把数据从一个取值范围映射到另一个占用较小内存空间的取值范围,生成概要数据结构。Flajolet和Martin提出了支持计数查询的概要技术(counting sketch),用来快速地求解数据集中不同元素的个数,简称为FM概要(FM sketch)技术。
FM概要技术被应用到无线传感器网络的感知查询处理中。经过一次遍历并只用一小块空间就能快速估计感知数据流中不同元素的个数,在节省能量的同时也尽可能地提高了查询精度。使用FM概要技术进行网内聚集对于无线传感器网络具有很强的适应性。传感器网络的无线传播特性使一个节点同时向很多邻居节点进行广播成为可能。其次,sketch技术对复制不敏感,允许一个传感器节点把所有传给它的网络数据合并到一个将要发送的数据包中。选择合适的同步策略,就可以非常方便地聚集数据而每个节点只需进行一次广播。
3.利用数据卸载技术的近似查询处理方法
数据卸载在无线传感器网络的数据管理中被广泛使用,在此主要介绍数据卸载在近似连接查询中的应用。在无线传感器网络中执行多连接查询时,需要耗费巨大能量在节点之间进行大量的数据传输。在一个小型的由电池驱动的无线传感器网络中,每个节点都受能量和存储容量的限制,而在网络之外存在一个连接节点,它的能量、内存和CPU都不受限制。网络的任务是监测环境数据,并利用感知到的数据进行连接。为了计算一个给定时间段内的感知数据的连接结果,连接节点需要向网络中的节点发出查询,接着,数据节点将自己的数据发送到连接节点进行连接。为节省能量开销,每个数据节点传送尽量少的数据到连接节点。在每次传送数据之前,数据节点先将本地感知数据的概要信息传送给连接节点。连接节点利用这些概要信息来决定从不同的节点索取实际的数据。连接节点只会向每个节点索取它所感知的数据中的一部分,产生的连接结果是传送全部数据时的连接结果集的子集。这一问题称为传感网络中的近似连接问题。在进行近似连接时,希望连接节点向不同的数据节点索取的数据能够满足最大连接结果子集(MAX-subset)要求,即被传送给连接节点的数据可以产生最大的连接结果集。