图数据建模与查询：从基础到高级应用

### 图数据建模与查询：从基础到高级应用 #### 1. 节点建模与边约束 在数据建模中，对于未连接的节点，部分数据架构师倾向于使用可空的 Y 列，而非让两列都指向同一节点。虽然最终效果相同，但使用可空 Y 列会使某些查询变得复杂，因为需要处理 NULL 值的情况。 ##### 1.1 边的约束 Edges 表可用于表示任何图，但当前结构未隐含语义，难以判断每条边是有向还是无向。例如： ```sql INSERT INTO Edges VALUES (1, 2); INSERT INTO Edges VALUES (2, 1); ``` 这两行可能在逻辑上相同，也可能不同。若图中的边是有向的，插入两条边表示双向连接；若为无向边，则需添加约束以避免插入逻辑上相同的路径。 - **使用触发器** 首先清空 Edges 表： ```sql TRUNCATE TABLE Edges; GO ``` 然后创建触发器： ```sql CREATE TRIGGER CheckForDuplicates ON Edges FOR INSERT, UPDATE AS BEGIN IF EXISTS ( SELECT * FROM Edges e WHERE EXISTS ( SELECT * FROM inserted i WHERE i.X = e.Y AND i.Y = e.X ) ) BEGIN ROLLBACK; END END; GO ``` 再次插入之前的两行数据时，触发器会回滚第二个插入操作，防止重复边的创建。 - **使用索引视图** 创建一个包含 1 到 8000 的数字表： ```sql SELECT TOP (8000) IDENTITY(int, 1, 1) AS Number INTO Numbers FROM master..spt_values a CROSS JOIN master..spt_values b; ALTER TABLE Numbers ADD PRIMARY KEY (Number); GO ``` 创建索引视图： ```sql CREATE VIEW DuplicateEdges WITH SCHEMABINDING AS SELECT CASE n.Number WHEN 1 THEN e.X ELSE e.Y END X, CASE n.Number WHEN 1 THEN e.Y ELSE e.X END Y FROM Edges e CROSS JOIN Numbers n WHERE n.Number BETWEEN 1 AND 2; GO CREATE UNIQUE CLUSTERED INDEX IX_NoDuplicates ON DuplicateEdges (X,Y); GO ``` 索引视图逻辑上包含插入的路径及其反向路径，唯一索引可约束重复路径。两种方法性能相近，但索引视图更具优势，还可用于快速查找所有有向路径。 #### 2. 基本图查询：查找连接节点 在遍历图之前，需了解有向边和无向边的区别及建模方式。以下节点对可表示边，无论 Edges 表是否为有向： ```sql INSERT INTO Edges VALUES (2, 1), (1, 3); GO ``` ##### 2.1 有向图查询 从特定节点出发，若存在从节点 X 到节点 Y 的边，则节点 Y 可从节点 X 访问。查询从节点 1 出发可访问的节点： ```sql SELECT Y FROM Edges e WHERE X = 1; ``` ##### 2.2 无向图查询 无向图中，边可双向遍历。查询从节点 1 出发可访问的节点： ```sql SELECT CASE WHEN X = 1 THEN Y ELSE X END FROM Edges e WHERE X = 1 OR Y = 1; ``` 该查询复杂度增加，且在处理大数据集时性能不佳。可通过创建多个索引并使用 UNION ALL 查询来改善： ```sql SELECT Y FROM Edges e WHERE X = 1 UNION ALL SELECT X FROM Edges e WHERE Y = 1; ``` 但此方法仍不如有向图查询性能好，因此建议通常将图建模为有向图。 #### 3. 图的遍历 要了解底层数据结构，需对图进行遍历。以下通过街道地图示例说明。 ##### 3.1 数据准备 创建相关表： - **Streets 表**：存储街道信息 ```sql CREATE TABLE Streets ( StreetId int NOT NULL PRIMARY KEY, StreetName varchar(75) ); GO INSERT INTO Streets VALUES (1, '1st Ave'), (2, '2nd Ave'), (3, '3rd Ave'), (4, '4th Ave'), (5, 'Madison'); GO ``` - **Intersections 表**：存储交叉路口信息 ```sql CREATE TABLE Intersections ( IntersectionId int NOT NULL PRIMARY KEY, IntersectionName varchar(10) ); GO INSERT INTO Intersections VALUES (1, 'A'), (2, 'B'), (3, 'C'), (4, 'D'); GO ``` - **IntersectionStreets 表**：映射街道和交叉路口 ```sql CREATE TABLE IntersectionStreets ( IntersectionId int ```