摘要:
1.本文的创新点:本文采用社团划分的方法对大规模数据库进行模式抽象.模式抽象的目的是将大规模的数据库模式抽象成为一个多层次的可浏览的模式摘要.在模式摘要中,每一个层次都是对上一层次的展开,用户可以根据需求逐步地对数据库模式进行展开浏览,从而能快速了解数据库的内容,简化数据库查询的过程.本文将数据库模式抽象问题明确地分为三个步骤:首先,将数据库依据主题划分为主题组,每一个主题组都是关于某个特定的主题的表的集合.其次以主题组为基本单位,依据主题组之间的相似度进行聚类以产生更高层次的模式摘要.最后,通过衡量表的重要度,给每个主题组和结果类加上标签,以方便用户了解每个主题组和结果类的内容.2.实现方法:将数据库的模式用模式图来表示,其中节点代表数据库中的表,边代表与表之间的参照(引用)关系.为了降低大规模数据库模式的稀疏度,我们利用面向对象数据库中的继承关系,将继承关系作为节点之间的一种边添加到数据库模式图中.同时为了区别数据库模式图中表之间的参照关系边和继承关系边,我们为这两种边设置了不同的权重.我们将参照关系边的权重设置为1,继承关系边的权重设置为使模式图在进行社团划分后结果的modularity最大的值.基于“相同主题的表之间大部分都是紧密联系的,而不同主题的表之间大都是联系很少或者根本没有联系”的特性,本文采用了基于最大化modularity的社团划分方法来将数据库划分为主题组.本文采用了贪婪算法,将模式图初始化为任意两点之间都不存在边;在每次迭代的过程中选择一条边,通过添加这条边,能使整个模式图的modularity增加的值最大,然后将此边添加到模式图中;不断重复添加边的过程,直到整个模式图的modularity达到最大.对任意两个主题组,本文通过衡量两个主题组之间数据的交叉程度,以及两个主题组数据分布是否相似来衡量两个主题组之间的相似度.在计算出任意两个主题组之间的相似度后,本文使用层次聚类算法对主题组进行聚类,聚类的结果我们称之为抽象类.有了主题组和抽象类之后,我们计算数据库模式中每个表的重要程度,用每个主题组中最重要的表的名称作为整个主题组的标签;再利用抽象类中的主题组之间具有继承关系,将抽象类中的基类主题组标签或者基类主题组集合对应的标签作为抽象类的标签.我们的模式抽象方法将产生三层模式抽象:第一层的元素为抽象类,是多个主题组的集合,第二层的元素为主题组,是具有相同主题的表的集合,第三层的元素为表.3.结论及未来待解决的问题:本文中提出的基于社团划分的数据库模式抽象算法优于现有数据库模式抽象算法;能够非常有效地为大规模数据库产生高质量多层次的模式摘要.利用此模式摘要,用户可以快速地找到其所关注的主题和表,缩减用户熟悉和浏览数据库的时间,方便用户构造查询和查找表之间的联系.我们未来将探索是否能够根据用户的查询需求来定制数据库的模式抽象;以及使用其他的社团划分方法来解决大规模数据库模式抽象中出现的挑战.4.实用价值或应用前景:大规模数据库的模式中通常包含数以千计的表,数量巨大的表和表与表之间的复杂联系成为用户了解和使用数据库的巨大障碍.用户通常需要花费大量的时间和精力来理解数据库的模式,以便构造合适的查询来访问数据库.本文中提出的基于社团划分的数据库模式抽象算法能够为大规模多主题数据库产生一个多层次的数据库模式摘要,使用此摘要,用户可以快速地了解数据库中的主题,每个主题包含哪些表,以及这些表之间的关系.可以有效地减少用户浏览数据库的时间,极大地提高数据库的易用性.