集体索引在单输入渐进式查询中的应用

摘要：随着数据库的日益庞大，要使用户能在大量数据中进行更快速的查询，需要更高效的查询技术。本文中所研究的新的查询类型，称为渐进式查询（progressive queries，简称PQ），由一组相互关联的，并逐步计算的步查询组成。

关键词：渐进式查询；步查询；集体索引

中图分类号：TP311 文献标识码：A文章编号：1007-9599 (2011) 10-0000-02

Mass Index Application in the Single Input Progressive Queries

He Zhiquan

(Shanghai University of Electric Power of Computer and Information Engineering,Shanghai200090,China)

Abstract:With the increasingly large databases,more efficient database techniques for faster user queries on massive data are required.In this paper,we study a new type of query,called progressive queries.A progressive query is defined as a set of interrelated and incrementally formulated step-queries.

Keywords:Progressive inquiry;Step inquiry;Mass index

现在的数据库存储量很大，所以需要更先进的技术来查询和处理数据。本文研究的新的查询类型称为渐进查询，由一组步查询构成。

一、引言

与以往不同，即将探讨的这种查询含有多个步骤（逐步）。我们把含有多个步骤渐进的查询，定义为渐进式查询，每一步称为步查询（step-query）。据此，提出一个能使渐进式查询处理更加高效的新的集体索引技术，关键思想是采用一个特殊的索引结构，把在其成员索引的集合上输入步查询更有效的转化为对结果关系的索引，便于接下来的步查询使用。

本文的结构如下：第2节引入了一种查询模型来描述单输入线性PQ。第3节讲解集体索引技术在单输入渐进式查询上的应用。第4节总结并讨论未来的研究方向。

二、渐进式查询模型

一个渐进式查询（PQ）由若干个步查询（SQ）构成。用户在一个或多个外部关系上提交一个步查询SQ1，把SQ1的执行结果作为输入，提交第二个步查询SQ2。SQ2也可以用外部关系作为输入，依此类推。重复此过程，直到最后一步查询提交。用户根据需要决定如何进行下一步，当对搜索结果不满意时也可随时停止。

举个例子，考虑一个渐进式查询PQ的三个步查询，定义如下：

1.SQ1：R1′=σcond1（R1）.

2.SQ2：R2′=πx，y（σcond2（R1′⋈cond3R2））.

3.SQ3：R3′=πx，z（R2′⋈cond4R3）

用户首先提交SQ1，然后基于SQ1的结果R1'提交SQ2，最后，基于SQ2的结果R2'提交SQ3。其中，R1、R2和R3是外部关系。

（一）单输入线性渐进式查询的结构

我们根据查询结构和步查询的输入定义了单输入线性（single-input linear）渐进式查询。如图1所示，其中实线和虚线是指外部和内部关系。

图1.单输入线性

单输入线性PQ有两个特性：查询结构是线性的；每个非初始的步查询来源单一。其定义如下：

1.∀i：（SQjSQi）and（SQkSqi）⇒j=k；and

2.ifSQi∈Initial（PQ）：|E-Domain（SQi）|=1；and

3.∀SQi∉Initial（PQ）：E-Domain（SQi）=∅.

（二）目前渐进式查询的方法

假设一个PQ是基于一个或多个大型外部关系来执行，目前较合理的方法是根据索引动态地估计。注意到上一步查询的结果能更高效的转化为下一步查询的输入，所以这一技术能够在一系列的步查询中保持高效。在接下来的两节中，我们将根据目前的这种技术，提出一种新的索引结构，即集体索引。

三、集体索引在单输入线性渐进式查询中的应用

首先提出单输入线性渐进式查询技术（包括索引结构及搜索算法）。例如，一个关系R的集体索引由在R上的成员索引的集合组成，结构较为特殊，其中每个成员索引都是一个传统的B+树。下面分析如何用集体索引进行高效查询，假设一个集体索引服务于单输入线性PQ的外部关系R的输入。简单起见，在下面的讨论中，我们假设一个成员索引为PQ的一个步查询。PQ在第i（i≥1）步的步查询SQi的搜索和索引保持算法如下：

算法：通过集体索引进行步查询处理

Input：（1）当前查询识别器Current Qid；（2）当前步数i（≥1）；（3）步查询SQi；（4）SQi的输入关系R′i−1；（5）R′i−1的集体索引CI′i−1.

Output：（a）SQi的结果关系R′i；（b）R′i转化后的集体索引CIi′.

Method：

（1）Initialize result relation R′ito empty；

（2）Identify a member index I in CI′i−1that can be used for processing SQi；

（3）if E is not empty do

（4）for each leaf node entry le in E do

（5）fetch corresponding router entry re located by φ（le.Tid）；

（6）if i=1 or（re.QueryID=Current Qid and e.StepNo=I − 1）then

（7）if i=1 then

（8）Fetch the tuple t located by le.Tid from R′i−1；

（9）Let re.QueryID=CurrentQid；

（10）else

（11）Fetch the tuple t located by re.TempTid from R′i−1；

（12）end if

（13）Put t into R′i；

（14）Let re.TempTid be the new Tid of t in Ri′；

（15）Let re.StepNo=i；

（16）Update the router with modified entry re；

（17）end if

（18）end for

（19）Let CIi′be CIi−1′with the revised router entries；

（20）else

（21）Let CIi′be an empty collective index；

（22）end if

（23）return Ri′and CIi′.

四、结论与展望

用户在庞大数据中的查询的情况越来越多，如何进行高效快速查询亟待解决。本文已经研究了庞大数据查询的新类型，即渐进式查询。主要研究贡献如下：

1.引入了一个查询模型，描述了单输入PQ的线性结构和步查询的输入需求；

2.提出了一个新的索引结构，即集体索引，能有效地逐步查询。集体索引技术通过动态调整逐步查询。

之后的工作重点包括解决集体索引在其他类型的PQ中的应用，并将此项技术应用到庞大的数据库管理系统实体中。

参考文献：

[1]Halevy,A.Y.(2001)Answering queries using views:a survey.VLDBJ.,10,270-294

[2]Franklin,M.,Halevy,A.and Maier,D.(2005)From databases to dataspaces:a new abstraction for information management.SIGMOD Rec.,34,27-33

[3]Comer,D.(1979)The ubiquitous B-tree.ACM Comput.Surv.,11,121-137