Найти одного представителя класса, Задача 3

добавлено: 02 апр 13
понравилось:0
просмотров: 1432
комментов: 0

теги:

Автор: Павел Воронцов

Эта задача встретилась мне в тестовом задании. Да простит меня работадатель... Было это уже достаточно давно и вряд ли все эти годы задания остаются неизменными. Но все же, если меня попросят убрать данное решение, я уберу.


/* Таблица характеристик товаров (размер, марка, цвет …) */
create table sp_type  ( type_id int not null primary key, name char(40) );
/* Таблица значений характеристик товаров ( XL, Казбек, красный, …) */
table sp_value  ( value_id int not null, name char(40), type_id int not null,
constraint spv_pk primary key (value_id, type_id )
,constraint spv_fk foreign key (type_id) references sp_type (type_id));
/* Таблица описаний товаров. Для каждого товара, для каждой характеристики из определенного 
для данного товара набора, указано ее значение. Товар, таким образом, это несколько строчек, 
объединенных одним значением goods */
table sp_set ( goods int not null, type_id int not null, value_id int not null
,constraint sps_pk primary key ( goods, type_id)
, constraint sps_fk1 foreign key (type_id) references sp_type (type_id)
, constraint sps_fk2 foreign key (value_id, type_id) references sp_value (value_id, type_id)
);

insert into Sp_type (Type_id,Name)
values (1,'Наименование');
insert into Sp_type (Type_id,Name)
values (2,'Размер');
insert into Sp_type (Type_id,Name)
values (3,'Цвет');
insert into Sp_type (Type_id,Name)
values (5,'Состав');
insert into Sp_type (Type_id,Name)
values (7,'Производитель');

insert into Sp_value (Value_id,type_id,Name)
values (6,1,'Полотенце');
insert into Sp_value (Value_id,type_id,Name)
values (7,2,'Большое');
insert into Sp_value (Value_id,type_id,Name)
values (8,3,'Красный');
insert into Sp_value (Value_id,type_id,Name)
values (10,5,'Хлопок');
insert into Sp_value (Value_id,type_id,Name)
values (12,7,'Китай');
insert into Sp_value (Value_id,type_id,Name)
values (13,3,'Белый');

insert into Sp_set (Goods,type_id,value_id)
values (1001,1,6);
insert into Sp_set (Goods,type_id,value_id)
values (1001,2,7);
insert into Sp_set (Goods,type_id,value_id)
values (1001,3,8);
insert into Sp_set (Goods,type_id,value_id)
values (1002,1,6);
insert into Sp_set (Goods,type_id,value_id)
values (1002,2,7);
insert into Sp_set (Goods,type_id,value_id)
values (1002,5,10);
insert into Sp_set (Goods,type_id,value_id)
values (1002,7,12);
insert into Sp_set (Goods,type_id,value_id)
values (1003,1,6);
insert into Sp_set (Goods,type_id,value_id)
values (1003,2,7);
insert into Sp_set (Goods,type_id,value_id)
values (1003,3,13);


Задача: пользователь указывает некоторое множество значений T из {sp_type.type_id}. Среди товаров, описанных в sp_set найдутся такие, что все характеристики из T им приписываются. Среди них так же, возможно, найдется несколько таких, что у них все значения характеристик из T совпадают. Такие товары называются эквивалентными. Получается, что множество T задает множество классов эквивалентности товаров. Требуется написать запрос, позволяющий получить ровно по одному представителю из каждого класса, приняв в качестве параметра множество T и число его элементов.

Например, дано T={1,2,3}
Получаем на выходе :
GoodsType_idValue_id
100116
100127
100138
100316
100327
1003313

Например, дано T={1,2}
Получаем на выходе :
GoodsType_idValue_id
100116
100127

при этих же параметрах, на выходе можно было бы получить и такое:
GoodsType_idValue_id
100216
100227


Решение:
Предположим, что у нас есть хранимая процедура, куда передается табличная переменная table @tmp_set (id int not null primary key), в которую занесены идентификаторы интересующих нас атрибутов.

select t.*
from sp_set t join (select max(a.goods) as id /* нас интересует любой продукт из эквивалентных
                                                             , пусть будет максимальный */
from (
select goods, -- идентификатор продукта
sum(1.0/(type_id+1.0/value_id)) as m, /* идентификатор набора атрибутов данного продукта */
count(*) as c /* количество атрибутов в наборе */
from sp_set
where type_id in (select id from @tmp_set) /* только те продукты, у кого есть интересующие нас атрибуты */
group by goods) a
where a.c = (select count(*) from @tmp_set) /* количество атрибутов совпадает, то есть продукт имеет ВСЕ 
                                  атрибуты из  интересующего нас набора */
group by a.m /* группируем наборы */
) b on b.id = t.goods 
and t.type_id in (select id from @tmp_set); /* только атрибуты из интересующего нас набора */

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

Комментарии




Необходимо войти на сайт, чтобы оставлять комментарии