Определения, относящиеся к рекурсии
Обход дерева в ширину. При этом способе обхода непосредственные потомки обходятся слева направо, до того как производится переход к потомкам следующего уровня родства.
Рис. 16.5. Пример дерева
При обходе в ширину дерева, показанного на рис.16.5, узлы будут обходиться в следующем порядке: Корень-Потомок1-Потомок2-Потомок3-П1.1-П1.2-П1.3-П2.1-П2.3-П3.1-П3.2-П3.3.
Обход дерева в глубину. При этом способе обхода на каждом шаге производится переход к самому левому текущему потомку. При обходе в глубину дерева с рис.16.5 порядок обхода узлов будет следующим: Корень-Потомок1-П1.1-П1.2-П1.3-Потомок2-П2.1-П2.2-П2.3-Потомок3-П3.1-П3.2-П3.3.
Цикл в ориентированном графе. В теории графов ориентированный граф называется циклическим в том и только в том случае, когда хотя бы один узел графа одновременно является и предком, и потомком (т. е. для этого узла имеется и выходящая, и входящая дуги). В SQL:1999 узлами графа рекурсии являются строки, входящие в результат рекурсивного запроса, а дуги соответствуют способам обработки текущих строк, которые ведут к добавлению к результату новых строк. На рис.16.6 показан простейший пример ориентированного графа с циклом.
Рис. 16.6. Пример графа с циклом
Прямая рекурсия. По определению, некоторый элемент использует прямую рекурсию в том и только в том случае, когда он обращается сам к себе без посредников. Пример, приведенный на рис.16.6, демонстрирует (в графовой форме) прямую рекурсию. На рис.16.7 показан графовый пример непрямой рекурсии.
Рис. 16.7. Графовый пример непрямой рекурсии
Линейная рекурсия. При линейно рекурсивном вызове элемент прямо рекурсивно обращается сам к себе не более одного раза. В SQL:1999 в определении любой виртуальной таблицы с рекурсией допускается не более одной ссылки на саму себя (в разделе FROM и/или в подзапросах). На рис.16.8 показан графовый пример рекурсии, не являющейся линейной.
Монотонность. Монотонной прогрессией называется последовательность неубывающих или невозрастающих значений. Например, последовательность натуральных чисел {1, 2, ... , n, ...} является монотонной. В SQL:1999 свойство монотонности поддерживается в том смысле, что число строк результата рекурсивного запроса не уменьшается на каждом шаге рекурсии.
Взаимная рекурсия. Элементы A и B связаны отношением взаимной рекурсии, если A прямо или косвенно вызывает B, и B прямо или косвенно вызывает A. На рис.16.9 показан графовый пример взаимной рекурсии (элемент A вызывает элемент B через элемент C, а элемент B вызывает элемент A через элемент D).
Рис. 16.8. Графовый пример нелинейной рекурсии
Рис. 16.9. Графовый пример взаимной рекурсии
Отрицание. В контексте SQL отрицанием называется любое действие, приводящее к уменьшению числа строк в результате запроса. Свойствами отрицания обладают операции над (мульти)множествами EXCEPT и INTERSECT, спецификация DISTINCT, условие NOT EXISTS и т.д. В стандарте SQL не запрещается использование отрицания в рекурсивных запросах. Возможной проблемы нарушения монотонности удается избежать за счет того, что отрицание разрешается применять только к тем таблицам, которые являются полностью известными (или вычисленными) к моменту применения отрицания. В процессе вычисления таблицы применение к ней отрицания не допускается.
Начальный источник рекурсии. При выполнении рекурсивных вычислений обычно (хотя и не всегда) имеется некоторое начальное значение. В SQL этим начальным источником рекурсии является одна или несколько строк, удовлетворяющих некоторым начальным условиям. На основе этих строк в процессе рекурсивного вычисления производятся дополнительные строки, образующие окончательный результат.
Стратификация. В SQL рекурсивный запрос обычно состоит из "рекурсивной" и "нерекурсивной" частей. В процессе стратификации ("расслоения") запроса выполнение этих двух частей разделяется. В более сложных рекурсивных запросах может содержаться несколько рекурсивных частей и более одной нерекурсивной части. В этом случае в процессе стратификации будет обнаружено большее число слоев.
Семантика фиксированной точки. В контексте SQL:1999 семантика фиксированной точки означает, что решение о завершении рекурсивного запроса принимается тогда, когда становится невозможно добавить к результату какие-либо дополнительные строки.
- Введение в модель данных sql
- 1. Лекция: Язык баз данных sql: общее введение, типы данных и средства определения доменов Введение
- Краткая история языка sql
- Структура языка sql
- Типы данных sql
- Tочные числовые типы
- Истинно целые типы
- Точные типы, допускающие наличие дробной части
- Приближенные числовые типы
- Типы символьных строк
- Типы битовых строк
- Типы даты и времени
- Тип даты
- Типы времени
- Типы временной метки
- Типы времени и временной метки с временной зоной
- Типы временных интервалов
- Булевский тип
- Типы коллекций
- Типы массивов
- Типы мультимножеств
- Анонимные строчные типы
- Типы, определяемые пользователем
- Ссылочные типы
- Средства определения, изменения определения и отмены определения доменов
- Определение домена
- Примеры определений доменов
- Изменение определения домена
- Примеры изменения определения домена
- Отмена определения домена
- Неявные и явные преобразования типа или домена
- Неявные преобразования типов в sql
- Явные преобразования типов или доменов и оператор cast
- Заключение
- 2. Лекция: Язык баз данных sql: средства определения базовых таблиц и ограничений целостности
- Введение
- Средства определения, изменения и ликвидации базовых таблиц
- Определение базовой таблицы
- Определение столбца
- Значения столбца по умолчанию
- Ограничения целостности столбца
- Определение табличного ограничения
- Табличное ограничение первичного или возможного ключа
- Проверочное табличное ограничение
- Табличное ограничение внешнего ключа
- Разновидности способов сопоставления значений внешнего и возможного ключей
- Поддержка ссылочной целостности и ссылочные действия
- Примеры определений базовых таблиц
- Изменение определения базовой таблицы
- Добавление, изменение или удаление определения столбца
- Примеры изменения определения столбца
- Изменение набора табличных ограничений
- Примеры изменения набора табличных ограничений
- Отмена определения (уничтожение) базовой таблицы
- Средства определения и отмены общих ограничений целостности
- Определение общих ограничений целостности
- Отмена определения общего ограничения целостности
- Немедленная и откладываемая проверка ограничений
- Заключение
- 3. Лекция: Язык баз данных sql: общая характеристика оператора select и организация списка ссылок на таблицы в разделе from
- 4. Лекция: Язык баз данных sql: предикаты раздела where оператора select
- Предикат сравнения
- Примеры запросов с использованием предиката сравнения
- Предикат between
- Примеры запросов с использованием предиката between
- Предикат null
- Примеры запросов с использованием предиката null
- Предикат in
- Примеры запросов с использованием предиката in
- Предикат like
- Примеры запросов с использованием предиката like
- Предикат similar
- Примеры запросов с использованием предиката similar
- Предикат exists
- Примеры запросов с использованием предиката exists
- Предикат unique
- Примеры запросов с использованием предиката unique
- Предикат overlaps
- Примеры запросов с использованием предиката overlaps
- Предикат сравнения с квантором
- Примеры запросов с использованием предиката сравнения с квантором
- Предикат match
- Примеры запросов с использованием предиката match
- Предикат distinct
- Примеры запросов с использованием предиката distinct
- Заключение
- 5. Лекция: Язык баз данных sql: группировка и условия раздела having, порождаемые и соединенные таблицы
- Логические выражения раздела having
- Предикаты сравнения
- Предикат between
- Предикат null
- Предикат in
- Предикат like
- Предикат exists
- Предикат unique
- Предикаты сравнения с квантором
- Предикат distinct
- Более сложные конструкции оператора выборки
- Соединенные таблицы
- Формальные определения
- Примеры соединений разного вида
- Примеры запросов с использованием соединенных таблиц
- 6. Лекция: Язык баз данных sql: средства формулировки аналитических и рекурсивных запросов
- Возможности формулирования аналитических запросов
- Раздел group by rollup
- Агрегатная функция grouping
- Раздел group by cube
- Рекурсивные запросы
- Определения, относящиеся к рекурсии
- Рекурсивные запросы с разделом with
- Раздел search
- Раздел cyrcle
- Рекурсивные представления
- Заключение
- 7. Лекция: Язык баз данных sql: средства манипулирования данными
- Введение
- Базовые средства манипулирования данными
- Оператор insert для вставки строк в существующие таблицы
- Вставка всех строк указанной таблицы
- Вставка явно заданного набора строк
- Вставка строк результата запроса
- Оператор update для модификации существующих строк в существующих таблицах
- Оператор delete для удаления строк в существующих таблицах
- Представления, над которыми возможны операции обновления
- Представления, допускающие применение операций обновления, в стандарте sql/92
- Представления, допускающие применение операций обновления, в стандарте sql:1999
- Критерии применимости операций обновления
- Правила функциональных зависимостей
- Раздел with check option определения представления
- Режимы проверки cascaded и local
- Примеры результатов действия раздела with check option
- Исторический очерк