传感器数据流复杂查询结果的数据起源跟踪方法

摘要

本发明公开了一种传感器数据流复杂查询结果的数据起源跟踪方法，包括以下步骤：步骤1、确定起源追踪查询滑动窗口大小；步骤2、对起源查询进行规范化描述；步骤3、对起源追踪查询的类别进行判断并设计相应算法；步骤4、设计起源追踪的框架；步骤5、对整个起源追踪算法进行实施，从而实现对传感器数据流复杂查询结果的数据起源的跟踪。突破现有传感器数据管理系统中无法支持复杂查询回溯的技术局限，将数据起源追踪概念首次引入传感器数据流上的复杂查询领域，为新型在线追踪应用提供可行的解决方案。

主权项

1.一种传感器数据流复杂查询结果的数据起源跟踪方法，其特征在于，包括以下步骤：步骤1、通过起源追踪查询滑动窗口大小，其中步骤1确定起源追踪查询滑动窗口大小具体包括以下步骤：步骤11、对起源追踪查询滑动窗口进行定义，起源追踪查询窗口大小为w_i个间隙，W_i＝(t-w_i，t)，设标签i出现在阅读器的有效范围，在窗口W_i期间阅读器在每个间隙以相同的概率p_i读取标签i；步骤12、对起源追踪查询滑动窗口间隙进行读取概率为p_i的相互独立的Bernoulli试验；假设在W_i的所有间隙，标签i只出现在W_i的子集S_i，令表示在这些观测间隙上的平均经验读取率，其中p_i,t根据阅读器的标签列表信息计算得到，其中S_i为二项采样，|S_i|为的二项随机变量；步骤13、选择w_i从而确保以较高概率读到标签i，若在平滑窗口中间隙的个数w_i满足不等式则可以保证在窗口W_i中以大于1-δ的概率读取标签i，式中δ为用户期望的误差概率，从而确定起源追踪查询滑动窗口大小；步骤2、对起源查询进行规范化描述，其中步骤2对起源查询进行规范化描述是在关系数据模型基础上，引入概率化元组，提供不确定性起源信息追踪的标准过程，并为用户提供声明性的连续查询语言接口；步骤3、对起源追踪查询的类别进行判断并设计相应算法，其中步骤3对起源追踪查询的类别进行判断并设计相应算法具体包括以下步骤：步骤31、根据是否已知起源查询对应的正向查询模式，和起源是否为标准关系模式，将起源追踪类型划分为四种类型，若已知正向查询为标准关系SPJ(选择、投影、连接)视图模式，则执行步骤32；若已知正向查询为标准关系ASPJ(聚集、选择、投影、连接)视图模式，则执行步骤33；若已知正向查询为非标准关系ASPJ视图模式，则执行步骤34；若未知正向查询模式且操作为非标准关系ASPJ视图模式，则执行步骤35；步骤32、已知正向查询为标准关系SPJ视图模式起源追踪查询，将所有SPJ视图都转换成SPJ典型形式，使用基于典型形式的追踪查询计算指定元组的起源； 步骤33、已知正向查询为标准关系ASPJ视图模式起源追踪，以中间结果作为聚集元组与基本流之间的纽带，在需要的时候从基本流计算得出中间结果的相关部分，在数据仓库中将整个中间结果存储为物化辅助视图；步骤34、已知正向查询为非标准关系ASPJ视图模式起源追踪查询，将作用在传感器数据流的操作分为分散与合并两类，若每个输入数据项产生0个或多个相互独立的数据项，则视为分解操作，采用枚举输入数据项的方法确定输出项的起源；否则采用合并操作，即将合并操作细分为上下文无关合并和保留键值合并，以渐增的方式验证输入项的子集；步骤35、未知正向查询模式且操作为非标准关系ASPJ视图模式起源追踪查询，采用动态切片技术计算指定元组起源，设计未知操作定义的黑盒起源追踪方法；步骤4、设计起源追踪的框架，其中步骤4设计起源追踪的框架包括以下步骤：步骤41、对起源查询信息模型基本实体进行分类，将其分为数据流和查询，数据流由基本流与导出流两种类型组成：基本流来自系统之外的某一设备、传感器网络、或者一个服务；导出流来自于基本流或其它的导出流；步骤42、设计分布式事件处理系统，该系统以中央服务方式接受查询请求，在多个分布式查询执行引擎上部署查询，并且在各自生命周期时间内执行查询；系统监控各个查询引擎上的负载，根据重用规则、查询和网络代价估计对查询进行优化，将收到的查询分布到有效的查询执行引擎；步骤43、在步骤42的基础上，构建基于数据流模式的传感器数据起源查询框架，该框架包括起源的组织、存储策略、起源与数据的结合方式，以及起源的传播方式；步骤5、对整个起源追踪算法进行实施，从而实现对传感器数据流复杂查询结果的数据起源的跟踪。