powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Как реализовать сравнение множеств?
23 сообщений из 23, страница 1 из 1
Как реализовать сравнение множеств?
    #39235197
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Уважаемые профи, подскажите, пожалуйста, новичку, как наиболее эффективно (простота, производительность, расширяемость)
реализовать сравнение множеств? В Кратких источниках инфы не нашел, Дейта читать начал, но не хватает ни подготовки, ни времени, чтобы осилить.
Интересует прежде всего общий подход, принципы (частных случаев, где это требуется, даже у меня несколько).

Дано:
- интернет-проект, работа в интерактивном режиме, в реальном времени. Планируемая нагрузка - несколько тысяч хостов в сутки.
- язык PHP
- СУБД не выбрана, выбор во многом зависит от ответа на указанный выше вопрос. С др. стороны, выбор ограничен бесплатными СУБД, пока рассматриваю MySQL и Postgresql.

Есть сущности (порядка 20 тысяч), у которых есть однородные свойства.
Общий набор свойств - около 1 тысячи, но каждая сущность обладает только 1-50 из этого набора.
Пользователь задает несколько произвольных сущностей, программа получает из базы и производит пересечение множеств их свойств. (На этом этапе особых сложностей не вижу, все варианты сработают.)
Далее возникает сложность: нужно найти в базе те сущности, у которых есть то же (пересеченное) множество свойств (в идеале - не только полное, но и частичное).

Проблема: Не знаю, как лучше организовать такой поиск.

Мои варианты:

1) свойства каждой сущности реализовать массивами. Использовать Постгрес (не работал с этой СУБД). Наиболее понятный для меня путь, тем более, что свойства могут быть в различной степени выражены и иметь др. характеристики, что можно реализовать многомерностью массивов. Не знаю, однако, будет ли такой поиск (сравнение массивов) работать:
а) корректно, б) сравнимо по производительности, скорости со вторым.

2) создать отдельную таблицу свойств (поля) и сущностей (записи), в ячейках собственно писать степени выраженности свойства у сущности (например, 0 - 100%). Фактически др. реализация двумерного массива. Насколько я понимаю, больше подходит под
концепцию реляционной базы, но становится громоздкой (тысяча полей и 20 тысяч строк), нечитабельной.
И запрос на поиск становится достаточно громоздким - типа: SELECT * FROM свойства WHERE поле1>0 AND поле2>0
AND поле23>0 ... AND поле45>0 (или его можно оптимизировать?).

Есть ли более эффективные варианты или какой из моих эффективнее? Спасибо!
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235225
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Проблема: Не знаю, как лучше организовать такой поиск.
Пересечение множеств делается с помощью оператора JOIN. Частичные пересечения получаются
за счёт фильтрации по количеству совпадающих атрибутов. Например, так:
Код: sql
1.
2.
3.
4.
select t1.id, count(*), count(t2.id)
  from t t1 left join t t2 on t1.attrib_value = t2.attrib_value
  group by t1.id, t2.id
  having count(t2.id) > 0


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235244
Фотография DirksDR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234,

Сформируй в таблице сущностей строковое поле PropertyList, которое содержит упорядоченный список свойств (или id свойств).
Например: PropertyList=',поле1,поле2,поле23, ...,поле45,'
Поиск будешь делать так:
SELECT * FROM сущности WHERE PropertyList like '%,поле1,%,поле2,%,поле23,% ...%,поле45,%'.
Сравнить по маске 20 тыс сущностей не так уж долго.
Поля в маске тоже должны быть упорядоченны.
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235268
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry Sibiryakov,

Спасибо за пример. Но мне бы сначала определиться с ОРГАНИЗАЦИЕЙ данных, для эффективной манипуляции ими (т.е. сравнения множеств).
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235280
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
DirksDR, спасибо! Подобная идея мне приходила в голову - загнать списки свойств в строку и искать LIKE или регулярными выражениями. Но будет ли это работать при различном кол-ве и порядке перечисления свойств у сущностей? Можно, конечно, перевести все свойства в числовые коды (четырехзначные) и упорядочить их при вставке по возрастанию. Но и тогда мне кажется, что этот вариант проигрывает тем двум, которые я привел выше. Если таблица 20000х1000 (второй мой вариант) может быстро обрабатываться, то пока выглядит предпочтительней - нет дублирования, возможно просто добавлять и изменять сущности и свойства....
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235323
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Но мне бы сначала определиться с ОРГАНИЗАЦИЕЙ данных, для эффективной
манипуляции ими (т.е. сравнения множеств).
Тебе бы сначала изучить теорию множеств. А далее просто: любая реляционная таблица это
множество, а выборка из неё - подмножество.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235341
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry Sibiryakov,

но я правильно понял, что вы лично - за второй вариант? (И ваш пример выборки как раз по этой таблице?)
Просто я пытаюсь найти самый эффективный вариант организации данных (быстрый, надежный, производительный) для сравнения множеств (в данном случае - пересечение чаще всего используется) + с учетом, что свойства сущностей могут иметь доп. характеристики (многомерный массив мне ближе по восприятию в практике, так получилось :))
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235375
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Просто я пытаюсь найти самый эффективный вариант организации данных
(быстрый, надежный, производительный) для сравнения множеств
Эва... Рекомендую ещё поискать святой грааль и чайник Рассела. С ними может получиться
проще и быстрее.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235445
Кот Матроскин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234,
Помимо ваших вариантов есть еще третий - сделать дополнительную таблицу свойств (IDСущности, ИмяСвойства, ЗначениеСвойства).
тогда отбирающий запрос будет выглядеть примерно
Код: sql
1.
2.
3.
4.
5.
select IDСущности
from Свойства
where ИмяСущности  in (<Здесь Ваш список пересечения, найденный на первом этапе>)
group by IDСущности
having count(*) = <Количество в списке пересечения>
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39235549
Фотография vadiminfo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234

Проблема: Не знаю, как лучше организовать такой поиск.


Если имеется в виду пересечение множеств, то, к примеру, у Оракла (но наверное не только у него) есть: intersect.

первое множество:
select * from
(
select 1, 2 from dual
union all
select 1, 3 from dual
)

второе
select * from
(
select 1, 2 from dual
union all
select 1, 4 from dual
)


Их пересечение:

select * from
(
select 1, 2 from dual
union all
select 1, 3 from dual
)
intersect
select * from
(
select 1, 2 from dual
union all
select 1, 4 from dual
)
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39236543
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Спасибо всем!
Насчет доп. таблицы - не совсем понял смысл ее.
Насчет Intersect - да, это выглядит лучше, чем Join, понятнее, по кр. мере. Вроде, Постгрес поддерживает? MySQL, кажется, нет.

А с массивами в Постгрес никто не работал? (Мой первый вариант). Там тоже есть простые запросы на пересечение и т.д. Все-таки очень интересно было бы узнать, как в реальности работает (надежность, производительность по сравнению со вторым вариантом)?
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39236792
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кот Матроскинcoder234,
Помимо ваших вариантов есть еще третий - сделать дополнительную таблицу свойств (IDСущности, ИмяСвойства, ЗначениеСвойства).
тогда отбирающий запрос будет выглядеть примерно
Код: sql
1.
2.
3.
4.
5.
select IDСущности
from Свойства
where ИмяСущности  in (<Здесь Ваш список пересечения, найденный на первом этапе>)
group by IDСущности
having count(*) = <Количество в списке пересечения>



Вот, все-таки заинтересовал меня этот вариант. Общая идея. Хотя я и не понял (поясните?), в чем смысл "дополнительности" таблицы, если это альтернатива (строгое ИЛИ) моим двум вариантам, и запрос остался мной непонятым, особо в части
авторin (<Здесь Ваш список пересечения, найденный на первом этапе>)

Конечно, на первый взгляд выглядит "не совсем эстетично", по таблице - "куча" дублирующихся сущностей с кучей дублирующихся свойств. Но пара сущность-свойство и далее - возможность нарастить характеристики свойства с помощью доп. столбцов + относительная простота выборки подкупают.... Хотя при таком варианте получается таблица ДО 1 млн строк... (Об обновлении - при изменении сущностей-свойств) не упоминаю...
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39236891
Кот Матроскин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Кот Матроскинcoder234,
Помимо ваших вариантов есть еще третий - сделать дополнительную таблицу свойств (IDСущности, ИмяСвойства, ЗначениеСвойства).
тогда отбирающий запрос будет выглядеть примерно
Код: sql
1.
2.
3.
4.
5.
select IDСущности
from Свойства
where ИмяСущности  in (<Здесь Ваш список пересечения, найденный на первом этапе>)
group by IDСущности
having count(*) = <Количество в списке пересечения>



Вот, все-таки заинтересовал меня этот вариант. Общая идея. Хотя я и не понял (поясните?), в чем смысл "дополнительности" таблицы, если это альтернатива (строгое ИЛИ) моим двум вариантам,

Вам не нравится слово "дополнительная"? Я имел в виду две таблицы - "Сущности" и "СвойстваСущностей". Если кроме свойств поиска у Ваших сущностей нет атрибутов, и Вы не видите проблем с получением IDсущности - ну да, таблицу самих сущностей можно не делать, и тогда описанная таблица станет основной.

coder234 и запрос остался мной непонятым, особо в части
авторin (<Здесь Ваш список пересечения, найденный на первом этапе>)

А что тут непонятного? Вот Вы, цитирую, "произвели пересечение множеств их свойств" (запросом или на клиенте) - вот результат этого пересечения подставьте вместо моих угловых скобок.
Если запросом - подставьте запрос, если на клиенте - сформируйте строку-перечисление через запятую и подставьте ее.

авторНо пара сущность-свойство и далее - возможность нарастить характеристики свойства с помощью доп. столбцов + относительная простота выборки подкупают.... Хотя при таком варианте получается таблица ДО 1 млн строк...

Тут надо понимать, что структура хороша именно для описанной Вами задачи - сравнения множеств свойств. Для обычного поиска по значениям свойств, типа "найти все детали из алюминия весом более 500г" - она подходит, ээ, не блестяще.
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39237121
servit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234СУБД не выбрана, выбор во многом зависит от ответа на указанный выше вопрос.

Есть ли более эффективные варианты <..>?Есть. Например, в СУБД Caché можно обойтись одним полем, в котором хранить сразу множество значений и строить индексы по ним.
Есть и соответствующее расширение SQL для поиска по таким полям (см. подробности в статье ).
Например для Вашей задачи можно сделать подобное:
Код: plaintext
Дана таблица "сущность" со следующими данными:
имямножествоe11,5,9e25,1,9,4e33,0,4e47,8,5
1) найти все сущности, множество которых содержит значения 4 и/или 5:

select * from сущность where for some %element(множество) (%value in (4,5))

Результат:
имямножествоe25,1,9,4e33,0,4e11,5,9e47,8,5
2) найти все сущности, множества которых входят (полностью или частично) в множества из сущностей 'e1' и/или 'e4' (т.е. 1,5,9,7,8,5):

select * from сущность where for some %element(множество) (%value %inlist (select $listfromstring(list(множество)) from сущность where имя in ('e1','e4')))

Результат:имямножествоe11,5,9e25,1,9,4e47,8,5Сгенерировал 20000 сущностей, в каждом множестве из которых от 1 до 50 полей со значениями от 1 до 1000.
Запрос вида 2) отрабатывает за 0.212 cек., из которых execute=0.003, fetch=0.209; количество вернувшихся записей = 11422.
Увеличение количества сущностей и/или полей в множестве не сильно скажется на скорости из-за наличия индексов.coder234Дано:
- интернет-проект , работа в интерактивном режиме, в реальном времени . Планируемая нагрузка - несколько тысяч хостов в сутки.
<..>
С др. стороны, выбор ограничен бесплатными СУБД, пока рассматриваю MySQL и PostgresqlХотя Caché и не бесплатна, но для стартапов есть интересные модели оплаты , например Revenue Share (отчисления от дохода), и хостинг.
Уже есть успешные примеры (см. ссылку выше).
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39237287
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кот Матроскин, спасибо, понятно.

servit, и вам большое спасибо, особо за выкладки по времени выполнения - буду сравнивать :)
Но более распространенная и бесплатная СУБД Postgresql предоставляет похожий функционал (массивы, индекс). Наверное, я постараюсь сделать несколько вариантов на стенде и сравнить.
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39247303
servit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Наверное, я постараюсь сделать несколько вариантов на стенде и сравнить.Сравнили?
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39247545
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234DirksDR, спасибо! Подобная идея мне приходила в голову - загнать списки свойств в строку и искать LIKE или регулярными выражениями. Но будет ли это работать при различном кол-ве и порядке перечисления свойств у сущностей? Можно, конечно, перевести все свойства в числовые коды (четырехзначные) и упорядочить их при вставке по возрастанию. Но и тогда мне кажется, что этот вариант проигрывает тем двум, которые я привел выше. Если таблица 20000х1000 (второй мой вариант) может быстро обрабатываться, то пока выглядит предпочтительней - нет дублирования, возможно просто добавлять и изменять сущности и свойства....


это была дурацкая идея, зря ты благодаришь.

нормальная идея - это EAV. дальше найдешь.
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39247568
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
servit, Нет пока не сравнивал. Переключился на другие задачи пока, а эта пусть отлежится немного, дозреет :) Может,еще какие варианты появятся. Или укрепится вера в один -два из уже имеющихся.

MasterZiv, Насколько я понимаю, EAV - это именно то, что предложил ранее Кот Матроскин 19180551
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39253004
coder234
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым??

А может, вообще обойтись без СУБД, и самый быстрый вариант - XML?
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39253528
servit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234 ,

Лучше спросите на форуме PostgreSQL или поищите там про массивы, например: 7897242 , 19140597
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39253634
Фотография Павел Воронцов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым??

А может, вообще обойтись без СУБД, и самый быстрый вариант - XML?Чудак-человек. До тебя никто-никто никогда велосипедов не делал, ты первый. Вперед, без сомнений, только вперед! О результатах доложишь.
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39253982
mad_nazgul
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым??

А может, вообще обойтись без СУБД, и самый быстрый вариант - XML?

Самый быстрый вариант не XML, а plain text в памяти.
Для этого есть куча noSQL БД.
Скорости не чета PostgreSQL, но есть "нюансы" - про ACID стоит забыть. :-)

А так, если что, в PostgreSQL есть "массивы" и "JSON".
По которым можно строить индексы и делать запросы.
...
Рейтинг: 0 / 0
Как реализовать сравнение множеств?
    #39255157
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
coder234Не устаю удивляться: неужели так никто никогда и не сравнивал производительность в той же Postgresql работы с элементами в массивах в одном поле таблицы и разнесенными по разным полям (т.е. собсно вопрос 1 поста) ? Скоро вернусь к этой задаче и буду первым??
А может, вообще обойтись без СУБД, и самый быстрый вариант - XML?

DS ведь ответил уже:
Dimitry Sibiryakov любая реляционная таблица это
множество, а выборка из неё - подмножество.
...
Рейтинг: 0 / 0
23 сообщений из 23, страница 1 из 1
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Как реализовать сравнение множеств?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]