链接分析模式搜索

Question

问题描述

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

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

每个实体类型都有属性。例如人：[年龄、身高、体重]。

每个关系也都有属性：例如Call(Phone,Phone) : [日期, 持续时间] 或 Own(Person, Phone) : [start-date, end-date]。

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

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

例如：

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

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

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

• 查找给定一组约束的前 1000 个[实体类型、关系类型、实体类型] 分配。
• 为上述
• 查找给定约束集的第一个[具体实体，关系类型，实体类型]分配找到下一个1000。
• 找到上述的下 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”之类的答案...

Answer 1

动态规划在这里应该会有帮助。

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

让 next_nodes(node x, Rule R) 返回链接 x 且符合规则 R 的所有节点。如果 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) 搜索和更新时间数据结构）。

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