Введение в системы БД (542480), страница 246
Текст из файла (страница 246)
23.20.Ьп Н. Хесч 5сгасе8!ез Гог Согпрвбпй сЬе Тгапсббче С1озвге оГ а РасаЬазе Ке!асюп // Ргос ! ЗсЬ 1пс. СопГ. оп Чету Ьагбе Раса Вазез. — Вг!8Ьсоп, 13К, 5ерсегпЬег, 1987. Приводится описание других алгоритмов транзитивного замыкания. Так же, как и в [23.! 9], в этой статье содержится полезный обзор разработанных ранее подходов к рассматриваемой проблеме. 23.21.Вапссйоп К, Масег Р., 5а8!ч У., (3!1гпап 3.Р. Май!с 5еса апб Ойег 5сгапйе СЧауз со 1спр!егпепс Ьой!с Ргойгашз // Ргос. 5й АСМ 51ОМОР-51ОРАСТ 5угпрозплп оп Рппсср!ез оГ РасаЬазе 5умегпз, 1986. Основная идея "магических множеств" заключается в динамическом введении нового набора "магических" правил, которые гарантируют получение того же результата, что и оригинальный запрос, но гораздо эффективнее эа счет сокращения числа "необходимых фактов" (см. раздел 23.7).
Изложение подробностей несколько сложно для восприятия и выходит за рамки данного комментария. Читателю предлагается прочесть эту статью или обратиться к работам [23.9], [23.10], [23.!6], чтобы получить более подробные сведения. Однако следует отметить, что существуют также многочисленные варианты этой основной идеи [23.22] — [23.24]. Кроме того, следует учесть работы [17.24]-[17.26], указанные в главе 17. 23.22.Вееп' С., Каспа)сг!зЬпап К. Оп йе Росчег оГ Марс 0 Ргос. бй АСМ 5!ОМОР- 5!ОРАСТ 5угпроз!шп оп Ргшс!р1ез оГРасаЬазе 5узсетз, 1987.
23.23.5асса Р., Хап!о!о С. Мабге Своп!!п8 Мейобз // Ргос. 1987 АСМ 5!ОМОР 1пс. СопГ. оп Мапайегпепс оГ Раса. — 5ап Ргапсйсо, Са)сТ., Мау, 1987. 23.24. Оагбапп О, Марс Твпсбопз; А ТесЬпк!пе со Орс!гп!хе Ехсепбеб Раса!о8 Кеспсз!че Ргорагпз // Ргос. ! Зй 1пс. СопГ оп Чесу Ьскбе Раса Вазев — Вп8Ьсоп, ЬСК, 5ерсеспЬег, 1987, 23.25.АЬо А., ЬС!!гпап 3.Р. С)п!чегза)!су оГ Раса Кеспеча! Ьапйнайез // Ргос. бй АСМ 5ущрояшп оп Рппсср)ез оГ Рго8гаппп!п8 Ьапйпайеа.
— 5ап АпСопю, Техаз, 1979. Для данной последовательности отношений Я, Г(й), Г(Г(Я) ), ... (где à — некоторая фиксированная функция) крайней точкой неизменности называется отношение В*, выведенное в соответствии со следующим алгоритмом наивного опенивания (см. ридел 23.7). й* с=8 бо ппШ К* вборв 9гонсп9 ; /* ввполнять, пока Н* не достигнет "точки неизменности" "/ й* с= Н* С)8108 Г(й*) епб ; Глава 23. Логические системы управления базами данньсх 937 В этой статье описываешься дополнение реляционной алгебры поня~нем "крайняя точка неизменности".
23.26Л31!гпап 3.Р. !гпрсегпепсабоп оС' Ьо81сас Оцегу Ьап8цайев сйг РасаЬавев й АСМ ТОРЯ. — 5ерсегпЬег, 1985. — ! О, № 3. Описывается важный класс технологий реализации возможных рекурсивных запросов. Методы определены в терминах "правил сбора" на "деревьях правил/целей", которые являются графами, представляющими некоторую стратегию запроса в терминах предложений и предикатов. В ста~ье определено несколько таких правил: одно из них соответствует приложению операторов реляционной алгебры, два больше соответствуют прямому формированию цепочки, а "косвенное" правило позволяет передавать результаты от одной подлели к другой. Косвенная передача информации затем становится основой для так называемых методов магических миолсеств 123.211-[23,24).
23.27.Твцг Б., гап!о!о С. ЬРЬ: А Ьой!с-Вавес! Раса-1.апйнайе 33 Ргос. ! 2сй |пс. Сопб оп Чету 1.агйе Раса Вавев. — Куосо, 3арап, Ацйця, 1986, Язык ЬРЬ включает генератор типа "множества*', отрицание (основанное на различиях множеств), операции определения данных и операции обновления. Это язык логического типа (нет никаких зависимостей упорядочения между утверждениями), причем компилируемый, а не интерпретируемый. Материал по этой теме можно также найти в !23.45). 23.28.Вапс!!Ьоп Г.
Ха!че Еча!цайоп об Кесцгяче Рейпед Ке!айова!3 М. Вгобсе апс! 3, Му!оров!ов !ес!в): Оп Кпочч!ес)8е Вазе Мапайегпепс 5увсегпв: 1псейгайп8 РасаЬаве апс! А! Бувсегпв. — Ыесч Уогк, Ы. г'.: Брг!пйег-Чег!а8, 1986. 23.29 Ьокспвк!! Е.Ь. А РгоЫеш-Опепсес$ !пГегепс!а! РасаЬаве 5уяет 33 АСМ ТОРБ.— БерсегпЬег, 1986. — 11, № 3. Первоисточник концепции "необходимых фактов'*. В статье описывается прототип системы, в которой применяется экстенсиональная база данных для компенсации очень быстрого расширения поискового пространства вследствие использования инференциальных технологий. 23.30.Ковепсйа1 А. ес а1.
Тгачегва! Кесцгяоп: А Ргасссса! АрргоасЬ со 5цррогйп8 Кесцгяче Арр!!сасюпв 33 Ргос. 1986 АСМ 51ОМОР 1пс. Сопб оп Мапа8егпепс оГ Раса.— ФавЫпйсоп, Р.С., 3ипе, 1986. 23.31.Оагс1апп О., Ре Ма!пс)геч11!е С, Еча!цас!оп об РасаЬаве Кесцгяче 1.о8!с Ргойгагпв ав Кеснпепс Рцпсйоп 5епев 33 Ргос. 1986 АСМ 51ОМОР 1пс. Сопб оп Мапайешепс оГ Раса.
— %авйп8соп, Р.С., 3цпе, 1986. 23.32.КавсЬ!с) Ь., Вц 5. г'.%. А Рагайес Ргосевяпй 5сгасейу Рог Еча!цайп8 Кеснгяче Оцег!ев 33 Ргос. 1238 !пс. Сопб оп Чету 1.агйе Раса Вавев. — Куосо, 3арап, Ацйцвс, 1986. 23.33.5ругасов ЬЬ ТЬе Рапгйоп Могсе!: А Рес!нсссче РасаЬаве Мос)е1 0 АСМ ТОР5.— МагсЬ, 1987. — 12, № 1. 23.34.Нап 3., НепвсЬеп Ь.3. Напсс!!п8 КесСцпссапсу !п сЬе Ргосевяпй ор Кесцгвгче Оцег!ев 33 Ргос. 1987 АСМ 5!ОМОР !пСегп. Сопб оп Мапайегпепг оС' Рага. — 5ап Ггапсйсо, Са!!Г., Мау, 1987. 23.35.г.Ьап8 %,, Чц С.Т. А )чесеввагу Сепг!!с!оп Рог а РоцЫе Кесцгв!че Кисе со Ье Ес!ц!ча!епс со а 13пеаг Кесцгяче Ки!е 33 Ргос.
1987 АСМ 51ОМОР!псегп. Сопб оп Мапайегпепс оГ Вага. — 5ап Ггапс!всо, Са!!С'., Мау, 1987. 938 Часть 3г. Дополнительные аспекты 23.36. !чей %. Кесцгяче Бгга!е8!ез Рог Апззчег!п8 Кесцгз№е Оцебез — ТЬе КОА/РО! Бггагейу Н Ргос. 1ЗгЬ!пгегп. Сопб оп Чету 1.агйе Рага Вазез. — Вг18Ыоп, 13К, БергевЬег, ! 987. 23.37.%Ьап8 К.-У., Хача!Ье Б.В. Ап Ехгепг!еб ОВ3ппсйче Ыоппа! Ропп АрргоасЬ аког Орйпййп8 Кеспгяче Ьой!с Оцеиез !п Ьоозе1у Совр!ег! Епч!гопвепгв // Ргос. 13й 1вегп. Сопб оп Чегу 1.агйе Рага Вазез. — ВПБЬгоп, 13К, БергепзЬег, 1987.
23.38.Хац8Ь!оп 3.Г. Совр!!!п8 БерагаЫе Кесцгзюпз // Ргос. 1988 АСМ Б1ОМОР 1пь Сопб оп Мапайевеп! оТОага. — СЫса8о, 111., 3цпе, 1988. 23.39Лоцп С., НепзсЬеп Ь.3., Нап 3. С!азябса!юп оТ Кеспгз!че Роппц!аз ш Оебцсиче ОагаЬазез Н Ргос. 1988 АСМ Б1ОМОО 1пг. Сопб оп Мапа8евепг оР Рага. — СЫса8о, П!., 3цпе, 1988. 23.40. Сег! Б., Ооп!оЬ О., Ьачагга 1.. Тгапз!айоп апг! Орйп!гаг!оп ой о8!с Овес!аз: ТЬе А18еЬга1с АрргоасЬ // Ргос. 12й !пь Сопб оп Чегу Ьвгйе Оага Вазев. — Куою, !арап, АцйцзЬ 1986.
23.41.Сег1 Б., Таиса Ь. Орйв!гайоп оТ Буяевз оТ А!8еЬга!с Еопаг!опз Рог Еча1ца!!п8 Рага1о8 !апет!ез // Ргос. 13й!пг. Сопб оп Чесу 1.аг8е Рага Вавез, — ВПБЫоп, 1ЗК, БергевЬег, 1987. 23.42. Чап Ое!бег А. А Меввайе Разя!п8 Ргавеюогк Тог Ьой!са! !снегу Еча!цагюп // Ргос.
1986 АСМ Б!ОМОО !пг. Сопб оп Мапа8евепг оТРага. — %азЫп8!оп, О.С., 3цпе, 1986. 23.43.%о!акоп О., Я1Ьегзсйагг А. Р!згг!Ьцгеб Ргосезяпй об Ьой!с Ргойгавв // Ргос. 1988 АСМ ЯОМОО!пг. Сопб оп Мапайевепг оРОага. — СЫсайо, 1П., 3ппе, 1988. 23.44.Ыац8Ьгоп 3.Р. е! а!. Ей!с!ел! Еча!ца!юп оТК!8Ь1-, Ьейь апб Мц!ВВЫпеаг Кц1ез // Ргос. 1989 АСМ ЯОМОР 1пп Сопб оп Мапа8евепг оТ Оага. — Рог!!апб, Оге., 3цпе, 1989.
23.45.Ыаоч! Б., Тзцг Б. А Ьой!са! Ьапйцайе Тог Раса апб Клочч1е68е Вазез. — 1чечг уотерс., Ы.У.: Совршег Бс1епсе Ргезз, 1989. Эта книга полностью посвящена языку ЬРЬ ~23.27!. 23.46.Себ Б., Ооп!оЬ О., Тапса 1-. Ьой!с Ргойгавпипй апй Оа!аЬазез. — Хечч Уогк, Ы.У.: Брбпйег-Чег!а8, 1990. 23.47.Раз Б.К. Ребцсг!че РасаЬазев апб Ьой!с Рго8гагппнп8. — Кеаб!п8, Маваг АгЫВоп%ез!еу, 1992. 23.48.КЕп М., Ьог!пах!! Е. Оп Совр!!е-Типе Опегу Оргии!габоп 1п Ребцсг1че ОагаЬазез Ьу Меана оТ Бгаг!с Р1!гепп8 // АСМ ТОРБ. — БергевЬег, 1990.
— 15, № 3. 23.49.А8гачга! К., Раг Б„апб 3а8аейзЬНН. 0!тес! Тгапз!г!че С!окате А!8огпЬвз: Рея8п апй Рег!оппапсе Еча1цагюп // АСМ ТОРБ. — БергевЬег, 1990. — 15, № 3. 23.50.!айаг!!зЬ Н.Ч. А Согпргеьз!оп МегЬоб го Магег!а1!ге ТгапзЫче С!окате // АСМ ТООБ. — РесевЬег, 1990. — 15, № 4. Предлагается технология индексирования, которая позволяет сохранить транзитивное замыкание данного отношения в сжатой форме таким образом, чтобы можно было выполнить тестирование и узнать с помощью одной справочной таблицы с индексом, будет ли данный кортеж находи~ься в замыкании. 23.51.АЬИеЬоц1 Б., ОгшпЬасЬ Б. А Кц1е-Вазег! Ьапйцайе ичй Рппсгюпз апб Бей // АСМ ТООБ. — Магсй, 1991.
— 16, № 1. Описывается "язык сложных объектов" 1"совр!ех оЬ3есг !апйцайе" — СОЬ), который является расширением языка Рага1о8 с интеграцией идеи дедуктивных и объектно-ориентированных баз данных, Глава 23. Логические системы управления базами данных 939 Ответы к некоторым упражнениям 23.1. а в правильное, б — правильное, в в неправильное. 23.2. В приведенных ниже выражениях а, Ь и с являются константами Сколема, а г— функцией Сколема. а)р(х, у) ~д(х, Х(х, у] ) б) р ( а, Ь ) ~ с ( а, г ] в) р ( а, Ь ) =« с ( а, с ) 23.6.
В соответствии с обычной практикой перечисленные ниже решения обозначаются как 23.б.п, где и — номер оригинального упражнения в главе 6. 23.6.13. ? «= Ю ( ?, 1л, 1с ) 23.6.14. ? «= Л ( 1, 1л, 'Ьопдоп' ) 23.6.15. КЕБ ( я ) «= БРЛ ( я, р, 'Л' ? «= КЕБ ( я ] 23.6.16.
? «= БРЛ ( я, р, 1, с ) АВР 300 < с АВР д < 750 23.6.17. КЕБ ( р1, рс ) «= Р ( р, рл, р1, и, рс ) ? ~ КЕЯ ( р1, рс ) 23.6.18. КЕБ ( я, р, 1 ) «= Я ( я, ял, яс, с ) АВР Р ( р, рп, р1, и, с ) АКР Л ( 1, ?л, с ) ? «= КЕЯ ( я, р, 1 ) 23.6.19-23.6.20. Не может быть выполнено без операции отрицания. 23.6.21. КЕЯ ( р ] «= БРЮ ( я, р, 1', с ) АВР Я ( я, ял, яс, 'Ьопдоп' ) «= КЕЯ ( р ] 23.6.22. КЕЯ ( р ) «= ЯРЛ ( я, р, ?, с ) АВР Б ( я, ял, яс, 'Ьопс]оп' ) А|Р Ю ( 1, 1л, 'Ьопс]оп' ) ? «= КЕЯ ( р ) 23.6.23. КЕЯ ( с1, с? ) «= БРЮ ( я, р, 1', с ) АКР Я ( я, ял, яг, с1 ) АВР Ю ( 1, 1'и, с? ) ? «=КЕЯ ( с1, с?) 23.6.24.
КЕБ ( р ) «= ЯРЮ ( я, р, 1, ~? ) АКР Я ( я, яп, в?., с ) АКР Л ( 1, 1л, с ) ? «= КЕЯ ( р ) 23.6.25. Не может быть выполнено без операции отрицания. 23.6.26. КЕБ ( р1, р? ) ~ ЯРЛ ( я, р1, 11, ф ) АВР Я ( я, р?, 12, д? ) ? ~ КЕБ ( р1, Р? ) 940 Часть г'. Дополнительные аспекты 23.6.27-23.6.30. Не может быть выполнено без функций группирования и функций обобщения. 23.6.3!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
