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

我有一个数据结构是一个无向图（可能密集）与节点和边缘。 节点I和J之间的边缘将具有与其相关的附加数据，并且我希望能够在查询时唯一地识别该边缘，并且能够快速确定I和J之间的边缘是否存在。

我决定用两张表完成这个工作：

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


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

其中每个边的主键将由具有两个节点ID的散列函数nodes_hash(node_id, node_id)计算。

我的问题：

我如何提出一个好的散列函数来计算边缘ID？

我可能会忽略这种方法的任何主要缺点？

---

没有理由为什么你需要将边缘编码为散列：确保没有重复是一个简单的约束条件。

尽管有计算散列的方法（创建路径枚举字符串，并计算其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
);

---

为什么要使用散列函数来生成这样的密钥？

我将有一个整数主键（节点ID）的节点。

我将有一个整数主键（边缘ID）的边缘。

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

我很容易想到使用散列函数的两个缺点。 首先，你可以碰撞。 事实上，如果所有东西都以整数存储，那么只会出现鸽子洞原理的碰撞。

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

你会处理一个无向图是下面的约束/触发器：

（1）添加一个约束/触发器，使节点1 <节点2（或<=如果允许自连接）。

（2）在node1，node2上添加唯一索引。

（3）添加before-insert触发器以确保对于任意值，node1获取较小值，并且node2获取较大值。

在Oracle中，可以通过至少具有基于功能的索引（node1，node2）和最大（node1，node）来组合这些索引。

链接地址: http://www.djcxy.com/p/52375.html

上一篇: Storing data about undirected graph edges in a database

下一篇: Efficient representation of edges in a C++ graph structure