Рекурсивные запросы

  Содержание: 

  Введение………………….……………………………………...……………….3

  1 Рекурсивные запросы .…………………….………………………….……….4

  1.1 Определения, относящиеся к рекурсии…………………………………….4

  1.2 Рекурсивные запросы с разделом WITH……………………………………7

  1.3 Рекурсивные представления………………………………………………..12

  Заключение…………………………………………………………………………...14

  Список  литературы…………………………………………………………....……..15 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

            

      Введение

      Традиционно язык SQL никогда не обладал возможностью формулировки рекурсивных запросов, где под рекурсивным запросом мы понимаем запрос к таблице, которая сама каким-либо образом изменяется при выполнении этого запроса. Это заложено в базовую семантику оператора SQL: до выполнения раздела WHERE результат раздела FROM должен быть полностью вычислен.

      Однако  разработчикам приложений часто приходится решать задачи, для которых недостаточно традиционных средств формулировки запросов языка SQL: например, нахождение маршрута движения между двумя заданными географическими точками, определения общего набора комплектующих для сбора некоторого агрегата и т.д. Компании-производители SQL-ориентированных СУБД пытались удовлетворять такие потребности за счет частных решений, обладающих ограниченными рекурсивными свойствами, но до появления стандарта SQL:1999 общие стандартизованные средства отсутствовали.

      Следует отметить и некоторое давление на SQL-сообщество со стороны сообщества логических систем баз данных. На основе языка логического программирования Prolog был разработан язык реляционных  баз данных Datalog, обеспечивающий все необходимые средства для обычной работы с базами данных наряду с развитыми возможностями рекурсивных запросов. Требовался адекватный ответ со стороны разработчиков стандарта SQL.

      Компромиссное решение для введения рекурсии в SQL было найдено на основе введения раздела WITH в выражение запроса. Только в этом разделе допускается как линейная, так и взаимная рекурсия между вводимыми порождаемыми таблицами. При этом только для линейной рекурсии обеспечиваются дополнительные возможности управления порядком вычисления рекурсивно определенной порождаемой таблицы и контроля отсутствия циклов. Следует заметить, что при чтении стандарта временами возникает впечатление, что его авторы сами не до конца еще осознали всех возможных последствий, к которым может привести использование введенных конструкций.

      

      

      1 Рекурсивные запросы

      Начнем  этот раздел с нескольких определений, касающихся понятий, которые связаны  с рекурсией. Эти понятия имеют  общий характер, но в приведенных  ниже определениях и комментариях к  ним (там, где это уместно) подчеркивается контекст SQL.

      1.1 Определения, относящиеся к рекурсии

      Обход дерева в ширину. При этом способе обхода непосредственные потомки обходятся слева направо, до того как производится переход к потомкам следующего уровня родства.

  

 
Рис. 1.1.  Пример дерева

      При обходе в ширину дерева, показанного  на рис. 1.1, узлы будут обходиться в следующем порядке: Корень-Потомок1-Потомок2-Потомок3-П1.1-П1.2-П1.3-П2.1-П2.3-П3.1-П3.2-П3.3.

      Обход дерева в глубину. При этом способе обхода на каждом шаге производится переход к самому левому текущему потомку. При обходе в глубину дерева с рис. 1.1 порядок обхода узлов будет следующим: Корень-Потомок1-П1.1-П1.2-П1.3-Потомок2-П2.1-П2.2-П2.3-Потомок3-П3.1-П3.2-П3.3.

      

      Цикл  в ориентированном  графе. В теории графов ориентированный граф называется циклическим в том и только в том случае, когда хотя бы один узел графа одновременно является и предком, и потомком (т. е. для этого узла имеется и выходящая, и входящая дуги). В SQL:1999 узлами графа рекурсии являются строки, входящие в результат рекурсивного запроса, а дуги соответствуют способам обработки текущих строк, которые ведут к добавлению к результату новых строк. На рис. 1.2 показан простейший пример ориентированного графа с циклом.

  

 
Рис. 2.2.  Пример графа с циклом

      Прямая  рекурсия. По определению, некоторый элемент использует прямую рекурсию в том и только в том случае, когда он обращается сам к себе без посредников. Пример, приведенный на рис. 2.2, демонстрирует (в графовой форме) прямую рекурсию. На рис. 2.3 показан графовый пример непрямой рекурсии.

  

 
Рис. 2.3.  Графовый пример непрямой рекурсии

      Линейная  рекурсия. При линейно рекурсивном вызове элемент прямо рекурсивно обращается сам к себе не более одного раза. В SQL:1999 в определении любой виртуальной таблицы с рекурсией допускается не более одной ссылки на саму себя (в разделе FROM и/или в подзапросах). На рис. 2.4 показан графовый пример рекурсии, не являющейся линейной.

      Монотонность. Монотонной прогрессией называется последовательность неубывающих или невозрастающих значений. Например, последовательность натуральных чисел {1, 2, ... , n, ...} является монотонной. В SQL:1999 свойство монотонности поддерживается в том смысле, что число строк результата рекурсивного запроса не уменьшается на каждом шаге рекурсии.

      

      Взаимная  рекурсия. Элементы A и B связаны отношением взаимной рекурсии, если A прямо или косвенно вызывает B, и B прямо или косвенно вызывает A. На рис. 2.5 показан графовый пример взаимной рекурсии (элемент A вызывает элемент B через элемент C, а элемент B вызывает элемент A через элемент D).

  

 
Рис. 2.4.  Графовый пример нелинейной рекурсии

  

 
Рис. 2.5.  Графовый пример взаимной рекурсии

      Отрицание. В контексте SQL отрицанием называется любое действие, приводящее к уменьшению числа строк в результате запроса. Свойствами отрицания обладают операции над (мульти)множествами EXCEPT и INTERSECT, спецификация DISTINCT, условие NOT EXISTS и т.д. В стандарте SQL не запрещается использование отрицания в рекурсивных запросах. Возможной проблемы нарушения монотонности удается избежать за счет того, что отрицание разрешается применять только к тем таблицам, которые являются полностью известными (или вычисленными) к моменту применения отрицания. В процессе вычисления таблицы применение к ней отрицания не допускается.

      Начальный источник рекурсии. При выполнении рекурсивных вычислений обычно (хотя и не всегда) имеется некоторое начальное значение. В SQL этим начальным источником рекурсии является одна или несколько строк, удовлетворяющих некоторым начальным условиям. На основе этих строк в процессе рекурсивного вычисления производятся дополнительные строки, образующие окончательный результат.

      

      Стратификация. В SQL рекурсивный запрос обычно состоит из «рекурсивной» и «нерекурсивной» частей. В процессе стратификации («расслоения») запроса выполнение этих двух частей разделяется. В более сложных рекурсивных запросах может содержаться несколько рекурсивных частей и более одной нерекурсивной части. В этом случае в процессе стратификации будет обнаружено большее число слоев.

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

      1.2 Рекурсивные запросы с разделом WITH

      Полный  синтаксис раздела WITH выглядит следующим образом:

with_clause ::= WITH [ RECURSIVE ]

with_element_comma_list

with_element ::= query_name [ (column_name_list) ]

     AS ( query_expression ) [ search_or_cycle_clause ]

search_or_cycle_clause ::= search_clause

    | cycle_clause

    | search_clause cycle_clause

search_clause ::= SEARCH recursive_search_order SET

      sequence_column_name

recursive_search_order ::= DEPTH FIRST BY

      order_item_commalist

    | BREADTH FIRST BY order_item_commalist

cycle_clause ::= CYCLE cycle_column_name_comma_list

    SET cycle_mark_column_name TO value_expression

    DEFAULT value_expression

    USING path_column_name

      Для иллюстрации возможностей рекурсивных  запросов с разделом WITH и пояснения смысла конструкций SEARCH и CYCLE воспользуемся классическим примером «разборки деталей» (в данном случае мы будем разбирать автомобиль). Предположим, что данные о конструктивных элементах автомобиля хранятся в таблице CAR, определенной следующим образом:

CREATE TABLE CAR (CONTAINING_PART VARCHAR (10),

                  CONTAINED_PART VARCHAR (10),

                  NUMBER_OF_PARTS INTEGER,

                  PART_COST DECIMAL (6,2));

      У автомобиля имеется один конструктивный элемент верхнего уровня – полностью  собранный автомобиль. Этот элемент  не является составной частью какого-либо другого элемента, и для его  строки значением столбца CONTAINING_PART является текстовая строка длины 0. В любой другой строке таблицы CAR, соответствующей некоторому неатомарному конструктивному элементу e, столбец CONTAINING_PART содержит идентификационный номер элемента e1, в который входит элемент e, столбец NUMBER_OF_PARTS – число экземпляров элемента e, входящих в e1, а столбец CONTAINED_PART – идентификационный номер самого элемента e. В любой строке таблицы CAR, соответствующей некоторому атомарному конструктивному элементу, значением столбца CONTAINED_PART является строка длины 0, а в столбце PART_COST сохраняется цена атомарного конструктивного элемента (для неатомарных элементов значение этого столбца равно нулю).

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

WITH RECURSIVE PARTS (PART_NUMBER,

        NUMBER_OF_PARTS, COST) AS

   (SELECT CONTAINED_PART, 1, 0.00 (a)

   FROM CAR

   WHERE CONTAINING_PART = ''

UNION ALL

   SELECT CAR.CONTAINED_PART, CAR.NUMBER_OF_PARTS,

      CAR.NUMBER_OF_PARTS * CAR.PART_COST

   FROM CAR, PARTS

   WHERE PARTS.PART_NUMBER = CAR.CONTAINING_PART)

SELECT PART_NUMBER, SUM(NUMBER_OF PARTS),

   SUM(COST) (b)

FROM PARTS

GROUP BY PART_NUMBER;

      Этот  запрос будет выполняться следующим  образом. При вычислении раздела  FROM основного запроса (b) начнется выполнение рекурсивного выражения запросов (a), определенного в разделе WITH. На первом шаге рекурсии будет выполнена часть данного выражения, предшествующая операции UNION ALL и образующая начальный источник рекурсии. В результате будет произведено исходное состояние виртуальной таблицы PARTS, в котором, в нашем случае, появится единственная строка, соответствующая автомобилю целиком. На следующем шаге к таблице PARTS будут добавлены строки, соответствующие конструктивным элементам второго уровня (для автомобиля это, по-видимому, двигатель, колеса, шасси и т.д.). Этот процесс будет продолжаться до тех пор, пока мы не дойдем до атомарных конструктивных элементов и не достигнем, тем самым, фиксированной точки. Поскольку в рекурсивном запросе содержится операция UNION ALL, в результирующей таблице могут появляться строки-дубликаты. Наличие строки-дубликата вида <part_no, number, cost> означает, что элемент с номером part_no входит в одном и том же числе экземпляров в несколько конструктивных элементов более высокого уровня.

      Раздел SEARCH

      В приведенном выше примере не определялся  порядок, в котором строки добавляются  к частичному результату рекурсивного запроса. Однако иногда требуется, чтобы иерархия обходилась в глубину или в ширину. Соответствующая возможность обеспечивается конструкцией SEARCH. При указании требования обхода в глубину гарантируется, что каждый элемент-предок появится в результате раньше своих потомков и своих братьев справа. Если указывается требование обхода иерархии в ширину, в результате все братья одного уровня появляются раньше, чем какой-либо их потомок. Ниже показан вариант запроса, в котором содержится раздел SEARCH с требованием обхода иерархии элементов автомобиля в ширину.

WITH RECURSIVE PARTS (ASSEMBLY, PART_NUMBER,

        NUMBER_OF_PARTS, COST) AS