Freebase 数据库实践

Freebase是一个知识库,由人提交对现实事物的描述组成这个庞大的知识库。由于Freebase有结构化的性质(不像搜索引擎),可以通过Freebase进行知识推理。详见Wikipedia。类似的有Yago,Cyc等,我感觉还是Freebase最完善。Freebase用的是MQL来进行读写数据库。但是不清楚他们用的什么数据库架构,我觉得肯定不是简单的关系型数据库。

数据库课程的实践任务是通过Freebase的dump data用关系型数据库重新构建,当然没有在线的那么完善的功能。这些数据为24G,解压缩后大概300G。所以可以看出总共的信息量不超过24G。从数据描述也可以看出有很多重复。如下是文件的数据格式。

Topic:

理清建模的思路,必须了解freebase到底是什么。通过google的api wiki和freebase的wiki,我知道其中的节点就是Entity(Topic)。然后根据freebase的主页可以看到目前有46,236,787个Topic。所以地一件事就是找出所有Entity,通过Topic wiki,可以知道每个Topic都有一个GID和MID,GID已经不用了。所以找MID即可,如m.045c7b。这大概有8千万个,但是不是每个mid都是topic,还要满足是common.topic的type,因此去掉不满足条件的剩下4千多万个,符合实际。这也大大降低了难度。有了这些mid后,我觉得不能用字符串来作为数据库的主键,因此根据wikimid,这些mid都是32进制的数,很容易就转换为Int型,索引和空间效率都大大提高。(yt同学直接压缩字符的长度,也是吊,可以通过用户输入的部分MID,预测要输的完整MID)

Description:

有了Topic的MID,就可以以此为中心来开展工作了。首先是看看freebase里的Topic的schema。我感兴趣的是Description,Image(这里只有一个链接,还需要手动通过google取得图片,如google,后来发现Image很少,因此放弃)。通过sed直接过滤即可。

Name:

每个object在freebase里都有name,而且是各种各样的name。我们只关心type.object.name,同样用sed可以完成这个工作。大概90%的Topic都有英文name。要求是要根据输入的来查询相关的topic。这里我们要做的就是fulltext。幸运的是InnoDB,已经支持fulltext (最后解释为什么用InnoDB)。在这里我们做的一个主要优化是把这个表放到SSD上,速度就提高了10倍以上,只能说SSD吊。

Entity Relation:

不管老师的实际要求是什么,我觉得要做就得牛X。老师的几个要求意义不大,不有趣。比如找出跟Entity相关的所有object,完全没有意义,不过就是增大了数据库大小。其他要求也不提了,我就说说我们组的比较吊的一点:找出所有和指定Topic相关的Topic,并给出是什么关系。这个的挑战有两个,一个是得到所有有两个MID的元组后,去掉不是Topic的元组。二是如何表现这个联系。

第一个问题解决方法:全部找出来后,先按第一个topic的mid排序,与所有topic的排好序的mid比较,去掉不是topic的元组。再按第二个topic的mid排序,与所有topic的排好序的mid比较,去掉不是topic的元组。相当于两次sort-merge-join,复杂度为2Nlog(N)+log(M)+2(N+M)。还是能接收的,事实也证明linux的sort命令很吊。

第二个问题解决方法:采用d3.js库。可视化查询,本来想做到,按一下topic,自动平滑的扩展相关的topic,但是还是太弱,没有完成,只能不平滑的进行跳转。如下的效果。

baidu
baidu topic in freebase

Final:

根据要求和一些自己的想法,我们构建的数据库模型如下。为了存储效率,我们牺牲了一点查询效率,很多查询都需要join3个表。另外我们采用InnoDB,不可否认这在批量插入的时候确实比较慢, 比较是行级锁,但InnoDB是未来,必须好好了解其特性,而且InnoDB支持外键,为了完美,果断InnoDB。另外为了适应InnoDB和要求,还得修改一下my.cnf,可以提高缓存和排序效率。

freebase
freebase relation

最后的数据库,共935,874,169条记录,共72.1GB。各表分布如下。在这过程中,走了不少弯路,因此也产生不少中间文件,只能说多亏了linux简单的命令如sort、grep、 sed、awk、 split,在windows真不知道怎么搞,只能自己写c处理。data

 

3 thoughts to “Freebase 数据库实践”

  1. 那个第一个问题是过滤是object的mid么?可以直接暴力用一个bool数组来标记mid是不是object 我4G内存刚好可以开一个2^30的bool数组 再大一位就悲剧了。。这样判断的复杂度只有O(1)

发表评论

电子邮件地址不会被公开。 必填项已用*标注