С.Д. Кузнецов - Основы баз данных (1121716), страница 76
Текст из файла (страница 76)
Монотонной прогрессией называется последовательность неубывающих или невозрастающих значений. Например, последовательность натуральных чисел (1, 2, ..., и, ...1 является монотонной. В 8(.)).:1999 свойство монотонности поддерживается в том смысле, что число строк результата рекурсивного запроса не уменьшается на каждом шаге рекурсии. Взаимная рекурсия. Элементы л и в связаны отношением взаимной рекурсии, если А прямо или косвенно вызывает В, и В прямо или косвенно вызывает л.
На рис. 16.9 показан графовый пример взаимной рекурсии (элемент л вызывает элемент в через элемент с, а элемент в вызывает элемент л через элемент В). Рис. 16.8. Графовый пример нелинейной рекурсии Зб4 Лекция !6 С вдствв формулировки аналитических и рвк рсивных запросов Рис. 1б.9. Графовый пример взаимной рекурсии Отрицание. В контексте Я !1. отрицанием называется любое действие, приводящее к уменьшению числа строк в результате запроса. Свойствами отрицания обладают операции над (мульти)множествами дхбдгт и п~тклбвСт, спецификация ~ЛбттЬХ.'т, условие Ют вХтбтя и т. д. В стандарте Я.Н.
не запрешается использование отрицания в рекурсивных запросах. Возможной проблемы нарушения монотонности удается избежать за счет того, что отрицание разрешается применять только к тем таблицам, которые являются полностью известными (или вычисленными) к моменту применения отрицания. В процессе вычисления таблицы применение к ней отрицания не допускается. Начальный источник рекурсии.
При выполнении рекурсивных вычислений обычно (хотя и не всегда) имеется некоторое начальное значение. В Я)) этим начальным источником рекурсии является одна или несколько строк, удовлетворяющих некоторым начальным условиям. На основе этих строк в процессе рекурсивного вычисления производятся дополнительные строки, образующие окончательный результат. Стратификация.
В КЯ1 рекурсивный запрос обычно состоит из «рекурсивной» и «нерекурсивной» частей. В процессе стратификации («расслоения») запроса выполнение этих двух частей разделяется. В более сложных рекурсивных запросах может содержаться несколько рекурсивных частей и более одной нерекурсивной части. В этом случае в процессе стратификации будет обнаружено большее число слоев. Семантика фиксированной точки. В контексте Я)(.:1999 семантика фиксированной точки означает, что решение о завершении рекурсивного запроса принимается тогда, когда становится невозможно добавить к результату какие-либо дополнительные строки.
Рекурсивные запросы с разделом твайты В предыдуших лекциях мы уже говорили о разновидности спецификации ссылки на таблицу с использованием раздела ыттн. Однако мы умышленно отложили обсуждение рекурсивных возможностей. Полный синтаксис раздела иттн выглядит следуюшим образом: Збб Основы баз данных Курс н(ГЙ с1аияе ::= ХТТН ( ВЕСОВЯ1уЕ ] н(гй е1евепг совва 11яг н(ГЬ е1евепс ::= снегу паве ( (со1ивп г1аве 1(яс) АЯ ( сгиегу ехргеяя(оп ) ( яеагсЬ ог сус1е с1аияе яеагс)з ог сус1е с1аияе ::= яеагсЬ с1аияе ( сус1е с1аияе яеагсЬ с1аияе сус1е с1аияе яеагсЬ с1аияе ::= ЯЕАВСН гесигя(че яеагсЬ огс(ег ЯЕТ яес(иепсе со1ипв паве гесигя(че яеагсЬ огс(ег ::= ОЕРТН Р1ВЯТ ВУ ог((ег (сев сопппа11яс ВВЕАОТН Р1ВЯТ ВУ огс(ег Тсещ соппна11яс сус1е с1аияе ::= СХОЖЕЕ сус1е со1ивп паве сон«па 11яс ЯЕТ сус1е вагх со1ипп паве ТО ча1ие ехргеяяуоп ОЕРАОЕТ ча1ие ехргеяя(оп ОЯ1ИО раГЬ со1ивп пап1е Для иллюстрации возможностей рекурсивных запросов с разделом ИТТН и пояснения смысла конСтрукций ЯЕАВСН и СХСЕЕ воспользуемся классическим примером «разборки деталей«(в данном случае мы будем разбирать автомобиль).
Предположим, что данные о конструктивных элементах автомобиля хранятся в таблице САВ, определенной следуюшим образом: СВЕАТЕ ТАВ(Е САВ (СОИТА1И1ИО РАНТ ЧАВСНАВ (10), СОЫТАТИЕО РАВТ ЧАВСНАВ (10), НОНВЕВ ОР РАВТЯ 1МТЕОЕВ, РАВТ СОЯТ ОЕС1ИАЕ (6,2))," У автомобиля имеется один конструктивный элемент верхнего уровня — полностью собранный автомобиль. Этот элемент не является составной частью какого-либо другого элемента, и для его строки значением столбца СОНТАТНТНО РАНТ является текстовая строка длины О. В любой другой строке таблицы сАВ, соответствуюшей некОтОрому неатОмаРному конструктивному элементу е, столбец соитА1И1ИО РАНТ содержит Идентификационный номер элемента е1, в который входит элемент е, столбец НОНВЕВ ОР РАВТЯ вЂ” число экземпляров элемента е, входящих в е1, а столбец сОИтА1нер РАВт — идентификационный номер самого элемента е.
В любой строке таблицы САВ, соответствуюШей некоторому атомарному конструктивному элементу, значением столбца СОМТА1НЕО РАНТ является Строка ДЛИНЫ О, а в столбце РАНТ СОЯТ сохраняется цена атомарного конструктивного элемента (для неатомарных элементов значение этого столбца равно нулю). Предположим„что нам требуется разобрать автомобиль, начиная с элемента самого верхнего уровня, и для каждого конструктивного элемента Лекция! б Средства формулировки аналитических и рекурсивных запросов получить его номер, общее число используемых экземпляров этого элемента, а также, если элемент является атомарным, общую стоимость используемых экземпляров. Вот возможная формулировка запроса (пример 16.3): Х1ТН ВЕСНВЯТЪЕ РАВТЯ (РАНТ МНМЕЕВ, %ЗМЕЕВ ОР РАРТЯ, СОЯТ) АЯ )ЯЕЬЕСТ СОИТА1ИЕР РАНТ, 1, 0.00 (а) РВОМ САВ ХНЕВЕ СОИТА1И1ИО РАНТ ОМ10И АйЬ ЯЕ1 ЕСТ САВ.СОИТА1ИЕО РАНТ, САВ.ЬВ)МЕЕВ ОР РАВТЯ, САВ.НОМЕЕВ ОР РАВТЯ * САВ.РАНТ СОЯТ РВОМ САВ, РАВТЯ хнеле РАВТБ.РАНТ номвеВ = сАВ.СОНТА1нтмо РАВт) Яеоест РАРт момееВ, Яом)момвеВ ОР РАВтЯ), Яом)СОЯт) (Ь) РВОМ РАВТЯ ОВООР ВУ РАНТ ИОМВЕРо Этот запрос будет выполняться следующим образом.
При вычислении раздела РВом основного запроса (ь) начнется выполнение рекурсивного выражения запросов (а), определенного в разделе х1тн. На первом шаге рекурсии будет выполнена часть данного выражения, предшествующая операции ОМТОН АЬЬ и образующая начальный источник рекурсии.
В результате будет произведено исходное состояние виртуальной таблицы РАВТБ, в котором, в нашем случае, появится единственная строка, соответствующая автомобилю целиком. На следующем шаге к таблице РАВтЯ будут добавлены строки, соответствующие конструктивным элементам второго уровня (для автомобиля это, по-видимому, двигатель, колеса, шасси и т.
д.). Этот процесс будет продолжаться до тех пор, пока мы не дойдем до атомарных конструктивных элементов и не достигнем, тем самым, фиксированной точки. Поскольку в рекурсивном запросе содержится операция ОМ10М АЫ,, в результируюшей таблице могут появляться строки-дубликаты. Наличие строки-дубликата вида <рагс по, питлбег, сове> означает, что элемент с номером рагс по входит в одном и том же числе экземпляров в несколько конструктивных элементов более высокого уровня. РаЗДЕЛ ННАНСН В приведенном выше примере не определялся порядок, в котором строки добавляются к частичному результату рекурсивного запроса. Однако иногда требуется, чтобы иерархия обходилась в глубину или в ширину.
Соответствуюшая возможность обеспечивается конструкцией ЯВАВсн. При указании требования обхода в глубину гарантируется, что каждый элемент- 367 Основы баз данных Курс предок появится в результате раньше своих потомков и своих братьев справа. Если указывается требование обхода иерархии в ширину, в результате все братья одного уровня появляются раньше, чем какой-либо их потомок. Ниже показан вариант запроса, в котором содержится раздел Бейдсн с требованием обхода иерархии элементов автомобиля в ширину (пример 16.4). Х1ТН ВЕСОВЯ1)ЗЕ РАВТЯ (АЯЯЕМВЕУ, РАРТ РОМЕЕВ, %ЗМЕЕВ ОГ РАВТЯ, СОБТ) АЯ ЗЯЕЬЕСТ СОИТА1И1ИО РАНТ, СОИТА1ИЕР РйВТ, 1, 0.00 ГНОМ САВ ХНЕВЕ СОИТА1И1НО РАРТ ОН1ОН Айй ЯЕЕЕСТ САВ.СОИТА1Н1ИО РАНТ, САВ.СОИТА1ИЕО РйВТ, САВ.%ЗМЕЕВ ОГ РйВТЯ, САВ.НОМВЕВ ОГ РАВТБ * СйВ.РАРТ СОЯТ РВОМ САВ, РАВТБ ХНЕВЕ РАРТБ.РАНТ НЗЗМВЕВ = САВ.СОИТА1И1ИО РАНТ) ЯЕРВСН НВЕА1УГН Г1ВЯТ ВУ СОНТА1Н1НО РАНТ, СОНТА1ИЕР РАНТ ЯЕТ ОВОЕВ СОЫЖИ ЯЕЕЕСТ РАРТ НОМНЕВ, ЬПЗМЕЕВ ОГ РАВТБ, СОЯТ ГРОМ РАВТЯ ОВРЕВ ВХ ОВОЕВ СОЮМИЗ В списке столбцов сортировки раздела БеАВсн должны указываться имена столбцов виртуальной таблицы, определенной в разделе х1 тн.
Поскольку в данном случае мы хотим, чтобы в результате сначала появлялись все конструктивные элементы одного уровня (сонтй1НТВЯ РАВт), а затем все их подэлементы (СОМРАТМЕО РАНТ), в список выборки рекурсивного запроса РАВТЯ добавлен столбец сонтй1нтна РАВт, который не используется нигде, кроме раздела яейВСН. В разделе яет к результирующей таблице рекурсивного запроса добавлен столбец, который мы назвали ОВОЕВ СОЬНМХ. Название соответствует природе столбца, потому что при выполнении рекурсивного запроса в этот столбец автоматически заносятся значения, характеризующие порядок генерируемых строк в соответствии с выбранным способом обхода иерархии.
Чтобы строки результата основного запроса появлялись в должном порядке, в этом запросе требуется наличие раздела ОВОЕВ ВУ с указанием столбца, определенного в разделе Яет. Раздел стдсде Наконец, обсудим, для чего нужен раздел СУВСЬЕ. Дело в том, что иногда сами данные, хранимые в таблицах базы данных, могут иметь цик- 368 Лекция 1б Средства формулировки аналитических и рекурсивных запросов лическую природу. Представим себе, например, компанию, в которой существует совет директоров, являющийся высшим органом управления компанией.
Обычным случаем является тот, когда, по крайней мере, один из членов совета директоров является простым служащим этой же компании (например, он может входить в совет директоров как представитель профсоюза). Назовем данного члена совета директоров емр Рте. Как член совета директоров, ЕМР РТЕ «управляет» деятельностью президента компании.
С другой стороны, как служащий компании, Емр Р1е находится в прямом или косвенном подчинении у президента компании. Такое положение может привести к зацикливанию выполнения рекурсивных запросов. Раздел суесье обеспечивает некоторую возможность распознавать подобные ситуации. Если у пользователя имеется полная уверенность в отсутствии циклов в данных, к которым адресуется рекурсивный запрос, то использование раздела СХЕСЬЕ не требуется. Подход к распознаванию зацикленных запросов, принятый в БЯ), состоит в том, что распознаются данные, которые уже участвовали ранее в формировании результата рекурсивного запроса. При наличии раздела СУЕСЬЕ при добавлении к результату строк, удовлетворяющих условию запроса, такие строки помечаются указанным значением, которое означает, что эти строки уже вошли в результат.
При попытке добавления к результату каждой новой строки проверяется, не находится ли она уже в результате, т. е. не помечена ли она этим указанным в разделе СТЕСРЕ значением. Если это действительно так, то считается, что имеет место цикл, и дальнейшее выполнение рекурсивного запроса прекращается. Обсудим все это более формально. Для удобства воспроизведем еше раз синтаксис раздела СУЕСЬЕ. сус1е с1ацве::= СУСЛЕ сус1е со1цлкт паше солтла 11вг БЕТ сус1е п~агх со1плтп ватле ТО ча1це ехргевсуоп 1 РЕРАРЬТ ча1пе ехргеввуоп 2 РЯ1МС рас1т со1чтлп папе В списке сус1е со1цтпп папе солтла 11вс указываются имена одного или нескольких столбцов, которые используются для идентификации новых строк результата на основе строк, уже входящих в результат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
