MySQL: эффективный способ вычисления набора мощностей Venn-Diagram - PullRequest
Новая
       31

MySQL: эффективный способ вычисления набора мощностей Venn-Diagram

0 голосов
/ 10 ноября 2018

Учитывая 4 таблицы, каждая из которых содержит предметы и представляет один набор, как получить количество предметов в каждом отсеке, необходимое для построения диаграммы Венна, как показано ниже.Расчет должен выполняться на сервере MySQL, избегая передачи элементов на сервер приложений.

Примеры таблиц: 

s1:         s2:         s3:         s4:
+------+    +------+    +------+    +------+
| item |    | item |    | item |    | item |
+------+    +------+    +------+    +------+
| a    |    | a    |    | a    |    | a    |
+------+    +------+    +------+    +------+
| b    |    | b    |    | b    |    | c    |
+------+    +------+    +------+    +------+
| c    |    | c    |    | d    |    | d    |
+------+    +------+    +------+    +------+
| d    |    | e    |    | e    |    | e    |
+------+    +------+    +------+    +------+
| ...  |    | ...  |    | ...  |    | ...  |

Теперь, я думаю, я бы рассчитал некоторые установленные мощности.Некоторые примеры с I соответствуют s1, II до s2, III до s3 и IV до s4:

quadruple Venn Diagram - Venn diagram made from 4 sets using ellipses

Если я переинтерпретирую sx как набор, я бы написал:

  1. |s1 ∩ s2 ∩ s3 ∩ s4| - белый 25 в центре
  2. |(s1 ∩ s2 ∩ s4) \ s3|- белый 15 справа внизу относительно центра
  3. |(s1 ∩ s4) \ (s2 ∪ s3)| - белый 5 внизу
  4. |s1 \ (s2 ∪ s3 ∪ s4)| - темно-синий 60 на синем фоне
  5. ... до 15.

Как эффективно рассчитать эти мощности на сервере MySQL?Предоставляет ли MySQL функцию, помогающую в вычислениях?

Наивным подходом будет запуск запроса для 1. 

SELECT count(*) FROM(
SELECT item FROM s1
INTERSECT
SELECT item FROM s2
INTERSECT
SELECT item FROM s3
INTERSECT
SELECT item FROM s4);

и другого запроса для 2. 

SELECT count(*) FROM(
SELECT item FROM s1
INTERSECT
SELECT item FROM s2
INTERSECT
SELECT item FROM s4
EXCEPT
SELECT item FROM s3);

и т. д., в результате 15 запросов.

Ответы [ 3 ]

0 голосов
/ 17 ноября 2018

Попробуйте что-то вроде этого: 

with universe as (
    select * from s1 
    union
    select * from s2
    union
    select * from s3
    union
    select * from s4
),
regions as (
    select
        case when s1.item is null then '0' else '1' end
        ||
        case when s2.item is null then '0' else '1' end
        ||
        case when s3.item is null then '0' else '1' end
        ||
        case when s4.item is null then '0' else '1' end as Region
    from universe u
    left join s1 on u.item = s1.item
    left join s2 on u.item = s2.item
    left join s3 on u.item = s3.item
    left join s4 on u.item = s4.item
)
select Region, count(*) from regions group by Region

Отказ от ответственности: я проверял это только в SQLite. Возможно, вам понадобится SET sql_mode='PIPES_AS_CONCAT', чтобы конкатенация строк ANSI работала в MySQL, или вместо этого используйте функцию concat. Синтаксис WITH поддерживается только начиная с версии 8.0 MySQL, но вместо этого вы можете использовать временные таблицы или вложенные запросы.

Если наборы очень велики, вы можете проиндексировать столбец item перед запросом на тот случай, если оптимизатор SQL не поймет это сам.

0 голосов
/ 25 ноября 2018

Вопрос немного сложен, поэтому ответы есть.Позвольте мне объяснить ответ КТ 

with universe as (
    select * from s1 
    union
    select * from s2
    union
    select * from s3
    union
    select * from s4
),
regions as (
    select
        case when s1.item is null then '0' else '1' end
        ||
        case when s2.item is null then '0' else '1' end
        ||
        case when s3.item is null then '0' else '1' end
        ||
        case when s4.item is null then '0' else '1' end as Region
    from universe u
    left join s1 on u.item = s1.item
    left join s2 on u.item = s2.item
    left join s3 on u.item = s3.item
    left join s4 on u.item = s4.item
)
select Region, count(*) from regions group by Region

Результат universe приводит к ОБЪЕДИНЕНИЮ всех таблиц (исключены дубликаты), что-то вроде 

+------+
| item |
+------+
| a    |
+------+
| b    |
+------+
| c    |
+------+
| d    |
+------+
| e    |
+------+
| ...  |
+------+

Тогда s1, s2, s3 и s4объединяются 

+------+---------+---------+---------+---------+
| item | s1.item | s2.item | s3.item | s4.item |
+------+---------+---------+---------+---------+
| a    | a       | a       | a       | a       |
+------+---------+---------+---------+---------+
| b    | b       | b       | b       | NULL    |
+------+---------+---------+---------+---------+
| c    | c       | c       | NULL    | c       |
+------+---------+---------+---------+---------+
| d    | d       | NULL    | d       | d       |
+------+---------+---------+---------+---------+
| e    | NULL    | e       | e       | e       |
+------+---------+---------+---------+---------+
| ...  | ...     | ...     | ...     | ...     |
+------+---------+---------+---------+---------+

и преобразуются в двоичную строку (0: если ячейка NULL; 1: еще) с именем Region, где первая цифра соответствует s1, вторая - s2 и т. д. 

+------+--------+
| item | Region |
+------+--------+
| a    | 1111   |
+------+--------+
| b    | 1110   |
+------+--------+
| c    | 1101   |
+------+--------+
| d    | 1011   |
+------+--------+
| e    | 0111   |
+------+--------+
| ...  | ...    |
+------+--------+

и, наконец, агрегированы и сгруппированы по регионам 

+--------+-------+
| Region | count |
+--------+-------+
| 1111   | 1     |
+--------+-------+
| 1110   | 1     |
+--------+-------+
| 1101   | 1     |
+--------+-------+
| 1011   | 1     |
+--------+-------+
| 0111   | 1     |
+--------+-------+
| ...    |       |
+--------+-------+

Обратите внимание, что регионы с 0 заданными элементами в них не отображаются в результатах и ​​0000 никогда не будет (= элемент не является частьюлюбого набора s1, s2, s3, s4), таким образом, есть 15 областей.

4-set venn diagram with regions in binary representation

0 голосов
/ 14 ноября 2018

Следующая процедура:

  1. Создана хранимая процедура, которая создает временные таблицы в памяти, содержащие наборы.
  2. Помните, что MySQL не позволяет вам ссылаться на временные данныеТаблица памяти более одного раза в запросе.
  3. Как отмечалось, MySQL не имеет INTERSECT или EXCEPT.Но вы можете подражать им.Удаляя дубликаты из ваших исходных / необработанных наборов, эмуляция может быть еще более упрощена.
  4. Принято решение сохранить вычисленное значение в каждой переменной и вывести таблицу, состоящую из всех 15 из этих значений, соответствующих компонентам.

На данный момент я придумал https://gist.github.com/Rillke/c2da0921f8f2a047615f41fab8781c11

...