2015-07-03
4949
В следующих упражнениях вам предлагается по словесному запросу к базе данных поставщиков и деталей составить соответствующее алгебраическое выражение или последовательность реляционных операций присвоения (на ваш выбор), необходимых для выполнения этого запроса. Если понадобится, можно также использовать реляционные сравнения. Для удобства ниже повторно приводится (в общих чертах) структура базы данных:
S (S#, SNAМE, SТAТUS, CIТY)
PRIМARY КЕУ (S#)
Р (Р#, PNAМE, COLOR, WEIGНТ, CIТY)
PRIМARY КЕУ (Р#)
J (J#, JNAМE, CIТY)
PRIМARY КЕУ (J#)
SPJ (S#, Р#, J#, QTY)
PRIМARY КЕУ (S#, Р#, J#)
FOREIGN КЕУ (S#) REFERENCES S
FOREIGN КЕУ (Р#) REFERENCES Р
FOREIGN КЕУ (J#) REFERENCES J
6.13. Получить полную информацию обо всех проектах.
6.14. Получить полную информацию обо всех проектах в Лондоне.
6.15. Получить номера поставщиков, которые обеспечивают проект J1.
6.16. Получить все отправки, где количество находится в диапазоне от 300 до 750 включительно.
6.17. Получить все сочетания "цвета деталей - города деталей".
6.18. Получить все такие тройки “номера поставщиков-номера деталей -номера проектов", для которых выводимые поставщик, деталь и проект размещены в одном городе.
6.19. Получить все такие тройки "номера поставщиков-номера деталей -номера проектов", для которых выводимые поставщик, деталь и проект не размещены в одном городе.
6.20. Получить все такие тройки "номера поставщиков-номера деталей--номера проектов", для которых никакие из двух выводимых поставщиков, деталей и проектов не размещены в одном городе.
6.21. Получить номера деталей, поставляемых поставщиком в Лондоне.
6.22. Получить номера деталей, поставляемых поставщиком в Лондоне для проекта в Лондоне.
6.23. Получить все пары названий городов, для которых поставщик из первого города обеспечивает проект во втором городе.
6.24. Получить номера деталей, поставляемых для всех проектов, обеспечиваемых поставщиком из того же города, где размещен проект.
6.25. Получить номера проектов, обеспечиваемых по крайней мере одним поставщиком не из того же города.
6.26. Получить все такие пары номеров деталей, которые обе поставляются одновременно одним поставщиком.
6.27. Получить общее число проектов, обеспечиваемых поставщиком S1.
6.28. Получить общее количество деталей Р1, поставляемых поставщиком S 1.
6.29. Для каждой детали, поставляемой для проекта, получить номер детали, номер проекта и соответствующее общее количество.
6.30. Получить номера деталей, поставляемых для некоторого проекта со средним количеством больше 320.
6.31. Получить имена проектов, обеспечиваемых поставщиком S1.
6.32. Получить цвета деталей, поставляемых поставщиком S1.
6.33. Получить номера деталей, поставляемых для какого-либо проекта в Лондоне.
6.34. Получить номера проектов, использующих, по крайней мере одну деталь, имеющуюся у поставщика S 1.
6.35. Получить номера поставщиков, поставляющих по крайней мере одну деталь, поставляемую по крайней мере одним поставщиком, который поставляет по крайней мере одну красную деталь.
6.36. Получить номера поставщиков со статусом, меньшим чем у поставщика S 1.
6.37. Получить номера проектов, город которых стоит первым в алфавитном списке городов.
6.38. Получить номера проектов, для которых среднее количество поставляемых деталей Р1 больше, чем наибольшее количество любых деталей, поставляемых для проекта J 1.
6.39. Получить номера поставщиков, поставляющих деталь Р1 для некоторого проекта в количестве, большем среднего количества деталей Р 1 в поставках для этого проекта.
6.40. Получить номера проектов, для которых не поставляются красные детали поставщиками из Лондона.
6.41. Получить номера проектов, полностью обеспечиваемых поставщиком S 1.
6.42. Получить номера деталей, поставляемых для лондонских проектов.
6.43. Получить номера поставщиков, поставляющих одну и ту же деталь для всех проектов.
6.44. Получить номера проектов, обеспечиваемых по крайней мере всеми деталями поставщика S 1.
6.45. Получить все города, в которых расположен по крайней мере один поставщик, одна деталь или один проект.
6.46. Получить номера деталей, поставляемых либо лондонским поставщиком, либо для лондонского проекта.
6.47. Получить пары "номер поставщика-номер детали", такие, что данный поставщик не поставляет данную деталь.
6.48. Получить все пары номеров поставщиков, скажем, Sx и Sy, такие, что оба эти поставщика поставляют в точности одно и то же множество деталей. (Выражаю благодарность г-ну Фатма Мили (Fatma Mili) из Окландовского Университета (Рочестер, Мичиган), предложившему эту задачу.)
Список литературы.
6.1. Codd E.F. А Relational Model of Data for Large Shared Data Ваnks // САСМ. - 1970. - 13, №6. (Переиздано: Milestones of Research - Selected Papers 1958-1982 (САСМ 25th Anniversary Issue) // САСМ. - 1983. - 26, № 1.)
Первая статья Кодда о реляционной модели, в которой даны определения алгебраических операций, перечисленных ниже. Интересно отметить, что определения выборки и соединения отличались от современных определений, а список операций включал операции связи и композиции, которые в настоящее время редко используются. Далее предполагается, что Х, У и т.д. представляют атрибуты или при необходимости сочетание атрибутов.
n Операция перестановки - переупорядочение атрибутов отношения слева направо; эта операция предназначалась для использования исключительно на внутреннем уровне системы, поэтому, естественно, такое упорядочение атрибутов не имеет никакого отношения к пользователю.
n Операция выборки - для данных отношений А {Х, У} и В {У} выборка из отношения А по В определяется как такое максимальное подмножество отношения А, что А [У]будет подмножеством (не обязательно собственным подмножеством) отношения В.
n Операция проекции более или менее соответствует сегодняшнему представлению.
n Несколько видов операции соединения (рассматриваются ниже).
n Операция связи - дано отношение A {X1,X2,...,Хn},связью отношения А будет выборка кортежей отношения А, для которых A[Xn]=A[X1] - выборка в том смысле, в каком этот термин использовался в данной главе, а не в смысле приведенного выше определения.
n Операция композиции - для данных отношений А {Х, У} и В {У, Z} композиция отношений А и В представляет собой проекцию по множеству атрибутов {Х;Z} некоторого соединения отношения А с отношением В по атрибуту У.
Уточним некоторые вопросы относительно операции соединения. Даны отношения А {Х, У} и В {У,Z}, в статье соединение отношений А и В определяется как отношение С{Х, У, Z}, такое, что С[X;Y]= А и C[Y,Z]= B. Естественное соединение (называемое в статье линейным естественным соединением для того, чтобы отличать его от другого вида соединения, называемого в статье циклическим соединением) - это важный частный случай, и он в общем не является единственно возможным. Заметьте, что θ -соединения (в отличие от "линейных" соединений), т.е. соединения, в которых используются операторы скалярного сравнения, отличные от оператора "равно", не рассматриваются.
6.2. Codd E.F. Relational Completeness of Data Base SubIanguages // Data Base Systems, Courant Computer Science Symposia Series 6. - Englewood Cliffs, N.J.: Prentice-Hall, 1972
Статья включает формальное определение исходной версии реляционной алгебры, которая близка к версии, рассмотренной в настоящей главе. Определены операторы объединения, пересечения, вычитания, расширения, декартова произведения, проекции, е-соединения (и естественного соединения), деления и θ -выборки. Ниже приведены принципиальные различия в определениях статьи и рассмотренной в этой главе версии.
n Операция проекции: в статье для данного атрибута исходного отношения допускается любое число вхождений в результирующее отношение (а не ограничивается одним вхождением).
n Операция выборки: в статье допускается произвольное скалярное сравнение двух значений атрибутов (в более общем случае - двух подкортежей) данного кортежа, но не разрешается сравнение значения атрибута такого кортежа с литералом.
n Наименование атрибута: вопрос об именах атрибутов результирующего отношения в статье не обсуждается совсем. Предполагается, что атрибуты отношения упорядочены слева направо и, следовательно, могут быть идентифицированы по их порядковому номеру в соответствии с расположением.
n Дополнительные сведения: в статье не обсуждаются операции EXTEND, SUMMARIZE, реляционные сравнения и операции обновления.
6.3. Darwen Н. Private communication. - 1992.
Предлагается обобщенная версия операции SUMMARIZE, которая решает определенные проблемы, рассмотренные в этой главе. Основная идея заключается в замене заключенного в круглые скобки списка атрибутов в операторе ВУ реляционным выражением
SUMMARIZЕ term ВУ relаtional - expression
ADD aggregate- expression АS attribute
Например:
SUMMARIZЕ SP ВУ S [ S# ] ADD COUNT АS NP
Здесь результат включает кортеж для поставщика S5 с количеством, равным нулю. В общем выражение
SUMMARIZЕ SP ВУ S [ S# ] ADD exp АS Z
определяется следующим образом:
n Отношение В должно быть совместимо по типу с некоторой проекцией отношения А, т.е. каждый атрибут отношения В должен быть атрибутом отношения А. Пусть атрибутами такой проекции будут А1, А2,..., Аn.
n Заголовок результата содержит все атрибуты отношения В плюс новый атрибут Z.
n Заголовок результата содержит все такие кортежи t, которые являются кортежами отношения В, расширенного значением для нового атрибута Z; это новое значение атрибута Z подсчитывается вычислением итогового выражения ехр по всем кортежам отношения А, которые имеют те же самые значения для атрибутов А1; А2,..., Аn, что и кортеж t
Основное различие между пересмотренным оператором SUММARIZE и версией, описанной выше в этой главе, состоит в том, что результат имеет то же самое кардинальное число, что и отношение В. Но когда возможны следующие ситуации:
n Если множество всех кортежей отношения А, которые имеют те же самые значения для атрибутов А1; А2,..., Аn, что и кортеж t, пустое, то итоговое выражение ехр будет применяться к пустому множеству значений. Как уже указывалось в этой главе, для функций COUNT И SUM результат будет равен нулю. Для функции МАХ он будет равен "минус бесконечности" (где "минус бесконечность" - это наименьшее значение в соответствующем домене). Для функции МIN он будет равен "плюс бесконечности" (определяется аналогично). Для функции AVG будет возникать исключительная ситуация.
n Если отношение В не просто совместимо по типу с некоторой проекцией отношения А, а фактически является такой проекцией, как в примере
SUММARIZE SP BY SP [ S# ] ADD COUNT AS NP
то мы фактически возвращаемся к первоначальному оператору SUММARIZE.
В частности, обратите внимание, что с этой пересмотренной формой оператора SUММARIZE операция
SUММARIZE SP BY TAВLE_DEE ADD SUМ (QTY) AS GRANUTOTAL
будет выполняться, т.е. возвращать корректный ответ, а именно нуль, даже если отношение SP будет пустым (сравните ситуацию с оператором SUММARIZE, описанную в настоящей главе). См. главу 4, где обсуждается отношение TAВLE_DEE.
6.4. Darwen Н., Date C.J. Into the Great Divide // C.J. Date and Hugh Darwen. Relational Database Writings 1989-1991. - Reading, Mass.: Addison-Wesley, 1992.
Оператор деления, как определено выше в этой главе, применяется к делимому отношению и отношению-делителю, которые удовлетворяют следующему требованию: заголовок делителя является собственным подмножеством отношения делимого. В этой статье (благодаря Стефану Тодду) обсуждается обобщение оператора деления, который применяется к любой паре какого бы то ни было отношения. Такой оператор определяется следующим образом. Для данных отношений А {Х, У} и В {У, Z} выражение
А DIVIDEВY В
дает отношение с заголовком {Х, Z} и телом, состоящим из всех кортежей {Х:х, Z:z}, таких что кортеж {Х'х, У:у} содержится в отношении А для всех кортежей { У:у, Z:z}, содержащихся в отношении В. Предположим, например, что у нас есть два отношения (SP{S#, Р#} и PJ{P#, J#}), где SP показывает, какими поставщиками какие детали поставляются, а РJ показывает, какие детали в каком проекте используются. Тогда выражение
SP DIVIDEВY PJ
дает отношение с заголовком {S#, J#}, показывающее такие пары номеров поставщиков и номеров проектов, в которых указанный поставщик поставляет все детали, используемые в указанном проекте. Более того, выражение
PJ DIVIDEВY SP
дает отношение с заголовком {J#, S#}, показывающее такие пары номеров проектов и номеров поставщиков, в которых указанный проект использует все детали, поставляемые указанным поставщиком.
По крайней мере, так было задумано. В статье показано, что ни первоначальная версия операции деления Кодда, ни обобщенная версия Тодда не дают полного решения проблемы (данные выше описания двух выражений DIVIDEBY нельзя назвать исчерпывающими). В статье также показано, что деление Тодда не является в полной мере совместимым дополнением деления Кодда; более того, если эти операторы усовершенствовать так, чтобы они могли решать поставленные задачи, то их нельзя будет назвать операторами "деления"!
Чтобы разобраться, почему оператор DIVIDEBY полностью не решает проблему, для решения которой он предназначался, давайте возвратимся к первоначальной версии оператора, предложенной Коддом. Рассмотрим запрос
"Получить номера поставщиков, которые поставляют все фиолетовые детали". Предположим, что отношение РР - выборка из отношения деталей содержащая лишь кортежи фиолетовых деталей, - уже построено. Тогда запрос выражается следующим образом:
SР [ S#, P#] DIVlDEВY РР [ P# ]
Теперь предположим (и это действительно соответствует нашим примерным данным), что фиолетовых деталей нет и отношение РР пустое, а значит, будет пустой и проекция этого отношения по атрибуту Р#. Но, если фиолетовых деталей нет, значит, каждый поставщик поставляет их все - даже поставщик S5 в наших примерных данных, не поставляющий деталей вообще! А поставщики, не поставляющие деталей, не представлены в отношении SP, значит, получить результат, включающий таких поставщиков, с помощью операции DIVIDEBY невозможно.
Эту проблему можно решить, определив новый оператор "деления по". Пусть отношения А, АВ и В имеют соответственно заголовки {Х}, { Х, У} и {У}. Тогда частным деления А на В по АВ (оператор А DIVIDEВY В PER АВ) будет отношение с заголовком {Х} и телом, состоящим из всех кортежей {Х:х},таких что кортеж {Х:х, У:у}принадлежит АВ Для всех кортежей {У:у}, принадлежащих В, или в сокращенной форме:
А.Х WНERE FORALL В EXISТS АВ (А.Х = АВ.Х AND АВ. У = В. У)
(операторы FORALL и EXISТS разъясняются в главе 7). Теперь запрос "Получить номера поставщиков, которые поставляют все фиолетовые детали" можно выразить просто (и корректно):
S [ S# ] DIVIDEBY РР [ P# ] PER SР [ S#, P# ]
Таким образом решается проблема операции деления, предложенной Коддом. Решение проблемы деления по версии Тодда аналогично.
Замечание. Очевидно, можно было бы расширить определение оператора "деления по", чтобы заголовки могли быть надмножествами {Х}, {Х,У} и {У} соответственно. Однако здесь это обсуждаться не будет.
6.5. Goldstein R.C., Strnad A.J. Тhе MacAIMS Data Management System //Рrос. 1970 АСМ SICFIDET Workshop оn Data Description and Access. - 1970.
6.6. Strnad A.J. Тhе Relational Аррrоасh to the Management of Data Bases // Рrос. IFIP Congress. - Ljubljana, Yugoslavia, 1971.
Система MacAIMS [6.5,6.6] - один из самых ранних примеров системы, поддерживающей n-арные отношения и языки уровня множеств. Она использует алгебраический язык и обладает двумя весьма интересными особенностями.
n Структура хранения может быть разной для хранимых отношений. Каждый тип структуры управляется компонентом, называемым "модулем реляционной стратегии", специальным для такой структуры, которая скрывает детали хранения от других частей системы (и конечно, от пользователя).
n Атрибуты хранились как "множества элементов данных". Каждому элементу данных (т.е. значению атрибута) присваивается уникальный ссылочный номер, а все ссылки к элементам данных внутри отношения осуществляются через ссылочный номер. Алгоритм присвоения ссылочных номеров следующий: если а и Ь принадлежат одному и тому же множеству элементов данных, тогда ссылочный номер для а будет больше для Ь, если и только если а больше, чем Ь. Вследствие этого любая операция сравнения между двумя элементами данных (из того же самого множества элементов данных) может быть выполнена непосредственно на соответствующих ссылочных номерах; кроме того, само реальное сравнение, вероятно, более эффективно, поскольку ссылки имеют фиксированную длину, в то время как элементы данных могут иметь и переменную длину. Этот момент особенно важен с учетом того, что такие сравнения являются операциями, которые, наверняка, наиболее часто выполняются внутри этой системы (как, вероятно, и во всякой системе баз данных).
6.7. Notley M.G. Peterlee IS/1 System // IBМ (UK) Scientific Centre Report UKSC-0018. - 1972.
См. комментарии к [6.8].
6.8. Todd S.J.P. The Peterlee Relational Test Vehicle - А System Overview // IBM Sys. J. - 1976. -15, № 4.
Peterlee Relational Test Vehicle (PRTV) - это экспериментальная система, разработанная в научном центре IBM UK, Петерли, Англия. Она была разработана на основе более ранней системы IS/1 [6.7]. В ней поддерживались n-арные отношения и версия алгебры под названием ISBL (Information System Base Language - базовый язык информационных систем). Эта версия алгебры основывалась на предложениях, изложенных в [6.9]. Идеи, изложенные в этой главе относительно результирующих имен атрибутов и операторов, основанных на согласованных именах атрибутов, идут еще от алгебры ISBL и предложений статьи [6.9]. Система PRТV обладала тремя важными свойствами.
n В ней были реализованы сложные методы преобразования выражений (это еще будет обсуждаться далее в этой книге).
n Она включала средство отложенного вычисления, что важно как для оптимизации, так и для поддержки именованных виртуальных отношений (т.е.представлений).
n Она обеспечивала "функцию расширяемости", т.е. возможность расширять систему, добавляя определенные пользователем вычислительные функции.
6.9. Наll Р.А.V., Hitchcock Р., Todd S.J.P. Аn Algebra of Relations for Machine Computation // Conference Record of the 2nd АСМ Symposium оn Principles of Programming Languages. - Palo Alto, Calif., 1975.
6.10. Furtado A.L., Kerschberg L. Аn Algebra of Quotient Relations // Proc. 1977 АСМ SIGMOD Intern. Conf. оn Management of Data. - Toronto, Canada, 1977.
Представлена пересмотренная версия реляционной алгебры для оперирования непосредственно с "относительными отношениями" ("quotient relations").
Дано отношение R, относительное отношение можно получить из отношения R путем группировки его кортежей на основе некоторого его атрибута (так же, как в операторе ву операции SUMMERIZE, описанной в этой главе). Например, относительное отношение, полученное из отношения поставщиков S на основе значений атрибута CITY - это множество из трех групп кортежей: в одной содержатся два кортежа поставщиков из Лондона, в другой - два кортежа поставщиков из Парижа, в третьей - один кортеж поставщика из Атена. Авторы утверждают, что работа непосредственно с такими относительными отношениями приводит к упрощению формулировок запросов и потенциально к более эффективной реализации системы.
6.11. Merrett Т.Н. The Extended Relational Algebra, А Basis for Query Languages // В. Shneiderman (ed.). Databases: Improving Usability and Responsiveness. - New York, N.Y.: Academic Press, 1978.
Целью этой статьи является введение кванторов в алгебру - не просто исчисления кванторов существования и кванторов всеобщности (об этом в главе 7), а более общих кванторов "количество" и "соотношение". С помощью этих кванторов можно выразить такие условия, как "по крайней мере три", "не более половины", "нечетное число" и т.д.
6.12. Наll Р.А.V. Relational Algebra, Logic and Functional Programming // Рrос. 1984 АСМ SIGMOD Intern. Conf. оn Management of Data. - Boston, Mass., 1984.
В статье представлена функциональная интерпретация реляционной алгебры с целью (как говорится в статье) изложить теоретические основы так называемых "языков четвертого поколения" (4GL) и интегрировать функциональные, логические и реляционные языки таким образом, чтобы они могли совместно использовать технологию реализации. Автор утверждает, что, хотя логическое программирование и базы данных уже на протяжении некоторого времени сближаются друг с другом, во время написания функциональных или аппликативных языков мало обращается внимания на требования баз данных или технологии. Поэтому статья главным образом вносит вклад в сближение между ними.
6.13. КIug А. Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions // JACM. - 1982. - 29, № 3.
В статье определяется множество расширений реляционной алгебры и реляционного исчисления для включения поддержки итоговых функций (для алгебры это нечто подобное оператору SUММARIZE, описанному выше в этой главе) и демонстрируется равносильность двух расширенных языков.
