Страницы

понедельник, 29 ноября 2010 г.

Построение множеств в реляционной базе данных

Человеческий мозг интересная штука, особенно интересно наблюдать, как ты работаешь, напряженно думаешь, строишь огромные схемы, чтоб решить какую-то задачу, а потом вдруг озарение и в результате 50 строк предыдущего кода заменяются на 10 нового. Данная заметка родилась примерно так. Поговорим об организации простых математических множест в реляционной базе данных.
Множество это набор элементов, если по простому. Первое, что нужно нам иметь возможность делать - это получать список элементов входящих в множество.

Потребность в решении задачи возникло при составлении списка взаимозаменяемых автозапчастей. Потому первое решение( к сожелению) было примерно таким:

create table crosses( p_key1 int(11), p_key2 int(11) )
Где p_key1 и p_key2 соответственно номера деталей, которые эквивалентны. Если "деталь1" может заменить "деталь2", а "деталь2" может заменить "деталь3", тогда логично предпложить, что "деталь1" может заменить "деталь3", это называется транзитивностью, это не обязательная характеристика элементов множеств, но в нашем примере имеет место. Собственно для эти трех деталей потребуется как минимум две записи. Чтобы охарактеризовать связь между всеми тремя, но это теория. А на практике, чтобы не путаться в запросах, потому что таких деталей может быть больше десятка, вроде бы стало удобно для каждой записи хранить ее кросы. То есть для примера из трех деталей мы получили бы следующий вид :
p_key1 p_key2
"деталь1" , "деталь2"
"деталь1" , "деталь3"
"деталь2" , "деталь1"
"деталь2" , "деталь3"
"деталь3" , "деталь2"
"деталь3" , "деталь1"
Уже настараживает...А теперь введем еще пару факторов такие как
1) Оператор ошибается, и добавляет неправильные элементы в существующие множества
2) Множества эквивалентных элементов всегда пополняется.
И теперь сразу видна неповоротливость данной схемы, что порадило априори кучу ошибок в логике работы, которые подтвердились на практике. Да и количество записей растет со скоростью n*(n-1), где n - количество деталей.
Второе решение сильно напоминающее экзоскелет. Написать переделать таблицу экивалентных деталей на манер экселя то есть :

create table crosses( p_key1 int(11), p_key2 int(11),p_key3 int(11), p_key4 int(11) .... )
Где p_key1, p_key2,p_key3 , эквивалентные детали. Размерность такой таблицы вызывает сомнения, потому что эквивалентных деталей может быть просто дикое количество, даже цифра в 100 уже вызывает сильные опасения. Приведем минусы
1) Добавление одного элемента уже в существующее множество приведет к операции сравнения по ста столбцам в худшем случае.
2) не будем же мы делать в самом деле таблицу из ста столбцов, мы напишем класс или библиотеку, которая работает с несколькими таблицами подобного типа, это нам позволит вроде бы избежать ограничения с размерностью.
3) явно видно что писать придеться снова много, ошибки неизбежны...

Собственно просто решение пришло, когда я обдумывал и набирался смелости взяться за описанные выше случай. Собственно идея в присвоение каждому множеству определенного идентификатора. Таблица приобретает вид


create table crosses(p_set int(11), p_key int(11) )
Где p_set уникальный идентификатор множества. Алгоритм работы прост. Мы нашли "деталь1", которая эквавалента другой "детале2". Мы начинаем поиск в таблице

SELECT p_set as p_set1 FROM crosses WHERE p_key='деталь1'

SELECT p_set as p_set2 FROM crosses WHERE p_key='деталь2'

Если первый и второй запрос дал результат, то мы на, например, заменяем p_set1 на p_set2 соответственно . То есть произошло слияние множеств.

UPDATE crosses SET p_set= $p_set1 WHERE p_set=$p_set2


Если какой из запросов дал результат, например нам стало известно $p_set2 то добавление нового свойства сводится к

INSERT INTO crosses(p_key,p_set) VALUES('деталь1',$p_set2)

Если оба запроса не дали результата, то создаем новый идентификатор например

LOCK TABLE crosses WRITE;

SELECT max(p_set)+1 FROM crosses
INSERT INTO crosses(p_set,p_key) VALUES($new_set,'деталь1'), ($new_set,'деталь2')
UNLOCK TABLES


Выборка всех элементов множества, в которое входит данный элемент осуществляется
в итоге всегда в фиксированое количество опеаций - две. Например дла "деталь1"

SELECT p_set as s FROM crosses WHERE p_key='деталь1'

SELECT p_key FROM crosses WHERE p_set=$s


P.S
можно и одним запросом...Но так нагляднее

Комментариев нет: