Доказательная алгоритмика. Глава 5

начало http://www.proza.ru/2015/07/16/1738
назад http://www.proza.ru/2015/07/21/1600

Доказательная алгоритмика

Глава 5

Как теперь понятно, основной тип объекта, который даёт нам реально программистские задачи – это массив (или список, то есть динамический массив) (И именно с такими объектами работает всем известный язык SQL) Но до сих пор мы работали только с 1-мерными массивами. А поэтому узнали, какой смысл имеют только 2 ключевых слова языка SQL – WHERE (то есть оператор отбора по условию)(пример – задача 5) и Order By (оператор упорядочивания, для которого также важны слова ASC (а порядке возрастания), DESC (в порядке убывания))(пример – задача 7),  также агрегатную функцию MIN (пример – задача 4)(аналогичным образом может быть реализована и агрегатная функция MAX. Агрегатные же функции  SUM, AVG и СOUNT требуют реализации иных алгоритмов.)
Если мы выйдем на работу с массивами хотя бы 2-х измерений, то нам сразу станет доступно, что имеется в виду под ключевым словом GROUP BY, а также многочисленные операторы соединения массивов.(INNER JOIN,  LEFT OUTER JOIN, RIGHT OUTER JOIN, FULL OUTER JOIN, CROSS JOIN)

Но сначала разберем (на примере алгоритма) смысл ключевого слово GROUP BY.
В SQL оно применяется для изменения алгоритма вычисления агрегатных функций, а именно в операторах вида SELECT col, agr(col) FROM A GROUP BY col (где agr – некоторая агрегатная функция) Кстати, отсюда видно, что ключевое слово GROUP BY работает и для 1-мерных массивов. Поэтому начнём с решения 1-мерной задачи и притом пока не содержащей вычисления агрегатной функции.
Задача 10:
Построить список c подмножеств a(i) множества а, значения элементов которых равны друг другу. (ключевое слово GROUP BY без вычисления агрегатной функции)

Предформальное описание
1.Список c индексов начальных элементов подмножеств a(k) множества а, значения элементов которых равны друг другу, получится при обходе списка b по i=1..count(b)
2.Список b получится как упорядоченный по возрастанию список а (см. алгоритм задачи 7)
3.Элемент с(k) списка с получится как индекс элемента b(i), удовлетворяющего предикату f(k)
(отмена)4.Предикат f(k) получится как b(i)>bc
5.Значение bc (состояние k) получится как значение элемента b(i), удовлетворяющего предикату f(k)
6.см. 4

Формальное описание
2)b=sort(a,up)
1)for i=1 to count(b) do
6)if b(i)>bc then
3)add(c,i)
5)bc=b(i)
Endif

Рис.16. Алгоритм для задачи 10

Понятно, что теперь можно пройтись по списку с и вычислить на нём всё,что нужно (любую агрегатную функцию) Составление этого подалгоритма предоставляю читателю.

Теперь наступила очередь работы с 2-мя массивами. Начнём с ключевого слова INNER JOIN (внутреннее соединение) (оператор SELECT A.col1, B.col2 FROM A INNER JOIN B ON A.col2 = B.col1)
Задача 11:
Построить список С, содержащий в каждом своём элементе в 1-ой колонке значения из колонки col1  списка А, во 2-ой колонке – значения из колонки col2 списка В, взятые из тех элементов А и В, для которых выполняется условие  A.col2 = B.col1 (то есть значение из колонки col2 списка А равно значению из колонки col1 списка В)

Предформальное описание:
1.Список С получится при обходе всех сочетаний элемента A(i)  списка А c элементом B(j) списка B
2.Элемент списка С получится как сочетание значения колонки col1 элемента A(i)  и значения колонки col2 элемента B(j), удовлетворяющих предикату f(i,j)
3.Предикат f(i,j) получится как A(i,’col2’)=B(j,’col1’)

Формальное описание
1)for i=1 to count(A) do
1)for j=1 to count(B) do
3)if A(i,’col2’)=B(j,’col1’) then
2)add(C,A(i,’col1’),B(j,’col2’))

Рис.17. Алгоритм для задачи 11.

В этом алгоритме, как видим, есть новый нюанс: в в 1-ом предложении предформального описания объявлен цикл в цикле. Именно это и есть способ получить все сочетания элемента A(i)  списка А c элементом B(j) списка B.
Но тут возникает вопрос: а что если в каком-то списке (например, А)  будет несколько элементов с одинаковыми значениями колонки col1 (а тем более, если при этом такое же будет и в другом списке) Ведь тогда каждое равное будет сочетаться с каждым равным, а потому один и тот же элемент списка (и того и другого) войдёт в результирующий список по нескольку раз, что не есть корректно.
Остаётся в итоге потребовать, что значения колонок, по которым происходит сопоставление элементов списка, были уникальными.(и такими 100%-но являются ключевые колонки) Но что-то я в учебниках по SQL такого требования нигде не встречал. И даже наоборот, иногда приводятся примеры, в которых сопоставление элементов списков происходит по колонке, в которой допустима неуникальность значений.

Следующее ключевое слово - LEFT JOIN (в некоторых диалектах LEFT OUTER JOIN) (левое внешнее соединение) (оператор SELECT A.col1, B.col2 FROM A LEFT OUTER JOIN B ON A.col2 = B.col1)
Задача 12:
Построить список С, содержащий в каждом своём элементе в 1-ой колонке значения из колонки col1  списка А, во 2-ой колонке – значения из колонки col2 списка В, взятые из всех элементов А и тех элементов В, для которых выполняется условие  A.col2 = B.col1 (то есть значение из колонки col2 списка А равно значению из колонки col1 списка В)

Предформальное описание
1.Список С получится при обходе всех сочетаний элемента A(i)  списка А c элементом B(j) списка B
2.Значение элемента списка С(i,j) получится как сочетание значения колонки1 и значения колонки2.
3.Элемент списка С(i,j)  получится как новый элемент списка С
4.Значение колонки 1 элемента списка С(i,j)   получится как значение колонки col1 элемента A(i) 
5.Значение колонки 2 элемента списка С(i,j)   получится как значения колонки col2 элемента B(j), удовлетворяющего предикату f(i,j)
6.Предикат f(i,j) получится как A(i,’col2’)=B(j,’col1’)

Формальное описание
1)for i=1 to count(A) do
1)for j=1 to count(B) do
3)add(C) (добавление нового, но пустого (по значению) элемента списка С)
4)C(‘1’)=A(i,’col1’)
6)if A(i,’col2’)=B(j,’col1’) then
5)C(‘2’)= B(j,’col2’)(А6-)
endfor

Рис.18. Алгоритм для задачи 12.

Следующее ключевое слово - RIGHT JOIN (в некоторых диалектах - RIGHT OUTER JOIN)
Задача 13:
Построить список С, содержащий в каждом своём элементе в 1-ой колонке значения из колонки col1  списка А, во 2-ой колонке – значения из колонки col2 списка В, взятые из тех элементов А, для которых выполняется условие  A.col2 = B.col1 (то есть значение из колонки col2 списка А равно значению из колонки col1 списка В)  и всех элементов В/ (оператор SELECT A.col1, B.col2 FROM A RIGHT OUTER JOIN B ON A.col2 = B.col1)

Предформальное описание
1.Список С получится при обходе всех сочетаний элемента A(i)  списка А c элементом B(j) списка B
2.Значение элемента списка С(i,j) получится как сочетание значения колонки1 и значения колонки2.
3.Элемент списка С(i,j)  получится как новый элемент списка С
4.Значение колонки 1 элемента списка С(i,j)   получится как значение колонки col1 элемента A(i), удовлетворяющего предикату f(i,j)
5.Предикат f(i,j) получится как A(i,’col2’)=B(j,’col1’)
6.Значение колонки 2 элемента списка С(i,j)   получится как значения колонки col2 элемента B(j)

Формальное описание
1)for i=1 to count(A) do
1)for j=1 to count(B) do
3)add(C) (добавление нового, но пустого (по значению) элемента списка С)
4)C(‘2’)=B(i,’col2’)
6)if A(i,’col2’)=B(j,’col1’) then
5)C(‘1’)= A(i,’col1’)
endfor

Рис.19. Алгоритм для задачи 13.

Остаётся реализовать только ключевые слова FULL OUTER JOIN и CROSS JOIN.
Задача 13:
Построить список С, содержащий в каждом своём элементе в 1-ой колонке значения из колонки col1  списка А, во 2-ой колонке – значения из колонки col2 списка В, взятые из тех элементов А, для которых выполняется условие  A.col2 = B.col1 (то есть значение из колонки col2 списка А равно значению из колонки col1 списка В)  и всех элементов В. (оператор SELECT A.col1, B.col2 FROM A FULL JOIN B ON A.col2 = B.col1)

Приведу только формальное описание (предформальное описание оставляю читателю):
1)for i=1 to count(A) do
1)for j=1 to count(B) do
3)add(C) (добавление нового, но пустого (по значению) элемента списка С)
C(‘1’)=А(i,’col1’)
4)C(‘2’)=B(i,’col2’)
6)if A(i,’col2’)=B(j,’col1’) then
5)C(‘1’)= A(i,’col1’)
C(‘2’)= B(j,’col2’)

Рис.20. Алгоритм для задачи 14.

Ну а ключевое слово CROSS JOIN – это совсем просто. (так называемое декартово произведение множеств. С этого и надо было начинать, как наиболее простой задачи)
Задача 14:
Построить список С, содержащий в каждом своём элементе в 1-ой колонке значения из колонки col1  списка А, во 2-ой колонке – значения из колонки col2 списка В при произвольном сочетании элементов списков А и В.(оператор SELECT A.col1, B.col2 FROM A CROSS JOIN B)

Формальное описание
1)for i=1 to count(A) do
1)for j=1 to count(B) do
2)add(C,A(i,’col1’),B(j,’col2’))

Рис.21. Алгоритм для задачи 14.

вперёд http://www.proza.ru/2015/07/23/1468