Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / Поиск при связях "многие ко многим" / 15 сообщений из 15, страница 1 из 1
28.01.2008, 00:23
    #35090533
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Здравствуйте. Вот какая ситуация.

Имеем табличку users ( user_id serial, user_name varchar ).
Здесь хранятся записи о пользователях. Каждая запись - один пользователь.
Пример:
1 | Вася
2 | Гоша

Имеем табличку tags ( tag_id serial, tag_name varchar).
Здесь хранятся теги пользователя (интересы). Т.е. ключевые слова, которые могут быть в БД.
Пример:
1 | Интернет
2 | Компьютеры
3 | Кино
4 | Пиво
5 | Лажа

Имеем табличку usertags ( ref_id serial, user integer, tag integer).
Здесь хранятся связи пользователей и тегов. Поле ref_id - просто первичный ключ
Пример:
1 | 1 | 1 /* Вася любит Интернет */
2 | 1 | 3 /* Вася любит Кино */
3 | 1 | 4 /* Вася любит Пиво*/
4 | 2 | 1 /* Гоша любит Интернет */
5 | 2 | 4 /* Гоша любит Пиво */
6 | 2 | 5 /* Гоша любит Лажу */
7 | 2 | 3 /* Гоша любит Кино */

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

У пользователей эти интересы могут пересекаться.

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

Делаю всё это в PostgreSQL.

Помогите, если знаете как.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 00:56
    #35090546
pamir
pamir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Михаил Кечиновесли я ищу по тегам "Пиво" и "Лажа", мне должны попасться все пользователи, у которых есть этот тег, но у них могут быть при этом и другие теги.Имеется ввиду, что должны быть ОБА этих тега ОБЯЗАТЕЛЬНО, но не обязательно они будут единственными тегами у пользователя? Или достаточно одного из двух?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 10:22
    #35090917
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Желательно потом реализовать И и ИЛИ, но сейчас требуется только И. Т.е. чтобы оба тега были.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 10:47
    #35090975
LeXa NalBat
LeXa NalBat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
например так. не проверял.

select * from
users as u
join ( select user from usertags where tag=4 ) as t4 on (u.user_id=t4.user) -- пиво
join ( select user from usertags where tag=5 ) as t5 on (u.user_id=t5.user) -- лажа
;
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 11:14
    #35091052
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
А если я не знаю конкретные теги, которые мне нужны? К примеру, я знаю идентификатор пользователя, у которого есть набор тегов. Я хочу найти пользователей, которые имеют те же теги (а может быть дополнительно и другие), которые имеет пользователь №1.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 11:30
    #35091110
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
К примеру, вот что я придумал:

SELECT DISTINCT user FROM usertags WHERE tag IN (
SELECT tag FROM usertags WHERE user = 1
)

1. Выбираем идентификаторы тегов, которые имеются у пользователя № 1 (можем подставить любого)
2. Выбираем идентификаторы пользователей из таблички связи тегов и пользователей, у которых идентификатор тега имеется в найденных тегах пользователя 1.

Это позволяет получить идентификаторы пользователей по ИЛИ. Как бы сделать, чтобы еще и по И было?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 11:40
    #35091151
LeXa NalBat
LeXa NalBat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
попробуйте примерно так

select user, count(*) as tnum from
( select tag from usertags where user = ? ) as t1 natural join usertags as t2
group by user having tnum = ( select count(*) from usertags where user = ? );

можно сделать "нечеткое И" заменив having на order by tnum desc.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 12:46
    #35091387
pamir
pamir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
В голову пришла шальная мысль. Добавить юзеру поле, какое-нибудь tag_hash. Заполнять его на триггере при изменении его тэгов. Заполнять следующим образом... в общем степенями двойки, где степени - id тэгов.
Т.е. для
1 | 1 | 1 /* Вася любит Интернет */
2 | 1 | 3 /* Вася любит Кино */
3 | 1 | 4 /* Вася любит Пиво*/

для Васи получаем 2 1 + 2 3 + 2 4 = 2+8+16 = 26.

Далее выбираем всех, у кого побитовое произведение дает тоже число. Т.е. 26 присутствует в полной мере.
Забыл битовое умножение в постгресе, но вообщем это выглдело бы так
1. Берем это число для образцового юзера - templ_user
Код: plaintext
select into templ_hash tag_hash from users where user_id= templ_user
2. Находим всех, кто нам нужен.
Код: plaintext
select * from users where (tag_hash and templ_hash) = templ_hash

Опять же - если нужно нечеткое И, то результат должен быть равен не templ_hash, а просто больше нуля - т.е. хоть одно из этого присутствует.

Можно написать процедуру, которая будет возвращать набор записей, принимая параметром образцового юзера (или по желанию уже полученый templ_hash)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.01.2008, 18:08
    #35092805
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Спасибо, я попробую сегодня и то и другое.

Но во втором случае - что будет, если номер тега будет № 10000 ? Слов-то много может быть.
Циферка великовата получается:
2 10000 = 1,9950631168807583848837421626836e+3010
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2008, 17:19
    #35095471
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
авторselect user, count(*) as tnum from
( select tag from usertags where user = ? ) as t1 natural join usertags as t2
group by user having tnum = ( select count(*) from usertags where user = ? );

В этом запросе ругается на алиас tnum в конструкции having tnum
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2008, 17:43
    #35095573
LeXa NalBat
LeXa NalBat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Михаил КечиновВ этом запросе ругается на алиас tnum в конструкции having tnum having count(*)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2008, 20:00
    #35095872
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
А так я пробовал, выдает ноль строк.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.01.2008, 11:02
    #35096640
LeXa NalBat
LeXa NalBat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Михаил КечиновА так я пробовал, выдает ноль строк.вы ошиблись
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
create table usrtags (
 usr integer,
 tag integer
);

insert into usrtags select generate_series( 1 , 8 ), generate_series( 1 , 4 );
insert into usrtags select generate_series( 1 , 8 ), generate_series( 5 , 6 );

select * from usrtags order by usr, tag;

select usr, count(*) from
( select tag from usrtags where usr =  1  ) as t1 natural join usrtags as t2
group by usr having count(*) = ( select count(*) from usrtags where usr =  1  )
order by usr;

select usr, count(*) from
( select tag from usrtags where usr =  1  ) as t1 natural join usrtags as t2
group by usr order by count(*) desc, usr asc;

drop table usrtags;
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
nalbat=> select usr, count(*) from
nalbat-> ( select tag from usrtags where usr =  1  ) as t1 natural join usrtags as t2
nalbat-> group by usr having count(*) = ( select count(*) from usrtags where usr =  1  )
nalbat-> order by usr;
 usr | count
-----+-------
    1  |      2 
    5  |      2 
( 2  rows)

nalbat=> select usr, count(*) from
nalbat-> ( select tag from usrtags where usr =  1  ) as t1 natural join usrtags as t2
nalbat-> group by usr order by count(*) desc, usr asc;
 usr | count
-----+-------
    1  |      2 
    5  |      2 
    3  |      1 
    7  |      1 
( 4  rows)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.01.2008, 02:36
    #35099133
Михаил Кечинов
Михаил Кечинов
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
Спасибо. Я попробую ваш пример.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.01.2008, 14:28
    #35100677
resu--
resu--
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск при связях "многие ко многим"
я совершенно согласен с pamirВ голову пришла шальная мысль. Добавить юзеру поле, какое-нибудь tag_hash. Заполнять его на триггере при изменении его тэгов...

и хотел бы добавить, что hash можно сравнивань не только по условию "=", а (вспомнив МНК (метод наименьших квадратов: 1 курс 2й семестер) - выдавать список совпадений по увеличению расхождений. гдето так:

... ORDER BY min( ( hash - hash_of_the_user )^2 ) -- это степень совпадения

т.к. такой select требует клаузы GROUP BY, которая может длится долго, рекомедую хранить степень совпадения в отдельной таблице и пересчитывать ее или по тригеру или регулярно по (cron'у), но не непосредственно перед быдачей пользователю.

ну и конечно число юзеров превышает (и намного) число всевозможный кашей, то и их можно вынести в отдельную таблицу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / Поиск при связях "многие ко многим" / 15 сообщений из 15, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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