1

问题描述

我正在一个巨大的图形数据库上实现一个链接分析算法。

图数据库由实体（顶点）和关系（边）构成。

每个实体类型都有属性。例如Person : [age,height,weight]。

每个关系也有属性：例如Call(Phone,Phone) : [date, duration]或 Own(Person, Phone) : [start-date, end-date]。

现在，我得到了具有以下结构的模式：

[实体类型，约束] [关系类型，约束] [实体类型，约束] [关系类型，约束] ... [实体类型，约束]

例如：

[人，年龄>20] [拥有，开始日期>1/1/2010] [电话，以“5”结尾] [通话日期>1/1/2010] [电话，以“6”开头] [拥有由，开始日期<1/2/2011] [人，身高>40]。

我需要为模式中的所有实体和关系找到所有有效的分配。

我可以使用以下原语查询数据库：

  • 查找给定约束集的前 1000 个[entity-type,relationship-type,entity-type]分配。
  • 为上述查找下一个 1000
  • 为给定的一组约束找到第一个[concrete-entity,relationship-type,entity-type]分配。
  • 为上述查找下一个 1000

将给定查询的所有答案都保存在 RAM 中是不可能的。每个实体-关系-实体三元组可能有数百万（数十亿？）的分配。但是，假设整个模式的分配数量很小。

我尝试了什么：

对于链ET1-RT1-ET2-RT2-ET3-RT3 ... 一个简单的实现是：

Get first 1000 (ET1-RT1-ET2)   
for each concrete ET2:
    Get first 1000 (ET2-RT2-ET3)
        for each concrete ET3:
            ...

问题是我可能不止一次地解决相同的子问题。

我正在寻找一种消除这种冗余的算法，这也是内存高效的。

笔记：

我正在寻找一种算法。不适用于诸如“使用 SQL JOIN”/“使用 SPARQL”之类的答案......

4

1 回答 1

0

动态编程在这里应该会有所帮助。

让我们在这里将规则简化为 R1-R2-R3...Rk。

让 next_nodes(node x, Rule R) 返回所有符合规则 R 的链接 x 的节点。如果 R 是实体约束：如果满足条件，则返回相同节点的单例集，否则返回空集。对于关系约束，它返回所有满足条件的链接节点。

Initialize cur_set to all set of nodes.

nextset = {}

For each rule R in Ri:
    for each node x in cur_set:
        nextset = nextset U next_nodes(x)
    cur_set = nextset

您应该能够将集合存储为哈希表或树（任何 log(n) 搜索和更新时间数据结构）。

虽然我省略了保留遍历路径的部分，但应该很容易做到。为集合中的每个元素添加一个名为“路径”的属性，并在每次迭代时附加当前节点。请注意，多条路径可能会导致相同的中间/最终节点。

于 2012-02-02T22:46:22.843 回答