在数据库中存储关于无向图边的数据

Question

我有一个数据结构，它是一个具有节点和边的无向图(可能是稠密的)。节点i和J之间的边缘将具有与其相关联的额外数据，我希望能够在查询时唯一地识别该边缘，并能够快速确定i和j之间是否存在边缘。

我决定使用两张表格来完成这一任务：

Table Nodes
-----------
node_id PK
...
(additional fields)


Table Edges
-----------
nodes_hash(node_id, node_id) PK
edge_thickness
...
(additional fields)

其中，每个边的主键将由一个哈希函数nodes_hash(node_id, node_id)计算，其中包含两个节点ID。

我的问题：

• 我如何想出一个好的哈希函数来计算边ID？
• 我可能忽略了这种方法的主要缺点吗？

Answer 1

没有理由需要将边缘编码为散列:确保没有重复项是一个简单的唯一约束问题。

虽然有计算散列的方法(创建路径枚举字符串，并计算其MD5哈希或类似于这些行的内容)，但是存储哈希没有价值，也没有使用路径枚举方案来存储图形数据本身。路径枚举与文件系统中的工作原理完全一样，存储类似于/a/b/c (如果按节点id枚举)或1.2.1.5 (如果按边缘序号枚举)之类的内容。

对于您的特定用途，我将使用公共邻接列表表设置(除非树中的其他操作调用更专门的数据结构，如节点集或路径/边缘枚举)。在这种结构中，顶层节点具有PARENT_ID = NULL。

CREATE TABLE NODES(
  NODE_ID INT NOT NULL,
  -- OTHER NODE ATTRIBUTES
  PRIMARY KEY (NODE_ID)
);

CREATE TABLE EDGES(
  NODE_ID INT NOT NULL,
  PARENT_ID INT,
  EDGE_WEIGHT INT NOT NULL,
  -- OTHER EDGE ATTRIBUTES
  FOREIGN KEY (NODE_ID) REFERENCES NODES(NODE_ID), 
  FOREIGN KEY (PARENT_ID) REFERENCES NODES(NODE_ID),
  CHECK (PARENT_ID <> NODE_ID),                   -- This avoids simple cycles
  CONSTRAINT UNIQ_EDGE UNIQUE (NODE_ID,PARENT_ID) -- This avoids duplicate edges
);

Answer 2

为什么要使用哈希函数来生成这样的键？

我将为这些节点提供一个整数主键( nodes )。

我将有一个整数主键(edge id)作为边缘。

然后，在每个节点的边缘表中有两个列，外键关系返回到节点表。

我可以很容易地想到使用散列函数的两个缺点。首先，你可能会有碰撞。事实上，如果所有的东西都是以整数的形式存储的，那么你就会因为鸽子洞原理而发生碰撞。

第二，无论如何，您需要存储节点ids。几乎所有我能想到的图问题都需要知道由边连接的节点。

您要处理的无向图是以下约束/触发器：

(1)添加一个node1 < node 2(如果允许自连接，则为<= )的禁忌/触发器。

(2)在node1，node2上添加一个唯一的索引。

(3)添加一个预插入触发器，以确保对于任意值，node1得到较小的值，node2获得更大的值。

在甲骨文中，可以通过在最少(node1，node2)和最大索引(node1，节点)上建立基于函数的索引来组合它们。