Cтраница 1
Полусоединение представляет интерес ввиду следующего его свойства: ( г [ X s) s г s ( см. упр. [1]
Полусоединения были определены в статье Bernstein, Chiu [1981], где можно найти и ответ к упр. [2]
Полусоединение представляет интерес ввиду следующего его свойства: ( гX s) х s г х s ( см. упр. [3]
Полусоединения были определены в статье Bernstein, Chiu [1981 ], где можно найти и ответ к упр. [4]
В таких случаях полусоединение может оказаться эффективным. Иногда же пол усоеди нения могут полностью заменить соединения. [5]
Но те из этих полусоединений, в результате которых происходит удаление некоторых кортежей из г -, на рассматриваемые свойства никак не влияют. [6]
SP, в свою очередь представляющий собой программу полусоединения. [7]
Понятие ациклической схемы базы данных впервые возникло в работах, посвященных операции полусоединения и сравнительному изучению свойств попарной согласованности и согласованности в целом. Первое определение полусоединения дали Холл, Хичкок и Тодд ( Hall, Hitchcock, Todd [1975]), назвавшие эту операцию обобщенным пересечением. Примерно в те же годы употреблялся и термин полусоединение, но операция, которую он обозначал, не имеет ничего общего с той, которую называем полусоединением мы. Бернштейн и Гудман ( Bernstein, Goodman [ 1979a, 1979с ]) распространили эту теорию на многоатрибутные полусоединения. [8]
Rp ], a SP ( 1) - кратчайшая из программ полусоединения для R, полных относительно G Рассмотрим программу полусоединения SP ( 1), полученную из SP ( 1) обращением порядка шагов на противоположный и заменой каждого шага rt ч - rt t rs на rj-t - rjtxri - Читателю предлагается показать, что программа полусоединения SP для R, составленная из последовательно расположенных программ SP ( 1) и SP ( 1) ( в таком порядке), является полной относительно любого Ог, 1 / р ( см. упр. Отсюда по предложению 13.5 следует, что 5Р ( rt, d) FR ( ri, d) для любого 1 /: р, и поэтому SP - программа полной редукции. Заметим, что SP содержит 2р - 2 шагов и что меньшим числом шагов обойтись нельзя ( см. упр. [9]
Понятие ациклической схемы базы данных впервые возникло в работах, посвященных операции полусоединения и сравнительному изучению свойств попарной согласованности и согласованности в целом. Первое определение полусоединения дали Холл, Хичкок и Тодд ( Hall, Hitchcock, Todd [1975]), назвавшие эту операцию обобщенным пересечением. Примерно в те же годы употреблялся и термин полусоединение, но операция, которую он обозначал, не имеет ничего общего с той, которую называем полусоединением мы. В работе Bernstein, Chiu [1981 ] впервые исследованы связи между деревьями соединений и программами полной редукции, хотя рассмотрен лишь случай полусоединений над единственным атрибутом. Бернштейн и Гудман ( Bernstein, Goodman [ 1979a, 1979с ]) распространили эту теорию на многоатрибутные полусоединения. [10]
Для каждого дерева Gt существует по крайней мере одна полная относительно него программа полусоединения для R. Ее можно построить, например, так: совершаем обход дерева Gt в обратном направлении ( от листьев к корню) и при посещении очередной вершины добавляем к нашей программе шаг, на котором вычисляется полусоединение отношения, ассоциированного с этой вершиной, и отношения, ассоциированного с ее непосредственным предком. [11]
Для каждого дерева Gt существует по крайней мере одна полная относительно него программа полусоединения для R. Ее можно построить, например, так: совершаем обход дерева Сг в обратном направлении ( от листьев к корню) и при посещении очередной вершины добавляем к нашей программе шаг, на котором вычисляется полусоединение отношения, ассоциированного с этой вершиной, и отношения, ассоциированного с ее непосредственным предком. [12]
Бернштейн и Гудман ( Bernstein, Goodman [ 1979b, 1980a ]) распространили теорию полусоединений на случай условий, включающих неравенства. В работах Chiu, Но [1980], Chiu, Bernstein, Но [1980] разработаны алгоритмы, которые по данному состоянию базы данных находят для него самую быструю программу полной редукции, - если хотя бы одна программа полной редукции для этого состояния существует. В отчетах Goodman, Shmueli [ 1980a, 1980b, 1981а, 1981 ] исследован ряд проблем относительно программ полной редукции и деревьев соединений, в том числе: построение программ редукции с помощью операций, отличных от полусоединения; неприменимость алгоритмов типа прогонки для выяснения вопроса о существовании программ полной редукции; обобщение понятий цикла и клики на случай гиперграфов; оценка сложности преобразования, превращающего циклические схемы в ациклические. [13]
Бернпттейн и Гудман ( Bernstein, Goodman [ 1979b, 1980a ]) распространили теорию полусоединений на случай условий, включающих неравенства. В работах Chiu, Но [1980], Chiu, Bernstein, Но [1980] разработаны алгоритмы, которые по данному состоянию базы данных находят для него самую быструю программу полной редукции, - если хотя бы одна программа полной редукции для этого состояния существует. В отчетах Goodman, Shmueli [ 1980a, 1980b, 1981а, 1981 ] исследован ряд проблем относительно программ полной редукции и деревьев соединений, в том числе: построение программ редукции с помощью операций, отличных от полусоединения; неприменимость алгоритмов типа прогонки для выяснения вопроса о существовании программ полной редукции; обобщение понятий цикла и клики на случай гиперграфов; оценка сложности преобразования, превращающего циклические схемы в ациклические. [14]
Таким образом, точка завершения для Rt - это тот шаг в SP, которым заканчивается вычисление полусоединения отношения, ассоциированного с Rh с отношениями, которые ассоциированы с непосредственными потомками Rt. Если в программе SP нет точки завершения для Rt относительно Git будем считать, что СР ( Ri) неопределено. [15]