Введение в системы БД (542480), страница 245
Текст из файла (страница 245)
Запишите на языке Рага(ой решения для упр. 6.(3 — 6.50, где это возможно. 23.7. Запишите на языке Рага(оЕ решения для упр. 8.(, где это возможно. 23.8. Заверши~с (ради собственного удовольствия) объяснение реализации метода унификации и резолюции, данное в разделе 23.7, для решения запроса "Найти все компоненты детали с номером 'Р1'".
Список литературы В последние годы число публикаций в области логических СУБД быстро возрастает, и приведенный ниже список предо~валяет собой лишь малую чань всей имеющейся на сегодня ли~ературы. Список включает следующие тематические группы. ° Книги [23.1]-[23.9] или посвящены логике в целом (отчасти в контексте вычислений, отчасти в контексте баз данных), или представляют собой сборники статей именно по логическим СУБД. ° Работы [23.10]-[23.12] являются учебными пособиями, как и книги [23.46] и [23.47].
° Работы [23.14], [23.17] — [23.20], [23.30], [23.49] и [23.50] посвящены операции транзнтивного замыкания и ее реализации. ° В работах [23.21]-[23.24] описана важная метолика выполнения рекурсивных запросов — "магические множества", а также различные ее варианты.
Замечание. С этим вопросом также связаны публикации [17.24]-[17.26]. Остальные публикации демонстрируют масштабность исследований, которые ведутся в этой области. В них описываются лополнительные аспекты этой темы (в основном, без комментариев). 23.1. Бгой П.П. Бевй Еой!с апг! Ахютайс ТЬеопев. — Бап Ггапсасо, СаЫ: %.Н. Ггеетап апг! Сотрапу, 1961. Представляет собой весьма неплохое введение в логику. 23.2.
Маппа 2., ФаЫ!пйег й. ТЬе Ьой!са! Ваяв гог Сотршег Ргойгапип!п8. Чо[ите 1. 1)едисйте йеавоп!п8 (1985); Чо[ите П. Эедисйте ТесЬп!с!иев (1990). — йеай!п8, Мазал АгЫ!воп-%ев[еу, 1985, 1990. 233. Оту Р.М.(3. 1лй!с, А18еЬга апд ЭатЬвпев. — СЫсйеяег, Еп81апд: ЕПЬ Нонкой 1Ы., 1984. Книга является прекрасным введением в исчисление высказываний и исчисление предикатов с точки зрения базы данных. В ней также освещены другие темы, имеющие непосредственное отношение к ланной. 23.4.
Фа!кег А.„МсСогд М., Бозта ЛР., %йвоп %.О. Кпотт!ебйе Буяетв апд Рго!ой (2пд еб,). — йеаб[п8, Макал АгЫ!воп-Фев!еу, 1990. Хотя книга и посвящена логическому программированию в целом, в ней достаточно материала, касающегося логических СУБД в частности. 23.5. Оайа!ге Н., М|п1сег 1. Бой!с апг[ Вага Вавев. — Хетт Уог1с, Н.У.: Р!епшп РиЫ!вЫпй Согр., 1978. Один из первых (если не самый первый) сборников статей по данной теме. 23.6. кегвььегй 1.. (ед,).
ехреп Оашьаве Буяетв д Ргос. !я!пг. Фогиюр оп ехреп Ра1аьаве Бувгетв (К!азтаЬ 1в!апд, Б.С.). — Мел[о Рагй, СаИ.: Веп]ат!и/Ситт!пйв, 1986. Прекрасный сборник статей, располагающих к размышлениям. Однако не все они непосредственно связаны с темой данной главы. Даже названия разделов вносят некоторую путаницу в то, что же на самом деле относится "к экспертным системам баз данных". Перечислим эти разделы. 1.
Теория баз знаний. 2. Логическое программирование и базы данных. 934 Часть р. дополнительные аспекты 3. Архитектуры экспертных баз данных, инструменты и методы. 4. Логические рассуждения в экспертных системах баз данных. 5. Доступ к интеллектуальным базам данных и взаимодействие с ними. Кроме того, имеется ведущая статья Джона Смита ()оЬп Бгп!1Ь) по экспертным системам баз данных и отчеты рабочей группы по системам управления базами знаний, логическому программированию и базам данных, объектным системам баз данных и системам знаний.
Как указывает в предисловии редактор этой публикации, концепция экспертной системы базы данных "подразумевает различные определения и, бесспорно, различные архитектуры". 23.7. М!и!сег Л (еб.). Роцпбайопз ой Оебцсг!че ОагаЬазез апг! Ьой!с Ргойгащщ!п8. — Зап Магео, Сайй: Могйап Кацйпапп, 1988. 23.8. Му!оров!оз 1., Вгоб!е М.Ь, (ег!з). Кеаг!!пйз !и Ап!йс!а1 !пге!!!8епсе апб ОагаЬазез.— Бап Мазеп, СайГ.: Могцап Кацйпапп, 1988. 23.9.
Ы!!щап 1.О, ОагаЬазе апб Кпозч)ебйе-Вазе Буьчегпз, В 2-х томах. — Кос1сч!1!е, Мб: Сощрцгег Бс!епсе Ргезз, 1988, 1989. Одна из десяти глав первого тома целиком посвящена логическим методам. В этой большой по объему главе (в которой впервые был представлен язык Оага!ой) обсуждается связь между логической и реляционной алгеброй, а также реляционное исчисление в виде особого случая логического подхода в версии как для доменов, так и для кортежей. Второй том состоит из семи глав, пять из которых посвящены различным аспектам логических СУБД.
23.10.Оагбаг!и О., Ча!бцг!ех Р. Ке1аг!ода! ОагаЬазез апг! Кпож!ебйе Вазез.— Кеаг!!п8, Мазал Аг!г!!зоп-%ез!еу, 1989. В книге имеется глава, посвященная дедуктивным системам, в которой несмотря на вводный характер изложения содержатся сведения о теории таких систем, об алгоритмах оптимизации и т.д., причем в гораздо большем объеме, чем в данной главе. 23.11.8гопеЬга1гег М. 1пггобцсг!оп го "!пгебгагюп оТКпоъч!ес$8е апс$ Оага Мапайешепг" // М. Бгопеьгакег (егь). Веаб!пйз !и Оагаьазе Зузгешз.— Бап магео, саййл могйап Кацйпапп, 1988. 23.12.Оа1!а!ге Н., М|п1сег 1., Ьйсо!аз 1.-М. Ьой!с апб ОагаЬазез: А Оебцсг!че АрргоасЬ // АСМ Сощр. Бцгч.
— )цпе, 1984. — 16, № 2. 23.13.ОаЫ Ч. Оп ОагаЬазе Бузгешз Оече!оршепг гйгоцйй Ьой!с // АСМ ТООБ. — МагсЬ, 1982. — 7, № 1. Хорошее и ясное описание идей, лежащих в основе логических СУБД, с примерами, созданными автором на базе языка Рго1о8 в 1977 году. 23.14.А8газча1 К.
А!рйа; Ап Ехгепгйоп ой Ке)аг!опа! А!8еЬга го Ехргеав а С!азз ой Кесцгз!че Оцег!ез //1ЕЕЕ Тгапзасйоп оп Бойваге Епй!пеепп8. — )ц1у, 1988. — 14, № 7. Здесь предлагается новый оператор а/р/га, с помощью которого в рамках традиционной реляционной алгебры поддерживается формулировка "большого класса рекурсивных запросов" (в действительности — надмножество линейных рекурсивных запросов).
Существует мнение, что оператор а/р/га является достаточно мощным для решения многих практических проблем, включая рекурсию, и более простым в применении по сравнению с другими общими механизмами рекурсии. В Глава 23. Логические системы управления базами данньп 935 книге приводная несколько примеров его использования.
В частности, показано, как могут обрабатываться задачи транзитивного замыкания и "обобщенных требований" (см. соотве~с~венно публикацию [23,17] и раздел 23.6). Материал по этой теме содержится также в публикациях [23.18] и [23.! 9]. 23.15.Ке(сег К. Точгагс)з а Ьой(сас Кесопзсгцспоп ос Кесапопа! РасаЬазе ТЬеогу й Оп Сопсерша1 Мос(е!11п8: Регзресс]чез (гоги Агс!Веса! 1псесййепсе, РасаЬазез, апсс Ргойгапнп1п8 Ьапйца8ез (ейь М.1.. Вгойе, 1.
Му!оров!оз, 2%. 5сйсп!с)с). — Хеся Уог1с, Х.Ул 5рйпйег-Чегса8, 1984. Как уже отмечалось в разделе 23.2, хотя работа Рейтера и является первоисточником в этой области, многие исследователи до него изучали связь между логикой и базами данных (см., например, [23.5], [23.7] и [23.13]). Однако, по всей вероятности, именно "логическая реконструкция реляционной ~сории" значительно повысила интерес к предмету и побудила к активным исследованиям в этой области. 23.!6.Валс!1Ьоп Р., Каша)сг!зйпап К. Ап Ашасецг'з 1псгодцсбоп со Кесцгяче Овесу Ргосезяпй 5сгасе8!ез Л Ргос. 1986 АСМ 51ОМОР 1пс. Сопб оп Мапа8еспепс оТ Раса.
— Фазй!п8соп, Р.С., 1986. (В переработанном виде опубликована в сборнике М. 5сопеЬгассег (ей). Кеас!1пйз сп РасаЬазе 5узсешз.— 5ап Масео, СаИл Могйап Кацбпапп, 1988, а также в [23.8].) Прекрасный обзор положительных и отрицательных сторон существующих методов решения проблемы реализации рекурсивного запроса. Положительно оценивается наличие множества технологий, разработанных для решения этой проблемы, а отрицательно — трудности выбора технологии, наиболее подходящей для конкретной ситуации (в частности, многие технологии представлены без описания характеристик производительности).
После описания основных идей логических баз данных в статье предлагается множество алгоритмов — наивное и полунаивное оценивание, итерационные запросы и подзапросы, рекурсивные запросы и подзапросы, АРЕХ, язык Рго!о8, алгоритмы Хеншена/Нэкви, АхоУльмана, Кифера-Лозинского, вычислительный алгоритм, магические множества и их обобщение. Сравниваются различные подходы на основе домена приложения (т.е. класса проблем, для которых применяется данный алгоритм), производительности и простоты их реализации.
В статье также приводятся показатели производительности (со сравнительным анализом), полученные в резуль~ате проверки различных алгоритмов на основе простого теста. 23.17.1оаппЫ!з У.Е. Оп сйе Согпрцсабоп ос сйе Тгапяцче Ссозцге ог" Ке!асюпа! Орегасогз й Ргос. 12Й |пС. Сопб оп Чету 1.агйе Раса Вазез. — Куосо, )арап, Ацйцзс, 1986. Транзитивное замыкание является операцией фундаментального значения при обработке рекурсивного запроса [23.! 8]. В статье предлагается новый алгоритм реализации этой операции (основанный на полходе типа "разделяй и властвуй").
Об этом также речь идет в работах [23.14], [23.18] — [23.20], [23.49], [23.50]. 23.18.)айайьй Н.Ч., Айгаскас К., Хеьз 1.. А Бшду ос Тгапяйче С!озцге аз а Кесогяоп Месйапйш й Ргос. 1987 АСМ ЯОМОР 1пс. Сопб оп Мапайеспепс ос Раса. — 5ап ГгапсВсо, СаИ., Мау, 1987. Немного переработанная цитата нз аннотации: "В этой статье показано, что каждый линейный рекурсивный запрос может быль выражен в виде транзитивного замыкания, которое начинается и завершаешься операциями, уже существующими в 936 Часть г'.
Дополншпельньсе аспекты реляционной алгебре". В статье также делается предположение, что для эффективной реализации линейной рекурсии в общем случае, а значит, и для создания эффективных дедуктивных СУБД лля большого класса рекурсивных проблем достаточно обеспечить эффективную реапизанию транзитивного замыкания. 23.19.А8гагча1 К., Зайаб!зЬ Н. Р!гесс А18ог!йгпз Гог Сошрпс!п8 йе Тгапгййче С)оввге оГ РасаЬазе Ке!асюпз // Ргос 1Зй 1пс. СопГ. оп Чету Ьагйе Раса Вазез. — Вг!8Ьсоп, \3К, 5ерсетЬег, ! 987.
Предлагается набор алгоритмов для транзитивного замыкания, которые "не представляют задачу как вычисление рекурсии, а получают замыкание, опираясь на исходные принципы" (отсксда и определение аугесг — "непосредственный" ). В статье также содержится полезное резюме предыдущих работ по другим алгоритмам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
