Каков наиболее эффективный способ хранения наборов в базе данных?

Question

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

Например, если моя база данных имеет множество {1, 2, 3}, {2, 3, 5}, {5, 10, 12}, и я запросить его для:

• множеств, (2, 3), {2, 3, 5}
• Наборы, которые являются подмножествами {1, 2, 3, 4}, должны дать мне {1, 2, 3}, {2, 3, 5} , 2, 3}
• Наборы, которые пересекаются с {1, 10, 20} он должен дать мне {1, 2, 3}, {5, 10, 12}

Answer 1

"Эффективное" может означает много вещей, но нормализованный способ состоял бы в том, чтобы иметь таблицу Items со всеми возможными элементами и таблицу Sets со всеми наборами и таблицу поиска ItemsSets. Если у вас есть наборы A и B в таблице Sets, запросы, подобные (для этого, для ясности, а не для оптимизации ... также «Set» - плохое имя для таблицы или поля, поскольку это ключевое слово)

SELECT itemname FROM Items i 
WHERE i.itemname IN 
(SELECT itemname FROM ItemsSets isets WHERE isets.setname = 'A') 
AND i.name IN 
(SELECT itemname FROM ItemsSets isets WHERE isets.setname = 'B') 

Это, например, пересечение A и B (вы можете почти наверняка ускорить это как ОБЪЕДИНЕНИЕ, опять же, «эффективный» может означать много вещей, и вам понадобится архитектура, которая позволяет использовать запрос, например что). Аналогичные запросы могут быть сделаны, чтобы узнать разницу, дополнение, тест на равенство и т. Д.

Теперь я знаю, что вы спросили об эффективности, и это ужасно медленный способ запроса, но это единственный надежный масштабируемый архитектуре для таблиц, чтобы сделать это, и запрос был просто простым, чтобы показать, как создаются таблицы. Вы можете делать всевозможные сумасшедшие вещи, скажем, пересечения кешей или хранить несколько элементов, которые находятся в одном наборе, и обрабатывать это или что у вас есть. Но не надо. Cached информация в конечном итоге будет устаревать; статические ограничения на количество элементов в размере поля будут превзойдены; ad-hoc члены новых кортежей будут неверно истолкованы.

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

Answer 2

Поскольку некоторые наборы неизвестны заранее (ваш комментарий предполагает, что они исходят от клиента в качестве критерия поиска), вы не можете «предусмотреть» установленные отношения в базе данных. Даже если бы вы могли это сделать, это означало бы избыточность и, следовательно, возможность для несоответствий.

Вместо этого, я хотел бы сделать что-то вроде этого:

CREATE TABLE "SET" (
    ELEMENT INT, -- Or whatever the element type is. 
    SET_ID INT, 
    PRIMARY KEY (ELEMENT, SET_ID) 
) 

Дополнительные предложения:

• Обратите внимание, как ЭЛЕМЕНТ поле находится на переднем крае первичного ключа. Это должно помочь запросам ниже, чем PRIMARY KEY (SET_ID, ELEMENT). Вы можете добавить последний, если хотите, но если вы этого не сделаете, то вы также должны ...
• Cluster таблица (если ваша СУБД поддерживает ее), что означает, что вся таблица представляет собой всего лишь одно B-дерево (и без кучи таблицы). Таким образом, вы максимизируете производительность запросов ниже и сводите к минимуму требования к хранилищу (и эффективность кеша).

Вы можете найти идентификаторы наборов, которые равны или надмножества (например) множества {2, 3}, как это:

и наборы, которые пересекаются {2, 3}, как это:

SELECT SET_ID 
FROM "SET" 
WHERE ELEMENT IN (2, 3) 
GROUP BY SET_ID; 

и устанавливает, которые равны или являются подмножествами {2, 3}, как это:

SELECT SET_ID 
FROM "SET" 
WHERE SET_ID NOT IN (
    SELECT SET_ID 
    FROM "SET" S2 
    WHERE S2.ELEMENT NOT IN (2, 3) 
) 
GROUP BY SET_ID;