Введение в системы БД (542480), страница 242
Текст из файла (страница 242)
Кроме того, для интенсиональной базы данных существует следующий набор ограничений внешних ключей. ЯР ( я, р, д ) =ь Я ( в, яп, я1, яс ) АМР Р ( р, рл, рс, рн, рс ) И т.д. Замечание. Для удобства представления здесь предполагается, что переменные, расположенные справа от символа импликации (ял, я1 и тш.), связаны с квантором существования. (Все остальные, как отмечалось выше, в разделе 23.3, связаны с квантором всеобщности.) С технической точки зрения мы нуждаемся в некоторой функции Сколема. Например, переменная яп в действительности должна быть заменена, скажем, функцией ЯМ( я), тле ЯМ является функцией Сколема. Кстати, обратите внимание, что в данном случае многие ограничения нельзя считать чистыми предложениями в смысле. определенном в разделе 23.5, поскольку их правая сторона не является дизъюнкцией простых термов, Теперь следует добавить несколько дедуктивных аксиом.
Я( я, яп, яс, яс)АМРяс>15 =ь 0000 ЯОРРРТЕН ( я, яП, яс ) (Сравните с определением представления ОООР ЯОРР1 1ЕН, данным в разделе 9.1 главы 9.) Я ( ях, яхп, яхс, яс ) АМР Я ( яу, яуп, яу1, яс ) => ЯЯ СОРОСАТЕО ( ях, яу ) Я ( я, яп, яс, с ) АМР Р ( р, рл, р1, рн, с ) => ЯР СОЬОСАТЕР ( я, р ) И т.д.
Для того побы рассматриваемый пример был интереснее, попробуем расширить базу данных поставщиков и деталей, включив в нее переменную-отношение "состав деталей", которая будет содержать сведения о том, какие детали ру входят в качестве компонентов первого уровня в состав другой детали (узла) рх. Для зтого прежде всего следует задать ограничение на идентификацию существующих деталей (рх и ру). 920 Часть р'. дополнительные аспекты РАКТ ЯТКОСТОКЕ ( рх, ру ) =о Р ( рх, хп, х1, хь', хс ) АИО Р ( ру, уп, у1, уь, ус ) Затем необходимо определить некоторые значения ее данных. РАКТ ЯТКОСТОКЕ РКРТ ЯТКОСТОКЕ РАКТ ЯТКОСТОКЕ РАКТ ЯТКОСТОКЕ и т.д.
(На практике определение РАКТ ЯТКОСТСКЕ должно было бы также иметь аргумент "количество'*, который указывал бы количество деталей ру, входящих в состав детали рх, но в данном случае он опускается из соображений простоты.) Теперь можно добавить пару дедуктивных аксиом для обаяснения, каким образом деталь рх содержит деталь ру в качестве компонента любо~о уровня. РАКТ ЯТКОСТОКЕ ( рх, ру ) ~ СОИРОКЕКТ ОР ( рх, ру ) РАКТ ЯтйоотОКЕ ( рх, рг ) АИО СОИРОИЕИт ОР ( рг, ру ) ~ СОМРОИЕМТ ОР ( рх, ру ) Иначе говоря, деталь ру является компонентом детали рх на определенном уровне, если она является непосредственным компонентом либо детали рх, либо детали рг, которая, в свою очередь, является компонентом детали рх на определенном уровне.
Обратите внимание, что вторая аксиома рекурсивна, поскольку предикат СОИРОИЕИТ ОР определяется в ней на основе самого этого предикатаз. В классических реляционных системах, наоборот, не допускается использование полобных рекурсивных определений представлений (а также запросов, ограничений целостности и т.п.). Эта способность поддерживать рекурсивные определения — одно из самых очевидных различий между дедуктивными СУБД и их классическими аналогами. Хотя, как уже упоминалось в разделе 23.5 и как было показано в главе 6, не существует фундаментального ограничения, из-за которого классическую реляционную алгебру нельзя было бы расширить для поддержки соответствующего набора рекурсивных операторов.
В разделе 23.7 возможность поддержки рекурсии обсуждается несколько подробнее. Язык Оа1а!ор Из сказанного можно слелать вывод, что наиболее ясно выраженной частью дедуктивной СУБД может быть язык, на котором будут формулироваться дедуктивные аксиомы (или правила). Самым известным языком такого типа является Раса!ой [23.9), названный так по аналогии с языком Рго)ой. Ниже приведено его краткое описание. Замечание. Основное внимание при создании этого языка уделялось не его вычислительным (как это обычно бывает с традиционными реляционными моделями [5.1)), а описательным качествам.
При этом основной целью было создание языка, гораздо более 5 Фактически было определено траизитивиое замыкание — в любой момент отношение, соответствуюи5ве предикату СОМРОМЕМТ ОР, являеп1ся транзитивным заиыкинием отношвния, соопметствуюгчесо предикату РАКТ ЯТКОСТОКЕ <см славу б). 921 Глава 23. Логические системы управления базами данных выразительного, чем традиционные реляционные языки (23.9).
В результате в языке Рага(о„, как и во всех логических СУБД, был сделан акцент на операциях выполнения запросов, а не обновления данных, хотя можно и нужно расширить этот язык также для поддержки операций обновления (подробнее об этом будет сказано ниже). В простейшей форме язык Ра!а(оЕ поддерживает формулировку правил в виде простых прелложеиий Хорна без функций. В разделе 23.4 предложение Хорна было определено как %ГГ-формула одного из двух видов. А? АКР А2 АКР ...
АКР Ап А1 АКР А2 АКР ... АКР Ап ~ В В этих конструкциях все А и В являются неотрицаемыми экземплярами предикатов, которые содержат только константы и переменные. Однако в языке Ра!а(оЕ вторая из приведенных конструкций записывается в обратном порядке. В ~ А? АКР А2 АКР ... АКР Ап Для полного соответствия с другими публикациями на эту тему далее будет использоваться именно такая запись. В данном предложении В является заголовком правила, или заключением, а терм А — телом правила, или предпосылкой либо целью, в которой отдельные термы являются подчиненными целями (или подцелями). Для краткости связки АКР часто заменяют запятыми.
Следовательно, программа на языке Ра1а!ой представляет собой набор таких предложений. разделенных обычным образом, т.е. точкой с запятой (в этой книге, однако, вместо точки с запятой используется перенос на отдельную строку). При этом в такой программе порядок расположения предложений не имеет никакого значения. Заметим, что вся дедукгннвная база данных может рассматриваться как программа Раса!оЕ в указанном выше смысле. Можно, например, все аксиомы, заданные для поставщиков и деталей (основные аксиомы, ограничения целостности и дедуктивные аксиомы), записать в с~иле программы Рага(об, разделив их точкой с запятой или разместив в отдельных строках, и в результате получить программу на языке Ра!а1оЕ, Однако, как уже указывалось, экстенсиональная часть базы данных обычно не определяется таким способом; она определяется так, как принято в традиционных базах данных.
Основная функция языка Ра!а1оЕ заключается в формулировании дедуктивных аксиом. Как отмечалось выше, эту функцию следует рассматривать в качестве расширения механизма определений представлений, существующего в современных реляционных СУБД. Язык Ра!а!оЕ может также использоваться в качестве языка запроса (точно так, как и язык Рго1оЕ). Для примера предположим, что на языке Ра!а!оЕ дано следующее определение "хороших" поставщиков 6000 ВРРРЕ?ЕК.
6000 ЯРРРР2ЕК ( в, вВ, вс ) ~ Я ( в, вп, вВ, вс ) АКР вс > 15 Ниже приведены примеры запросов на основе этого определения. 1. Найти всех хороших поставщиков. ? е= 6000 ВРРРЕ?ЕК ( в, вв, вс ) 2. Найти хороших поставщиков в Париже. ? е= 6000 ВРРРЕ?ЕК ( в, ве, 'Рагзв' ) 922 Часть р. дополнительные аспекты 3.
Является ли поставщик с номером 'Я1' хорошим? ? ~ 6000 ЯОРРЫЕЕ ( 'Б1', вс, вс ) И так далее. Иначе говоря, запрос на языке Оа!а!оЕ состоит из специального правила с заголовком типа "?" и телом, состоящим из одного герма, который обозначает результат запроса. Заголовок "?" означает (по соглашению) "Показать". Следует отметить, что несмотря на поддержку рекурсии сушествует достаточное количество стандартных операций для традиционных реляционных систем, которые не поддерживаются в языке Оа!а!оЕ, например скалярные операции ("+", "-" и т.д.), операции обобщения (СОСЕТ, ЯОИ и др.)„группирования и т.д.
В этом языке также не поддерживается именование атрибутов (значение аргументов предиката зависит от его относительного расположения), не обеспечивается полная поддержка доменов (т.е. типов данных, определенных пользователем в смысле, изложенном в главе 5). Как уже отмечалось, в языке не предусмотрены операции обновления, а также не поддерживается декларативная спецификация удаления и обновления внешних ключей (ОЕ1ЛТЕ САБСАОЕ и т.д.). Для преодоления всех этих недостатков было предложено несколько расширений языка Оага!оЕ. Предполагается, что, помимо всего прочего, эти расширения обладают следуюшими дополнительными возможностями.
° Отрицаемые предпосылки, например такие, как показано ниже. ЯЯ СОБОСАТЕО ( вх, ву ) е= Я ( вх, вхл, вхС, вс ) АИО Я ( ву, вул, ву4, вс ) АИО ИОТ ( вх = ву ) ° Скалярные операторы (встроенные и определенные пользователем), например такие, как показано ниже. Р ИТ 1И БЕАИБ ( р, рп, р1, рд, рс ! е= Р ( р, рп, р1, ри, рс ) АИО рд = ри * 454 В данном примере предполагается, что встроенная функция "*" (умножение) может быть записана в обычном инфиксном представлении.
Более ортодоксальное представление герма, следующего за оператором АИО, выглядело бы как =( рд, * (ри, 454 ) ) . ° Операторы обобщения и группиравания (в некотором смысле эта тема касается отдельных особенностей оператора БОИИАЕ1БЕ, что подробнее описано в главе 6). Эти операторы необходимы для того, чтобы разрешить проблему так называемых требований обобщения. Она заключается не только в поиске деталей ру, которые являются компонентами деталей рх на любом уровне, но также в выяснении, сколько деталей ру (на всех уровнях) требуется для изготовления детали рх (при этом, естественно, предполагается, что переменная-отношение РАЕТ БТЕОСТЕЕЕ содержит атрибут ОТ?).
° Операторы обновления. Один из подходов в реализации этих операций, и не только их, основан на том наблюдении, что в языке 1)аГа!оЕ любой предикат в заголовке правила должен быть неотрицаемым и каждый кортеж, генерируемый этим правилом, может рассматриваться как "вставленный" в результирующее отношение. Возможное расширение, таким образом, должно допускать использование отрицаемых предикатов в заголовке правила и рассматривать отрицание как запрос иа удаление (соответствуюшнх кортежей). Глава 23. Логические системы управления базами Донных 923 ° Предложения "нв-карловского" типа в теле правила. Иначе говоря, в определении правил лопускается использование %ГЕ-формул самого общего вила. Обзор этих расширений вместе с примерами и обсуждением приложений языка Рага!о8 можно найти в книге (23.!О), где также обсуждается множество методов реализации языка Раса!ой.
23.7. Обработка рекурсивных запросов Как отмечалось в предыдущем разделе, одна из наиболее замечательных особенностей дедуктивных СУБД вЂ” способность поддерживать рекурсию. Именно поэтому изучению технологий реализации рекурсии в последние годы уделялось значительное внимание. Действительно, с 1986 года на каждой научной конференции по базам данных один или несколько докладов обязательно посвящаются этой теме. Ниже кратко обсуждается поддержка рекурсивных запросов — функция, которая обычно не характерна для традиционных СУБД.
В качестве примера повторим приведенное в разделе 23.6 рекурсивное определение переменной-отношения СОМРОМЕМТ ОГ в терминах структуры состава деталей РйЕТ ЯТЕОСТОЙЕ (для краткости вместо полного названия РйЕТ ЯТЕОСТОЕЕ используется сокращение РЯ, а вместо СОМРОМЕМТ ОР— СОМР; кроме того, используется запись, принятая в языке Ра!а!о8). СОМР ( рх, ру ) «= РЯ ( рх, ру ) СОМР ( рх, ру ) ~ РЯ ( рх, рг ) йМО СОМР ( рг, ру ) А вот пример типичного рекурсивного запроса к базе данных (" Найти все компоненты, из которых состоит деталь с номером 'Р1'"). Р «= СОМР ( 'Р1' Ру ) Второе правило в приведенном выше рекурсивном определении является линейно рекурсивным, поскольку предикат из заголовка правила встречается в теле правила только один раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
