Односторонние соединения и "n степеней разделения" в MySQL?

Question

У меня есть таблица сущностей с целочисленными идентификаторами, назовем ее Entities. В другой таблице у меня есть односторонние отношения между этими объектами, для которых есть столбец «От», «Кому» и какие у них отношения (давайте назовем эту таблицу Отношения). Сущности могут быть «двухсторонними», если у них есть два соответствующих односторонних отношения, и в целом это граф или сеть.

Я хочу написать процедуру, в которой я могу передать ему идентификатор сущности и узнать, сколько степеней разделения нужно пройти, и он возвращает каждый идентификатор сущности в пределах такого количества отношений переданного идентификатора. Я понятия не имею, как написать эту рутину. Итеративная природа этого выходит за рамки моего опыта с хранимыми процедурами. Любые подсказки, как начать это?

Answer 1

Для табличных отношений со столбцами from_id и to_id

DROP PROCEDURE IF EXISTS find_relationships;
DELIMITER $$

CREATE PROCEDURE find_relationships( start_id int(11), level int(11) )
BEGIN
  DECLARE found INT(11) DEFAULT 1;
  DROP TABLE IF EXISTS related_entities;
  CREATE TABLE related_entities (id int(11) PRIMARY KEY) ENGINE=HEAP;
  INSERT INTO related_entities VALUES ( start_id );
  WHILE found > 0 AND level > 0 DO
    INSERT IGNORE INTO related_entities
      SELECT DISTINCT from_id FROM relationships r
      JOIN related_entities rf ON r.to_id = rf.id 
      UNION 
      SELECT DISTINCT to_id FROM relationships r
      JOIN related_entities rf ON r.from_id = rf.id;
    SET found = ROW_COUNT();
    SET level = level - 1;
  END WHILE;
  SELECT * FROM related_entities;
  DROP TABLE related_entities;
END;
$$
DELIMITER ;

Должен работать для любого графа, находя все связанные узлы на расстоянии, заданном как уровень.

call find_relationships( 5, 2 );

Answer 2

В MySQL нет операторов with, поэтому вам понадобится временная таблица.Псевдокод:

drop table if exists tmp_nodes;

create temporary table tmp_nodes as
select :id as id;

while :depth++ < :max_depth
  insert into tmp_nodes
  select links.id
  from links
  join tmp_nodes as nodes on nodes.id = links.parent_id
  left join tmp_nodes as cycle on cycle.id = links.id
  where cycle.id is null;

select id from tmp_nodes optionally where id <> :id;

---

Похоже, piotrm написал для вас нужную функцию.