基于匹配的异构数据索引方法

梁英飞，童海红，刘 巍(中国航发哈尔滨东安发动机有限公司 信息档案中心，哈尔滨 150066)

20世纪以来，信息化数据以指数规模增长，这使得人们从纷乱复杂的异构数据中迅速有效地得到自己关注的信息变得困难重重，而索引是信息获取过程中最重要的一步。目前，结构化数据和非结构化数据的索引研究已取得重大成果，但单一类型的数据索引已无法满足用户需求，所以研究支持多种类型的数据索引已迫在眉睫[1,14]。

当前形势下的数据环境异常复杂，数据量日益增大。目前，异构数据类型主要包含两种：一种是以关系型数据库为代表的结构化数据；另一种是以文本文档、HTML网页、Email等为代表的非结构化数据。结构化数据的主要查询方式为SQL，非结构化数据的主要检索方式为关键词搜索。随着数据信息化的快速推进，能同时检索多种数据类型的索引已引起人们关注。异构数据索引不同于单一类型的数据索引，它能够支持各种类型的数据检索[1,6-7]。

部分匹配(Partial Match)：针对一个由d维向量空间{0,1}d中n个点组成的数据集，给定一个查询x，x包含在d维向量空间{0,1,*}d中，数据集中的点y满足对任意的i,xi≠*有xi=yi，则x与y部分匹配[1,13]。

已有文献已经证明部分匹配问题和子集合查询问题表面上虽然不同，但本质上是等价的。子集合问题定义：给定一个集合U，S是U中n个子集的集合，|U|=m，对一给定的查询集合Q⊆U，若存在P(P∈S)，满足Q⊆P，则Q是P的子集[15-16]。

部分匹配和子集合都是数学领域中研究比较广泛的问题，这两个问题在本质上等价，研究点也有很多重合部分。部分匹配问题是很多领域的最基本、最重要的应用问题，如在信息检索领域搜索包含指定关键词集合的文档，像Google，Baidu等，在数据库领域搜索满足等式约束(如“Age=25 and City=Shanghai”)的记录，在IP数据包分类领域中部分匹配也应用广泛。

在信息检索领域按照匹配程度，数据查询的种类主要包括两种：精确匹配查询(Exact Match Query)和部分匹配查询(Partial Match Query)[2]。直观的描述如下：定义一个文档，由一组关键词k1,k2,…,kn构成，(1)精确匹配查询：表示F的所有关键词必须全部匹配才能命中，即查询必须指定文档中所有存在的关键词，例如k1∧k2∧…∧kk；(2)部分匹配查询：只要存在表示F关键词匹配就可命中，即查询中包含一部分指定文档的关键词即可，例如ki∧kj。从目前的信息获取方式来看，用户发布的查询不可能每次都能全部命中数据对象的全部关键词，用户需要更加灵活地发布自己的查询，从这方面看部分匹配更适合异构数据索引的要求[8-12]。

1 部分匹配索引

1.1 部分匹配索引体系结构

本文构建异构数据索引主要分以下几个步骤：首先解决异构性问题，对给定的异构数据源统一数据模型，将来自各个不同数据源的数据统一用本文提出的数据模型表示，形成新的数据集；然后构建索引，针对数据模型中的关键词进行预处理，得到关键词在数据集U中的查询计数，将关键词依照查询计数排序；而后在逐级构建索引时，依然以关键词计数为基础，按照指定的剪枝条件有选择地构建特定数据条目的索引。为了加速索引的构建过程，本文在构建索引时利用了Trie树结构来加速查询的匹配速度，最终按照L1,L2,…Lk的顺序构建部分匹配索引。图1展示了部分匹配索引的体系结构。

图1 部分匹配索引体系结构图

1.2 数据模型

为保证来自不同数据源的各种各样的异构数据能映射到该模型上，本文在研究多个模型的基础之上提出一个较好的数据模型。该模型由三部分组成，可描述为