在MySQL中广度优先搜索查询？ [英] Breadth first search query in MySQL?

问题描述

我想构建一个mySQL查询，它返回给定节点x深度的图中的所有节点。表格结构是（neighborIDs可以包含多个值）：

<$>

p $ p $ Id名称描述neighborIDs


所以任务基本上是一个宽度 - 在mySQL中首次搜索。我发现在T-SQL中使用的方式，这在mySQL中可能吗？
单个SQL查询比编写一个PHP函数更好，它在节点的每个邻居上运行一个简单的SELECT（所以基本上可以制作大量的简单查询）？

感谢您的帮助

---

试试：

 SELECT root.ID，
 d1.ID，
 d2.ID 
 FROM位置root 
 LEFT JOIN位置d1 ON 
 root .neighborIDs LIKE CONCAT（'％'，d1.id，'％'）
 LEFT JOIN位置d2 ON 
 d1.neighborIDs LIKE CONCAT（'％'，d2.id，'％'）
 WHERE root.id = 1＃我猜这定义了搜索的起始节点。
  

一个示例表是：

  id名称desc neighborIDs 
 1 id1  -  
 2 id2 --- 
 3 id3 neighborours are 1,2 1,2 
 4 id4 neighbor is 3 3 
 10 id10 neigh is 4 4 
  

如果我运行输入id = 1的查询，如果BFS进入1级，它应该返回id = 3的行。

---

另一个尝试：

  SELECT id，neighborIDs 
 FROM locations 
 WHERE id = 3 
 OR 
 neighborIDs LIKE'％3％'
 OR（SELECT neighborIDs FROM locations WHERE id = 3）LIKE CONCAT（'％'，id，'％'）
  

该查询选择id = 3的节点的邻居。

解决方案

第0步：创建一个显示所有邻居对的视图

  CREATE VIEW邻居AS 
（SELECT loc1.id AS a 
，loc2.id AS b 
 FROM位置loc1 
，位置loc2 
 WHERE FIND_IN_SET（loc1.id， loc2.neighbours）> 0 
或FIND_IN_SET（loc2.id，loc1.neighbours）> 0 
）; 
  

步骤1：查找深度1的邻居

  SELECT b AS depth1 
 FROM neighbor 
 WHERE a = 1; <  - 对于ID为1的root用户
  

步骤2：查找深度2的邻居

  SELECT DISTINCT d2.b AS深度2 
 FROM邻居d1 
 JOIN邻居d2 
 ON d1.b = d2.a 
 AND d2.b！= 1 
 WHERE d1.a = 1 < - 对于id为1的root用户
 AND d2.b NOT IN 
（SELECT b AS depth1 < -  depth1 subquery 
 FROM neighbor 
 WHERE a = 1 < -  for root with id = 1 
）
; 
  

第3步：找到深度3的邻居

  SELECT d3.b as depth3 
 FROM neighbor d1 
 JOIN邻居d2 
 ON d1.b = d2.a 
 AND d2.b！= 1 
 AND d2.b NOT IN 
（SELECT b as depth1 
 FROM neighbor 
 WHERE a = 1 
）
 JOIN邻居d3 
 ON d2.b = d3.a 
 AND d3.b！= 1 
 WHERE d1.a = 1 
 AND d3.b NOT IN 
（SELECT b as depth1 
 FROM neighbor 
 WHERE a = 1 
）
 AND d3.b NOT IN 
（SELECT d2.b AS depth2 
 FROM neighbor d1 
 JOIN邻居d2 
 ON d1.b = d2.a 
 AND d2.b！= 1 
 WHERE d1.a = 1 
 AND d2.b NOT IN 
（SELECT b AS depth1 
 FROM neighbor 
 WHERE a = 1 
）
）
; 
  

正如您所看到的，查询行数量的增长是指数的，所以我不会尝试4级。

I want to build a mySQL query, which returns all nodes in a graph in x depth from a given node. The depth will be only 2-4.

The table structure is (neighborIDs can contain multiple values):

Id  Name  Desc  neighborIDs

So the task is basically a Breadth-first search in mySQL. I have found a way to do it in T-SQL, is this possible in mySQL? Is a single SQL query better, than writing a PHP function, that runs a simple SELECT on every neighbour of a node (so basically making tons of simple queries)?

Thanks for help

---

A try:

SELECT  root.ID,
        d1.ID,
        d2.ID
FROM    Locations root
        LEFT JOIN Locations d1 ON
          root.neighborIDs LIKE CONCAT('%',d1.id,'%')
        LEFT JOIN Locations d2 ON
          d1.neighborIDs LIKE CONCAT('%',d2.id,'%')
WHERE root.id = 1  # i guess this defines the starting node for the search..

An example table is:

id   name   desc                   neighborIDs  
1    id1    --     
2    id2    ---        
3    id3    neighborours are 1,2   1,2  
4    id4    neighbour is 3         3
10   id10   neigh is 4             4

If i run the query with the input id=1, it should return the row with id=3 if the BFS goes 1 level deep.

---

Another try:

SELECT id,neighborIDs
FROM locations
WHERE id = 3
OR
neighborIDs LIKE '%3%'
OR (SELECT neighborIDs FROM locations WHERE id = 3) LIKE CONCAT('%',id,'%')

This query selects the neighbors of the node with id = 3.

解决方案

step 0: Create a view that shows all neighbour pairs

CREATE VIEW neighbour AS
( SELECT loc1.id AS a
       , loc2.id AS b
  FROM locations loc1
     , locations loc2
  WHERE FIND_IN_SET(loc1.id, loc2.neighbours)>0
     OR FIND_IN_SET(loc2.id, loc1.neighbours)>0
) ;

step 1: Find neighbours of depth 1

SELECT b AS depth1
FROM neighbour
WHERE a = 1;               <-- for root with id=1

step 2: Find neighbours of depth 2

SELECT DISTINCT d2.b AS depth2
FROM neighbour d1
  JOIN neighbour d2
    ON d1.b = d2.a
      AND d2.b != 1
WHERE d1.a = 1                <-- for root with id=1
  AND d2.b NOT IN
     ( SELECT b AS depth1     <- depth1 subquery
       FROM neighbour
       WHERE a = 1            <-- for root with id=1
      )
;

step 3: Find neighbours of depth 3

SELECT d3.b as depth3
FROM neighbour d1
  JOIN neighbour d2
    ON d1.b = d2.a
    AND d2.b != 1
    AND d2.b NOT IN
       ( SELECT b as depth1
         FROM neighbour
         WHERE a = 1
       )
  JOIN neighbour d3
    ON d2.b = d3.a
    AND d3.b != 1
WHERE d1.a = 1
  AND d3.b NOT IN
     ( SELECT b as depth1
       FROM neighbour
       WHERE a = 1
      )
  AND d3.b NOT IN
     ( SELECT d2.b AS depth2
       FROM neighbour d1
         JOIN neighbour d2
           ON d1.b = d2.a
           AND d2.b != 1
       WHERE d1.a = 1
         AND d2.b NOT IN
            ( SELECT b AS depth1
              FROM neighbour
              WHERE a = 1
            )
     )
;

As you can see, the growth is exponential for the number of query lines, so I won't try the level 4.

这篇关于在MySQL中广度优先搜索查询？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！