Вычисление транзитивного отношения

[alexhemp]

Вычисление транзитивного отношения

Задача весьма теоретическая, но для меня имеющая практическое воплощение - расширение условий поиска.

Итак, существует таблица

X CHAR(30), Y CHAR(30)

В ней записано множество значений

например

A1 B1
B1 C1
A1 B2
....


т.е. по сути задана таблица синонимов
Но, она не полна, ибо существует транзитивность отношения

Требуется написать запрос который бы по заданному значению возвращал список всех синонимов, т.е. разрешал отношения, а именно делал вывод

Если A1 = B1 и B1 = C1 то A1 = C1

Пока в голову приходит поиграть в направлении

SELECT X, Y FROM table UNION DISTINCT SELECT Y, X FROM table

Потом нужно как-то самообъединить результат чтобы найти цепочки длиной два, и продолжать итерации пока не будут найдены все цепочки...

Вычисления могут быть долгими, но прямой перебор писать на php не хочется совсем...

 

[hermit_refined]

как известно, такое отношение разбивает множество на классы эквивалентности.
и удобнее для последующих выборок будет его хранить в виде element <--> equivalenceClassId.

а переконвертировать можно силами php, да.

 

[alexhemp]

да, думал над классами эквивалентности, возможно стоит сразу при добавлении в базу приписывать элемент к какому-либо классу.

Но поиск эквивалентных элементов нужно регулярно повторять, ибо возможен сценарий

Сперва добавили
A1 B1

Потом
С1 D1

А потом
B1 C1

В итоге на основе записи B1 = C1 следует объединить два класса...

 

[hermit_refined]

ой, ну при добавлении новой пары X, Y смотрим их в таблице (element <--> equivalenceClassId).
если принадлежат одному классу - ничего не делаем.
если разным - апдейтом объединяем классы.
если есть только один - присоединяем.
если ни одного - создаем новый класс.

 

[alexhemp]

а блин, торможу уже, ведь все можно сделать при добавлении и у нас не более двух классов ведь элементов то два...

ушел писать код