Предисловие

Один из приемов оптимизации запросов - замена соединения на объединение. Например, в СУБД Postgres полное соединение может вызвать тормоза. Тем не менее, не будем обсуждать преимущества и недостатки такого приема - применение зависит от конкретной ситуации. Проблема в том, что не всегда очевидно, когда можно выполнить такое преобразование без изменения результата запроса. Работать на авось, заметать грязь под ковер - не наши методы )). Укажем условия, когда два запроса будут эквивалентны, то есть результаты запросов будут совпадать для всех наборов данных - замена будет возможна. Доказательство теоремы будет проведено методом математической индукции для множеств конечной меры. Алгоритмы полного соединения, объединения, группировки хотя и имеют машинную реализацию, но прозрачны для пользователя. Поэтому метод математической индукции вполне уместен. Думаю, аналогичный результат известен в курсе реляционной алгебры, но ссылку найти не могу. Буду благодарен, если кто покажет. Если найдете ошибку в доказательстве — буду благодарен вдвойне.

Определим переменные

ТаблицаА — источник данных (таблица), содержит колонки КлючА, ПолеА.

ТаблицаБ — источник данных (таблица), содержит колонки КлючБ, ПолеБ.

Запрос1 = Новый Запрос;
Запрос1.Текст =
"ВЫБРАТЬ
ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) КАК Ключ,
ТаблицаА.КлючА,
ТаблицаА.ПолеА,
ТаблицаБ.КлючБ,
ТаблицаБ.ПолеБ
ИЗ
ТаблицаА КАК ТаблицаА
ПОЛНОЕ СОЕДИНЕНИЕ ТаблицаБ КАК ТаблицаБ
ПО ТаблицаА.КлючА = ТаблицаБ.КлючБ";

////////////////////////////////////////////////////////////////////////

Запрос2 = Новый Запрос;
Запрос2.Текст =
"ВЫБРАТЬ
ВложеннаяТаблица2.Ключ,
МАКСИМУМ(ВложеннаяТаблица2.КлючА) КАК КлючА,
МАКСИМУМ(ВложеннаяТаблица2.ПолеА) КАК ПолеА,
МАКСИМУМ(ВложеннаяТаблица2.КлючБ) КАК КлючБ,
МАКСИМУМ(ВложеннаяТаблица2.ПолеБ) КАК ПолеБ
ИЗ
(ВЫБРАТЬ
ТаблицаА.КлючА КАК Ключ,
ТаблицаА.КлючА КАК КлючА,
NULL КАК КлючБ,
ТаблицаА.ПолеА КАК ПолеА,
NULL КАК ПолеБ
ИЗ
ТаблицаА КАК ТаблицаА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.ПолеБ
ИЗ
ТаблицаБ КАК ТаблицаБ) КАК ВложеннаяТаблица2

СГРУППИРОВАТЬ ПО
ВложеннаяТаблица2.Ключ";

Теорема

Пусть выполняются условия:

• ТаблицаА не содержит повторений по полю КлючА
• ТаблицаА не содержит в поле КлючА значений NULL
• ТаблицаБ не содержит повторений по полю КлючБ
• ТаблицаБ не содержит в поле КлючБ значений NULL

Тогда Запрос1 эквивалентен Запрос2. Результаты запросов совпадают для всех наборов данных.

Примечание 1

Колонки КлючА, ПолеА, КлючБ, ПолеБ могут быть ссылочного или примитивного типа. Для ключевых полей исключены типы по которым невозможна сортировка или соединение - например строка неограниченной длины.

Примечание 2

Если поля — числовые, то можно использовать агрегатную функцию суммы, вместо Null для пустых полей таких столбцов устанавливать 0. При этом надо помнить, что агрегатные функции Сумма, Максимум «игнорируют» поля типа Null, возвращая результат так, как будто полей Null нет, хотя (Число+Null ) IS Null.

Примечание 3

Колонки могут сами состоять из нескольких колонок, то есть теорема распространяется на источники данных с многими колонками: Ключ1А, Ключ2А, … КлючXА, Поле1А, Поле2А, … ПолеYА.

Примечание 4

Выражение ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) будет равно либо ТаблицаА.КлючА, при ТаблицаБ.КлючБ IS NULL, либо ТаблицаБ.КлючБ, при ТаблицаА.КлючА IS NULL, либо ТаблицаА.КлючА = ТаблицаБ.КлючБ - поскольку полное соединение происходит по условию равенства. То есть выражение ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) симметрично и совпадает с результатом группировки.

Следствие 1

Пример эквивалентных запросов для внутреннего соединения.

Запрос3 = Новый Запрос;
Запрос3.Текст =
"ВЫБРАТЬ
ЕСТЬNULL(ТаблицаА.КлючА, ТаблицаБ.КлючБ) КАК Ключ,
ТаблицаА.КлючА,
ТаблицаА.ПолеА,
ТаблицаБ.КлючБ,
ТаблицаБ.ПолеБ
ИЗ
ТаблицаА КАК ТаблицаА
ВНУТРЕННЕЕ СОЕДИНЕНИЕ ТаблицаБ КАК ТаблицаБ
ПО ТаблицаА.КлючА = ТаблицаБ.КлючБ";

////////////////////////////////////////////////////////////////////////

Запрос4 = Новый Запрос;
Запрос4.Текст =
"ВЫБРАТЬ
ВложеннаяТаблица2.Ключ,
МАКСИМУМ(ВложеннаяТаблица2.КлючА) КАК КлючА,
МАКСИМУМ(ВложеннаяТаблица2.ПолеА) КАК ПолеА,
МАКСИМУМ(ВложеннаяТаблица2.КлючБ) КАК КлючБ,
МАКСИМУМ(ВложеннаяТаблица2.ПолеБ) КАК ПолеБ
ИЗ
(ВЫБРАТЬ
ТаблицаА.КлючА КАК Ключ,
ТаблицаА.КлючА КАК КлючА,
NULL КАК КлючБ,
ТаблицаА.ПолеА КАК ПолеА,
NULL КАК ПолеБ,
1 КАК ОграничительА,
0 КАК ОграничительБ
ИЗ
ТаблицаА КАК ТаблицаА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.КлючБ,
NULL,
ТаблицаБ.ПолеБ,
0,
1
ИЗ
ТаблицаБ КАК ТаблицаБ) КАК ВложеннаяТаблица2

СГРУППИРОВАТЬ ПО
ВложеннаяТаблица2.Ключ

ИМЕЮЩИЕ
СУММА(ВложеннаяТаблица2.ОграничительА) > 0
И СУММА(ВложеннаяТаблица2.ОграничительБ) > 0";

КОНТРПример 1.

Воспроизведем ситуацию, когда условия теоремы НЕ выполняются — результаты запросов не совпадают.

ТаблицаА содержит две строки (Ключ1А, Поле1А), (Ключ1А, Поле2А)

ТаблицаБ содержит две строки (Ключ1Б, Поле1Б), (Ключ2Б, Поле2Б)

ВЫБРАТЬ
"Ключ1А" КАК КлючА,
"Поле1А" КАК ПолеА
ПОМЕСТИТЬ ТаблицаА

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
"Ключ1А",
"Поле2А"
;
///////////////////////////////////////////////////////////

ВЫБРАТЬ
"Ключ1Б" КАК КлючБ,
"Поле1Б" КАК ПолеБ
ПОМЕСТИТЬ ТаблицаБ

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
"Ключ2Б",
"Поле2Б"

 

Результат Запрос1

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле1А	NULL	NULL
Ключ1А	Ключ1А	Поле2А	NULL	NULL
Ключ1Б	NULL	NULL	Ключ1Б	Поле1Б
Ключ2Б	NULL	NULL	Ключ2Б	Поле2Б

 

Результат Запрос2

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле2А	NULL	NULL
Ключ1Б	NULL	NULL	Ключ1Б	Поле1Б
Ключ2Б	NULL	NULL	Ключ2Б	Поле2Б

 

КОНТРПример 2

Воспроизведем ситуацию, когда условия теоремы НЕ выполняются — результаты запросов не совпадают.

ТаблицаА содержит одну строку (NULL, Поле1А)

ТаблицаБ содержит одну строку (NULL, Поле1Б)

ВЫБРАТЬ
NULL КАК КлючА,
"Поле1А" КАК ПолеА
ПОМЕСТИТЬ ТаблицаА
;
///////////////////////////////////////////////////////

ВЫБРАТЬ
NULL КАК КлючБ,
"Поле1Б" КАК ПолеБ
ПОМЕСТИТЬ ТаблицаБ

 

Результат Запрос1

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
NULL	NULL	Поле1А	NULL	NULL
NULL	NULL	NULL	NULL	Поле1Б

 

Результат Запрос2

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
NULL	NULL	Поле1А	NULL	Поле1Б

 

Доказательство будем проводить методом математической индукции. На первом шаге проверим утверждение на минимальном числе строк таблиц ТаблицаА, ТаблицаБ. Второй шаг — предположим, что утверждение выполняется для таблиц ТаблицаА, ТаблицаБ в которых содержится X и Y строк соответственно. Третий шаг — используя предположение шага 2 докажем, что утверждение выполняется для таблиц ТаблицаА, ТаблицаБ в которых содержится (X+1) и Y строк соответственно. В случае, если условия симметричны относительно ТаблицаА, ТаблицаБ, на этом доказательство заканчивается. Это хорошо изученный, классический, но трудный для понимания метод.

Шаг первый.

Следует учитывать, что рассматриваемые операции симметричны относительно выборок, поэтому количество вариантов можно сократить.

Вариант 1.

Ключ1А <> Ключ1Б, Ключ2А <> Ключ2Б, Ключ1А <> Ключ2А, Ключ1Б <> Ключ2Б

ТаблицаА, содержит две строки (Ключ1А, Поле1А), (Ключ2А, Поле2А),

ТаблицаБ, содержит две строки (Ключ1Б, Поле1Б), (Ключ2Б, Поле2Б).

 

Результаты Запрос1, Запрос2 совпадают

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле1А	NULL	NULL
Ключ1Б	NULL	NULL	Ключ1Б	Поле1Б
Ключ2А	Ключ2А	Поле2А	NULL	NULL
Ключ2Б	NULL	NULL	Ключ2Б	Поле2Б

Вариант 2.

Ключ1А = Ключ1Б, Ключ2А <> Ключ2Б, Ключ1А <> Ключ2А, Ключ1Б <> Ключ2Б

ТаблицаА, содержит две строки (Ключ1А, Поле1А), (Ключ2А, Поле2А),

ТаблицаБ, содержит две строки (Ключ1А, Поле1Б), (Ключ2Б, Поле2Б).

Результаты Запрос1, Запрос2 совпадают

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле1А	Ключ1А	Поле1Б
Ключ2А	Ключ2А	Поле2А	NULL	NULL
Ключ2Б	NULL	NULL	Ключ2Б	Поле2Б

Мы показали, что запросы дают одинаковый результат при выполнении условий теоремы, если таблицы содержат 2 записи. Случай, когда записей меньше двух — рассмотреть несложно, будем этот случай считать очевидным.

Шаг второй.

Пусть теорема выполняется для таблиц ТаблицаА(X записей), ТаблицаБ (Y записей). ТаблицаА не содержит повторений по полю КлючА и ТаблицаБ не содержит повторений по полю КлючБ. Запрос1 и Запрос2 эквивалентны, то есть дают одинаковый результат на всех наборах данных.

 

ТаблицаА

КлючА	ПолеА
Ключ1А	Поле1А
…	...
КлючXА	ПолеXА

 

ТаблицаБ

КлючБ	ПолеБ
Ключ1Б	Поле1Б
…	...
КлючYБ	ПолеYБ

 

Поскольку для выборки порядок строк не важен, мысленно переместим строки внутри выборки так, чтобы образовалось три группы. При этом первые W значений ключевого поля совпадают: Ключ1А = Ключ1Б, … , КлючWА = КлючWБ. Для остальных значений ключевые поля — отличаются.

 

Результаты Запрос1, Запрос2 совпадают:

 

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле1А	Ключ1Б	Поле1Б
…	…	…	…	…
КлючWА	КлючWА	ПолеWА	КлючWБ	ПолеWБ
Ключ(W+1)А	Ключ(W+1)А	Поле(W+1)А	NULL	NULL
…	…	…	…	…
КлючXА	КлючXА	ПолеXА	NULL	NULL
Ключ(W+1)Б	NULL	NULL	Ключ(W+1)Б	Поле(W+1)Б
…	…	…	…	…
КлючYБ	NULL	NULL	КлючYБ	ПолеYБ

Шаг третий.

Добавим в ТаблицаА еще одну строку Ключ(X+1)А, Значение(X+1)А. По условиям теоремы, ТаблицаА не содержит повторений по полю КлючА, то есть все значения поля различные.

Вариант 1.

Среди значений поля КлючБ нет ни одного, равного Ключ(X+1)А.

При расчете результата Запрос1 (Полное соединение) добавится еще одна строка.

 

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле1А	Ключ1Б	Поле1Б
…	…	…	…	…
КлючWА	КлючWА	ПолеWА	КлючWБ	ПолеWБ
Ключ(W+1)А	Ключ(W+1)А	Поле(W+1)А	NULL	NULL
…	…	…	…	…
КлючXА	КлючXА	ПолеXА	NULL	NULL
Ключ(X+1)А	Ключ(X+1)А	Поле(X+1)А	NULL	NULL
Ключ(W+1)Б	NULL	NULL	Ключ(W+1)Б	Поле(W+1)Б
…	…	…	…	…
КлючYБ	NULL	NULL	КлючYБ	ПолеYБ

При расчете результата Запрос2 — строка добавится в ВложеннаяТаблица2 как Объединение, при группировке эта строка не сгруппируется ни с одной строкой по условиям выше — тоже будет дополнительная строка. Результаты Запрос1, Запрос2 совпадают.

Вариант 2.

В силу требований теоремы значения поля КлючБ различны между собою. Поэтому не может быть случая, когда несколько полей равно Ключ(X+1)А. Однако, одно из значений поля КлючБ может быть равно Ключ(X+1)А. Совпадают (W+1) значений ключевого поля. Запишем результат в таблицу, проверим Запрос1, Запрос2 опираясь на результаты второго шага.

Ключ	КлючА	ПолеА	КлючБ	ПолеБ
Ключ1А	Ключ1А	Поле1А	Ключ1Б	Поле1Б
…	…	…	…	…
КлючWА	КлючWА	ПолеWА	КлючWБ	ПолеWБ
Ключ(W+1)А	Ключ(W+1)А	Поле(W+1)А	Ключ(W+1)Б	Поле(W+1)Б
Ключ(W+2)А	Ключ(W+2)А	Поле(W+2)А	NULL	NULL
…	…	…	…	…
Ключ(X+1)А	Ключ(X+1)А	Поле(X+1)А	NULL	NULL
Ключ(W+2)Б	NULL	NULL	Ключ(W+2)Б	Поле(W+2)Б
…	…	…	…	…
КлючYБ	NULL	NULL	КлючYБ	ПолеYБ

Результаты Запрос1, Запрос2 совпадают. Что и требовалось доказать.

Надеюсь, что эта теорема позволит нам избежать ошибок при замене левых соединений на объединение и значит — сделать программирование лучше.