gifts2017

Запрос – комбинатор

Опубликовал Сергей (ildarovich) в раздел Программирование - Практика программирования

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

Часть 1. 

Для начала рассмотрим более абстрактную задачу.

Имеется таблица с колонками: свойство и значение. Каждое свойство  в этой таблице может принимать одно или несколько значений. Требуется построить выходную таблицу с колонками:вариант, свойство, значение, содержащую все варианты комбинаций значений свойств. Например, если исходная таблица имеет вид:

 Свойство Значение 
 Цвет волос  блондинка
 Цвет волос  брюнетка
 Интеллект  глупая
 Интеллект  умная

То на выходе должна получиться таблица:

Вариант  Свойство  Значение 
 0  Цвет волос  блондинка
 0  Интеллект  глупая
 1  Цвет волос  блондинка
 1   Интеллект  умная
 2  Цвет волос  брюнетка
 2   Интеллект  глупая
 3  Цвет волос  брюнетка
 3   Интеллект  умная

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

Нумерация делается с помощью такого запроса:

	
ВЫБРАТЬ
	ВЫРАЗИТЬ(КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Слева.Свойство) / 2 КАК ЧИСЛО(10, 0)) КАК НомерПары,
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ Слева.Свойство) КАК Измерение,
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ВЫБОР
			КОГДА Слева.Свойство = Дано.Свойство
				ТОГДА Слева.Значение
		КОНЕЦ) КАК Мощность,
	КОЛИЧЕСТВО(РАЗЛИЧНЫЕ ВЫБОР
			КОГДА Слева.Свойство = Дано.Свойство
					И Слева.Значение <= Дано.Значение
				ТОГДА Слева.Значение
		КОНЕЦ) - 1 КАК Вариант,
	Дано.Свойство,
	Дано.Значение
ПОМЕСТИТЬ Цепь_1
ИЗ
	Дано КАК Дано
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Дано КАК Слева
		ПО (Слева.Свойство <= Дано.Свойство)

СГРУППИРОВАТЬ ПО
	Дано.Свойство,
	Дано.Значение


Перемножение делается с помощью такого запроса:

	
ВЫБРАТЬ
	ВЫРАЗИТЬ(Инь.НомерПары / 2 КАК ЧИСЛО(10, 0)) КАК НомерПары,
	Инь.НомерПары КАК Измерение,
	Инь.Мощность * ЕСТЬNULL(Янь.Мощность, 1) КАК Мощность,
	ЕСТЬNULL(ВЫБОР
			КОГДА Инь.Измерение < Янь.Измерение
				ТОГДА Инь.Вариант + Янь.Вариант * Инь.Мощность
			ИНАЧЕ Янь.Вариант + Инь.Вариант * Янь.Мощность
		КОНЕЦ, Инь.Вариант) КАК Вариант,
	Инь.Свойство,
	Инь.Значение
ПОМЕСТИТЬ Цепь_2
ИЗ
	Цепь_1 КАК Инь
		ЛЕВОЕ СОЕДИНЕНИЕ (ВЫБРАТЬ РАЗЛИЧНЫЕ
			Цепь_1.НомерПары КАК НомерПары,
			Цепь_1.Измерение КАК Измерение,
			Цепь_1.Мощность КАК Мощность,
			Цепь_1.Вариант КАК Вариант
		ИЗ
			Цепь_1 КАК Цепь_1) КАК Янь
		ПО Инь.НомерПары = Янь.НомерПары
			И Инь.Измерение <> Янь.Измерение



Последний запрос нужно повторить ]Log2(N)[ раз  в зависимости от общего количества свойств N.

Часть 2.

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

Для определенности будем считать, что спецификации задаются в справочнике «СпецификацииНоменклатуры» конфигурации «1С:Бухгалтерия предприятия» и что они имеют не более трех уровней. Тогда запрос, показывающий количество сырья, необходимое для выпуска одной единицы продукции будет иметь вид:

	
ВЫБРАТЬ
	ЕСТЬNULL(Уровень3.Номенклатура, ЕСТЬNULL(Уровень2.Номенклатура, Уровень1.Номенклатура)) КАК Номенклатура,
	СУММА(Уровень1.Количество * ЕСТЬNULL(Уровень2.Количество, 1) * ЕСТЬNULL(Уровень3.Количество, 1) / Уровень1.Ссылка.Количество / ЕСТЬNULL(Уровень2.Ссылка.Количество, 1) / ЕСТЬNULL(Уровень3.Ссылка.Количество, 1)) КАК Количество
ИЗ
	Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Уровень1
		ЛЕВОЕ СОЕДИНЕНИЕ Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Уровень2
			ЛЕВОЕ СОЕДИНЕНИЕ Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Уровень3
			ПО Уровень2.Номенклатура = Уровень3.Ссылка.Владелец
		ПО Уровень1.Номенклатура = Уровень2.Ссылка.Владелец
ГДЕ
	Уровень1.Ссылка.Владелец = &Номенклатура
СГРУППИРОВАТЬ ПО
	ЕСТЬNULL(Уровень3.Номенклатура, ЕСТЬNULL(Уровень2.Номенклатура, Уровень1.Номенклатура))


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

Для этого для начала построим таблицу с колонками: номенклатура, спецификация, в которой одной номенклатуре (свойству) может соответствовать несколько спецификаций (значений). Это можно сделать с помощью следующего запроса:

	
ВЫБРАТЬ
	Уровень1.Ссылка.Владелец КАК Продукт1,
	Уровень1.Ссылка КАК Рецепт1,
	Уровень2.Ссылка.Владелец КАК Продукт2,
	Уровень2.Ссылка КАК Рецепт2,
	Уровень3.Ссылка.Владелец КАК Продукт3,
	Уровень3.Ссылка КАК Рецепт3
ПОМЕСТИТЬ НашеВсе
ИЗ
	Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Уровень1
		ЛЕВОЕ СОЕДИНЕНИЕ Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Уровень2
			ЛЕВОЕ СОЕДИНЕНИЕ Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Уровень3
			ПО Уровень2.Номенклатура = Уровень3.Ссылка.Владелец
		ПО Уровень1.Номенклатура = Уровень2.Ссылка.Владелец
ГДЕ
	Уровень1.Ссылка.Владелец = &Номенклатура
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	НашеВсе.Продукт1 КАК Свойство,
	НашеВсе.Рецепт1 КАК Значение
ПОМЕСТИТЬ Дано
ИЗ
	НашеВсе КАК НашеВсе

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	НашеВсе.Продукт2,
	НашеВсе.Рецепт2
ИЗ
	НашеВсе КАК НашеВсе

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	НашеВсе.Продукт3,
	НашеВсе.Рецепт3
ИЗ
	НашеВсе КАК НашеВсе


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

Теперь соединим таблицу вариантов и содержание спецификаций:

	
ВЫБРАТЬ
	Вариации.Вариант,
	Состав.Ссылка.Владелец КАК Продукт,
	Состав.Ссылка.Количество КАК Стало,
	Состав.Номенклатура КАК Сырье,
	Состав.Количество КАК Было
ПОМЕСТИТЬ Рецепты
ИЗ
	Вариации КАК Вариации
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Справочник.СпецификацииНоменклатуры.ИсходныеКомплектующие КАК Состав
		ПО Вариации.Свойство = Состав.Ссылка.Владелец
			И Вариации.Значение = Состав.Ссылка


А затем в итоговом запросе добавим группировку и условие соединения по номеру варианта:

	
ВЫБРАТЬ
	ЕСТЬNULL(Уровень3.Сырье, ЕСТЬNULL(Уровень2.Сырье, Уровень1.Сырье)) КАК Номенклатура,
	СУММА(Уровень1.Было * ЕСТЬNULL(Уровень2.Было, 1) * ЕСТЬNULL(Уровень3.Было, 1) / Уровень1.Стало / ЕСТЬNULL(Уровень2.Стало, 1) / ЕСТЬNULL(Уровень3.Стало, 1)) КАК Количество,
	Уровень1.Вариант КАК Вариант
ИЗ
	Рецепты КАК Уровень1
		ЛЕВОЕ СОЕДИНЕНИЕ Рецепты КАК Уровень2
			ЛЕВОЕ СОЕДИНЕНИЕ Рецепты КАК Уровень3
			ПО Уровень2.Сырье = Уровень3.Продукт
				И Уровень2.Вариант = Уровень3.Вариант
		ПО Уровень1.Сырье = Уровень2.Продукт
			И Уровень1.Вариант = Уровень2.Вариант
ГДЕ
	Уровень1.Продукт = &Номенклатура

СГРУППИРОВАТЬ ПО
	Уровень1.Вариант,
	ЕСТЬNULL(Уровень3.Сырье, ЕСТЬNULL(Уровень2.Сырье, Уровень1.Сырье))

УПОРЯДОЧИТЬ ПО
	Вариант,
	Номенклатура

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

Вместо заключения

Существует мнение, что хитроумных запросов и алгоритмов можно вообще избегать, выбирая на этапе проектирования правильные СУБД или правильные структуры таблиц базы данных. Данный пример, кажется, работает не в пользу этого мнения. Ну и хорошо, иначе составление запросов было бы слишком скучным делом.

Скачать файлы

Наименование Файл Версия Размер Кол. Скачив.
Отчет "Комбинатор"
.erf 10,14Kb
07.08.14
10
.erf 10,14Kb 10 Скачать
Отчет "Варианты спецификаций для БП"
.erf 10,82Kb
07.08.14
9
.erf 10,82Kb 9 Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Марина Чирина (chmv) 08.08.14 14:58
2. Яков Коган (Yashazz) 08.08.14 18:28
Круто. Правда, нумеровать предпочитаю с помощью СКД. Да и вообще некоторые функции СКД уже существенно облегчили жизнь, например, по нарастающим итогам.
Ильдарович, а не было мысли поиграть с объектной моделью запросов 8.3.5, попробовать на ней все композитные запросы (например, замыкания)?
3. Сергей (ildarovich) 11.08.14 12:04
(2) Yashazz,
1) СКД хорош на своем месте - для постобработки результатов запроса. Все же это черный ящик. Когда я писал запрос для отчета "Неоплаченные долги при распределении оплаты по правилу ФИФО одним запросом и намного быстрее, чем Вы думали", столкнулся с тем, что первый вариант запроса в СКД работал невообразимо дольше, чем в консоли. Разработчик подтвердил ошибку и обещал исправить, но исправил или нет - не проверял, поскольку нашел обходной путь - другой вариант записи запроса. В СКД меня сейчас интересует возможность их каскадного соединения: когда в запросе что-то делается, затем делается постобработка в СКД и результат передается в следующую СКД для следующего этапа обработки. Вот этот путь кажется перспективным, поскольку позволяет быстро сделать вне запроса вещи, которые сложны для чисто запросной техники. Тут есть тонкое место - таблица значений вроде бы вводится в запрос по записям отдельными инсертами и это может узким местом. Но пока не выделил задачу, на которой можно было попробовать этот подход.
2) Относительно объектной модели запроса - мысль интересная. Но есть сомнения. Результатом будет программа (функция), которая строит программу (запрос). Пусть и более четко, но, кажется, еще менее наглядно. Здесь я бы подождал, пока эту технику начнут использовать в типовых. При наличии времени я бы стал пробовать придумать (несколько уже придумал) и использовать инструкции препроцессора в запросе, сохраняющие его читаемость. Поскольку у меня уже есть функция НовыйЗапрос, которой я интенсивно пользуюсь, я бы внес в нее и препроцессинг текста запроса.
4. Юрий Пермитин (YPermitin) 11.08.14 13:37
5. Р С (Dach) 13.08.14 19:04
Декартово произведение. Если количество свойств заранее известно, то можно решить такую задачу проще. Разбиваем таблицу на столько виртуальных таблиц, сколько различных свойств. Далее левое соединение первой ВТ со всеми остальными ВТ. В итоге получим из таблицы вида:

цвет волос блондинка
цвет волос брюнетка
интеллект умная
интеллект глупая
размер груди большая
размер груди маленькая

таблицу вида:

цвет волос блондинка интеллект умная размер груди большая
цвет волос блондинка интеллект умная размер груди маленькая
цвет волос блондинка интеллект глупая размер груди большая
цвет волос блондинка интеллект глупая размер груди маленькая

и т.д.

Таким образом нечетная колонка - свойство, четная - значение
6. Сергей (ildarovich) 13.08.14 19:20
(5) Dach, все правильно, декартово произведение сразу дает все комбинации значений свойств.
Только в вашем примере колонка "свойство" во всех соединяемых таблицах - лишняя, так как каждое свойство будет храниться в отдельной таблице, естественно ее назвать также как свойство (зачем колонка, которая во всей таблице принимает одно и то же значение?). Так же как свойство можно назвать поля в итоговой таблице.
Но это очевидное решение не работает, когда свойства и значения заранее не определены. Тогда при вашем подходе придется анализировать состав свойств и набирать под эти свойства текст запроса. Метод и запрос получится громоздким. Я, в общем-то пробовал этот подход в задаче получения вариантов спецификаций - хотел просто с минимальными усилиями решить задачу. Но получилось очень длинно и коряво.
Описанный метод гораздо более универсален: работает с заранее неизвестным набором свойств.
7. Р С (Dach) 13.08.14 22:50
(6) ildarovich, а если попробовать вот такой алгоритм:

Динамически управлять текстом запроса в цикле, да-да в цикле, ничего тут страшного.

0. Таблицу свойств и значений помещаем в ВТ на сервере СУБД.
1. Выбрать различные свойства, выгрузить в массив.
2. Цикл по массиву, получаем имя свойства, выбираем в ВТ все строки, с отбором по свойству. Имя ВТ назначаем как имя свойства.
3. Еще один проход по массиву в цикле, на этот раз получаем на первом шаге первую ВТ и далее, на последующих проходах лефт джойн. Используем менеджер ВТ, разумеется, для доступа к ВТ.
4. На выходе получаем требуемое декартово произведение.
Solvolna; An@st@si; AlexSunS; +3 Ответить 1
8. Сергей (ildarovich) 14.08.14 10:56
(7) Dach, вполне можно так сделать - будет работать, но это самый неэффективный способ.
Если уж решили выбрать свойства в массив, то (как было предложено в (6)) в том же своем цикле без всяких временных таблиц постройте конкатенацией текст запроса, который сразу соединит все таблицы.
По сравнению с моим вариантом потом еще потребуется запросы, которые
1) пронумеруют варианты;
2) объединят значения из разных колонок в одну таблицу с тремя колонками.
Еще раз повторяю, я такой подход пробовал. Получается более громоздко.
Можете попробовать сами - посмотрим, что у вас получится.
Также при большом количестве вариантов в вашем подходе много времени уйдет на нумерацию вариантов.
В общем, считаю пока свой метод решения этой задачи самым гибким, компактным и быстрым.
9. Максим Кузнецов (Makushimo) 19.08.14 02:49
"Последний запрос нужно повторить ]Log2(N)[ раз в зависимости от общего количества свойств N"
Если свойств будет 10, то сколько раз нужно "повторить последний запрос" ?
10. Сергей (ildarovich) 19.08.14 10:41
(9) Makushimo, запрос нужно будет повторить четыре раза:
1) ]10 / 2[ = 5,
2) ]5 / 2[ = 3,
3) ]3 / 2[ = 2,
4) ]2 / 2[ = 1.
11. Сергей (Che) Коцюра (CheBurator) 27.08.14 18:58
12. Сергей (ildarovich) 20.09.14 13:27
Оказалось, что если добавить к исходной таблице вероятность принятия свойствами конкретных значений, то можно посчитать вероятности сочетаний значений свойств и решать таким образом задачи расчета вероятностей сложных событий. Об этом написано в статье "Расчет вероятностей запросом".
13. Ilya (i_volodin) 04.02.15 15:38
Здравствуйте, ildarovich Люблю "непонимать" Ваши статьи :). Есть одни вопрос, Вы конструируете запросы конкатенацией в основном, а я тут наткнулся на "СхемаЗапросов", не пробовали ли вы ее? мне кажется, что она была бы Вам полезна.
14. Сергей (ildarovich) 04.02.15 16:19
(13) Илья, рад услышаться. К "схеме запросов" пока присматриваюсь. Обратил внимание на нее сразу как она появилась. Переписывать на нее уже сделанное не буду, а в новых задачках попробую. Даже задачка есть - сравнение таблиц значений запросом - полным соединением. Обычная техника дала слишком длинный код. Как-нибудь перепишу на объектную модель.

С другой стороны, есть идея развить язык запросов, добавив туда инструкции препроцессора. Несколько уже придумал, но застопорился. Кажется, такой подход даст большую наглядность при программировании запросов. С такой точки зрения объектная модель запроса - лишний уровень абстракции, уводящий от сути задачи.
15. Сергей (ildarovich) 24.04.15 23:33
Еще одна задача, которая может быть решена данным методом: поиск чисел, формирующих нужную сумму. В публикации http://infostart.ru/public/350311/ задача решается внешними средствами (на Java). А здесь можно сделать одним запросом.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа