Круговой матч

Question

У меня есть база данных с тремя таблицами: userid_tbl, need_tbl, have_tbl

create table userid_tbl
(user_id varchar2(15) not null primary key);

create table need_tbl
(user_id varchar2(15) not null,
have_item varchar2(100) not null,
foreign key (user_id) references userid_tbl (user_id)
);

create table have_tbl
(user_id varchar2(15) not null,
have_item varchar2(100) not null,
foreign key (user_id) references userid_tbl (user_id)
);

Каждый пользователь может создавать неограниченное количество записей о потребностях или услугах, которые они могут предоставлять другим в базе данных. Предметы из заранее определенного списка.

После объединения таблицы потребностей и потребностей я сопоставил потребности и потребности и отбросил запросы, которые не могут быть выполнены любым пользователем, в представлении, которое выглядит следующим образом:

Item:         Need:            Have:
1             Bob              George
2             George           Herbie
3             Herbie           Bob
4             Larry            Wally
5             Wally            Larry
6             John             George

Сейчас я пытаюсь написать запрос, в котором я могу рассчитать количество перестановок каждого пользователя, удовлетворяющего свои запрошенные потребности. Например, в приведенном выше примере Боб, Джордж и Херби могут вместе удовлетворить потребности друг друга, как это могут Ларри и Уолли, но Джон не может, поэтому общее количество будет равно 2.

Я впервые начал делать это с помощью LOOP, но должен быть более простой и менее ресурсоемкий способ сделать это с помощью одного запроса.

Answer 1

Смотрите подробные объяснения в статье в моем блоге:

• Нахождение петель в дереве

Если ваших пользователей можно найти более одного раза в столбце needs таблицы, это сложная задача NP.

Если нет, введите следующий запрос:

SELECT  COUNT(*)
FROM    v_needs
CONNECT BY NOCYCLE
        need = PRIOR have
WHERE   CONNECT_BY_ISCYCLE = 1

CONNECT BY NOCYCLE разрешает циклы в иерархических запросах (NOCYCLE просто останавливает ветвление, когда находит циклы, нет NOCYCLE возвращает ошибку).

CONNECT_BY_ISCYCLE возвращает истину всякий раз, когда находит цикл (для записи возвращается 1, которая выдаст корень текущей ветви на следующей итерации).

Обратите внимание, что этот запрос выдаст вам всех пользователей в циклах без их группировки.

Чтобы сгруппировать пользователей, выполните этот запрос:

SELECT  n.*, CONNECT_BY_ROOT(have), level
FROM    v_needs n
START WITH
        have IN
        (
        SELECT  MIN(have)
        FROM    (
                SELECT  have, CONNECT_BY_ROOT(have) AS root
                FROM    t_needs
                START WITH
                        have IN
                        (
                        SELECT  have
                        FROM    t_needs n
                        WHERE   CONNECT_BY_ISCYCLE = 1
                        CONNECT BY NOCYCLE
                                needs = PRIOR have
                        )
                CONNECT BY NOCYCLE
                        have = PRIOR needs
                )
        GROUP BY
                root
        )
CONNECT BY NOCYCLE
        have = PRIOR needs

Обновление:

Из вашего поста я вижу, что у вас есть ограничение на максимальную длину цикла.

Это значительно облегчает решение этой проблемы.

Просто добавьте условие ограничения цикла в каждый из запросов:

SELECT  n.*, CONNECT_BY_ROOT(have), level
FROM    v_needs n
START WITH
        have IN
        (
        SELECT  MIN(have)
        FROM    (
                SELECT  have, CONNECT_BY_ROOT(have) AS root
                FROM    t_needs
                START WITH
                        have IN
                        (
                        SELECT  have
                        FROM    t_needs n
                        WHERE   CONNECT_BY_ISCYCLE = 1
                        CONNECT BY NOCYCLE
                                needs = PRIOR have
                                AND level <= 5
                        )
                CONNECT BY NOCYCLE
                        have = PRIOR needs
                        AND level <= 5
                )
        GROUP BY
                root
        )
CONNECT BY NOCYCLE
        have = PRIOR needs
        AND level <= 5

Это остановит обход иерархического дерева на уровне 5th.

Если у вас есть 1,000,000 пользователей в вашей базе данных и 5 совпадений на пользователя в среднем, запрос должен будет проверить 1,000,000 * 5^5 = 3,125,000,000 строк, что является наблюдаемым числом строк.

Запрос будет значительно улучшен, если вы MATERIALIZE представите свое представление и создадите индексы 'need' и 'have'.

В этом случае выполнение запроса займет считанные минуты.

Answer 2

Это отличное начало для меня. Я бился головой о стену в течение нескольких дней. Позвольте мне дать еще несколько деталей, чтобы прояснить это. К сожалению, эта проблема является проблемой клика и является NP-полной, потому что все три столбца не являются уникальными.

Вот реальное приложение: я делаю исследовательский проект по эффективности отрицательной взаимности, то есть бартер, вместо обмена валют, где это неуместно или незаконно.

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

Если у меня есть база данных с тысячами получателей и десятками тысяч потенциальных доноров, я потенциально могу заключить многостороннюю транзакцию, чтобы максимизировать выгоду для максимально возможного числа получателей.

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

До сегодняшнего дня я никогда не слышал об Oracle Spatial. Похоже, это может быть именно тот продукт, который мне нужен, чтобы сделать это проще.