基于XML分布式数据库的DBSCAN分片方法研究

摘要：XML分布式数据库可以解决不同数据源的异构问题，各个数据库的数据之间传输问题。在实际应用中，由于数据量大，人们提出了数据分片来减少系统响应时间。然而在查询过程中，不变化的分片方法无法适不断变化和增加的谓词。并且按照现有的分割方法，大型数据库会有大量的谓词或属性，那么分割的片数也将成指数式增长。该文采用一种DBSCAN分割方法来解决这些问题。

关键词：DBSCAN；分布式数据库

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)07-1465-02

Study of DBSCAN Fragmentation Method Based on XML-Based Distributed Database

FANG Ming, LEI Yang

(School of Computer, Xi’an Shiyou University, Xi’an 710065, China)

Abstract: XML-based distributed database can solve problems caused by and architecture and transmission between different data sources. In practice, some offer fragmentation to reduce response time. However, In querying process, unchangeable fragment method can’t adapt to changing and increasing predicates. Moreover, according to traditional fragment method, large scale database may create too many predicates and attributes and the number of fragment will increase rapidly. This article uses DBSCAN fragmentation method to solve problems above.

Key words: DBSCAN; distributed database

1概述

由于XML分布式数据库可有效解决数据源异构问题并且大量半结构化数据以XML形式存储，XML分布式数据库逐渐成为分布式数据库的一个发展方向。对于关系型分布式数据库中有研究采用导出分片，对于XML分布式数据库有研究采用谓词构造初级水平分片方法或基于邻接矩阵初级水平分片方法。对于这些分片方式，虽然起到了加快查询速度的要求，但是在长期的使用过程中，导出分片还是初级垂直分片都没有反馈机制，不能满足不断出现的新谓词的要求，并且对于一些只用过一次的谓词，这些划分方法也会使用这些谓词对数据库进行划分，这对数据库带来不必要的冗余。本文采取并改进的DBSCAN方法本是数据挖掘中的聚类方法。DBSCAN方法可识别噪声，所以对于只用过一次的谓词，这种划分方法可以很好的识别谓词的模式并归类。

2相关定义

定义1简单谓词。给定一个关系R(A1,A2…An)，Aj是定义在域Dj上的属性。定义于关系R上的简单谓词pj即：AiθValue。θ∈{=,, , },Value∈Dj。

定义2核心对象[4]。给定ε，MinPts，若对象p的ε邻域ε(p)包含的对象的个数N MinPts，则称p为核心对象。

定义3簇概率核心对象。给定ε，MinPts，给定DBSCAN算法聚集的簇C。簇概率中心对象p（C）为使其与其他核心对象相比出现次数最多的核心对象。

定义4簇密度可达。点p从簇C密度可达，若至少有一点q∈C，从q直接可达p。

3传统分割方法的问题

对比动态的查询谓词来说，传统分布式数据库主要面对三个问题：谓词过多、分层汇总、谓词更新。

3.1传统分割方法的谓词过多问题

对数据库的分割的目的在于减少对无关数据的搜索与统计。而然分割的过多又使得必须查询多个分片并且汇总起来繁琐。DBSCAN方法对噪声不敏感，可以过滤掉使用极低的谓词。DBSCAN通过检查每个谓词的临域来搜索簇，找到所有的密度可达的谓词，并将可以合并的簇进行合并。未在各个簇内的谓词被标记为噪声。接下来找到各个簇的簇概率核心对象，并使用COM-MIN方法生成小项谓词，根据此谓词对分布式数据库进行分割。注意到谓词之间的维度为1，所以MinPts可以默认为1，只调节临域ε。

3.2传统分割方法的数据分层汇总问题

传统分割方法对分布式数据库的分割属于单一的、一次性分割，并没有考虑到较多的谓词涉及到的数据集需要更深层次的分割，而噪声谓词涉及的数据则不需要再次分割。而DBSCAN分割方法考虑到了这一点，通过设定阀值，当每个簇中的谓词的使用频次占总体谓词使用频次之和的比例大于这个阈值，就可缩小临域并对此簇进行进一步DBSCAN分割，直到小于阈值为止。分割完毕后生成XML文档，内容是分片模式(fragmentation schema)和簇分层树。

3.3传统分割方法的谓词更新问题

传统分割方法没有根据谓词的不断增加和访问频次的增加来对分布式数据库的分割来进行更新。本文提出Re-DBSCAN方法来进行更新。Re-DBSCAN跟踪每个谓词的使用频次和谓词之间是否密度可达来重新分割数据库。

4 DBSCAN分割方法

DBSCAN是基于密度的聚类算法。这种算法可将噪声或低密度区域与稠密对象区域分割开来，并且可以发现任意形状的簇。在本文起到的作用是发现使用者频繁使用的谓词簇，并找出簇中最常用的谓词，然后生成小项谓词对数据库进行分割。

4.1构造谓词使用矩阵

谓词使用矩阵的列是查询语句qi∈W，W为工作量，而行为简单选择谓词。若qi包含对应的谓词pj，则谓词使用矩阵的对应元素PUM(i,j )=1。另外每个查询语句的使用频次存储在向量Freq中。

表1简单谓词使用矩阵

表2查询频率向量

4.2构造谓词邻接矩阵

谓词邻接矩阵Aff是n×n矩阵，Aff（i,j）为谓词pi与谓词pj同时出现在同一查询语句中的次数。另外Aff（i,i）为pi在所有查询语句中出现次数的总和。若谓词pi蕴含谓词pj并且pi不是簇概率核心对象，则去掉pj并把pj把出现的频次加在Aff（i,i）上。

4.3 DBSCAN分割法描述

算法：DBSCAN分割法

输入：邻域ε，谓词邻接矩阵Aff，阈值Thres，谓词集合P。

输出：分片集合。簇分层树T

方法：

1）簇C0=P，簇分层树的根节点T（0）={C0}

Repeat

2）对每个属于C的簇使用DBSCAN方法，找到树的i层T（i）的子簇

3）T（i+1）=每个簇的子簇

4）找出每个子簇的簇概率核心对象pi, Ptempt= Ptempt∪{pi}

5）if子簇Ci谓词的使用频次占该簇中谓词使用频次之和的比例>Thres

then i++

6）减少ε

7）Until C=φ

8）使用COM_MIN方法根据Ptempt谓词集合产生出小项谓词，并放入Ptempt中9）根据P进行分片

5 Re-DBSCAN方法

算法：Re-DBSCAN

输入：邻域ε，簇分层树T，新增谓词使用矩阵ΔPUM，新增谓词集合ΔP，谓词集合P

输出：分片集合。

方法：

1）根据ΔPUM对PUM更新

2）任意pi∈ΔP，

If pi∈P then对pi所在的簇使用DBSCAN分割法。

Repeat

If pi P and T的根节点Cj，从Cj簇密度可达pi

then对Cj∪{pi}使用DBSCAN分割法找到簇概率核心对象q

if pi=q

then找到Cj点的父节点，使用DBSCAN分割法找到簇概率核心对象

Until pi≠q

6结束语

传统数据分布式数据库所遇三个问题：谓词过多问题、数据分层汇总问题、谓词更新问题。这三个问题在XML分布式数据库得到有效的解决，有效的提高了分布式数据库的查询效率。

参考文献：

[1]绍佩英.分布式数据库系统及其应用[M].北京:科学出版社,2005.

[2]胡孔法,董逸生,徐立臻,等.基于OLAP查询的数据仓库视图的水平分割[J].应用科学学报,2003,21(4) :362 - 366.

[3] Inmon W H.数据仓库[M].王志海,译.北京:机械工业出版社,2000.

[4] Han Jiawei.数据挖掘:概念与技术[M]范明,译.北京:机械工业出版社,2007.