Анализ вклада Кодда в Великий Спор
An Analysis of Codd's Contribution to the Great Debate
C.J. Date
()
Великий Спор являлся спором между сторонниками реляционного и сетевого подходов. Он происходил во время ACM SIGMOD Workshop on Data Description, Access, and Control в 1974 г.; основными докладчиками были Эдгар Ф. Кодд в пользу реляционного подхода (поразительно!) и Чарльз В. Бахман в пользу сетевого подхода, или подхода CODASYL. В процессе подготовки обсуждения Кодд написал статью под названием "Интерактивная поддержка непрограммистов: реляционный и сетевой подходы" [1], и именно эта статья обсуждается в данной заметке.
Замечание: официально авторами статьи числятся Кодд и Дейт, однако на самом деле статья целиком написана Коддом. (И наоборот, статья с соображениями о прикладном программировании [2], авторами которой числятся те же два автора, была написана Дейтом.)
Цели реляционного подхода
Позвольте начать с того, что думал Кодд относительно перспектив исследуемого им реляционного подхода. В ходе работы представления о перспективах изменялись. Не удивительно, что это отразилось в нескольких статьях Кодда. Например, в статье про RM/T [1] Кодд пишет: "Изначально ... реляционная модель ... рассматривалась как средство для освобождения пользователей от неприятностей, связанных с потребностью иметь дело с массой деталей представления хранимых данных". Более конкретно, а статье про Alpha [2] он обозначает следующие "принципиальные мотивы создания реляционной модели":
Независимость данных Простейшая из числа возможных структура, согласованная с семантическими соображениями Обеспечение унифицирующего принципа, упрощающего язык, требуемый для взаимодействия, и анализ операций, требуемый для авторизации доступа и оптимизации поиска Сравнительно легкий анализ согласованности [данных].
Позже в своей статье про "Великое Сражение" [3] Кодд пишет: "Реляционный подход разрабатывался как ответ на следующие требования, которые были сравнительно новыми в 1968 г.":
Независимость данных Интеграция файлов в базы данных Разнообразные типы пользователей Наличие многих терминальных пользователей с оперативным доступом к данным Возрастающий уровень совместного использования данных Сети удаленных баз данных.
В приглашенном докладе на конгрессе IFIP 1974 [4] (в том же году, когда была опубликована статья про Великое Сражение) Кодд перечисляет следующее как "цели [реляционного подхода]":
Обеспечить высокий уровень независимости данных Обеспечить спартанскую простоту представления данных, чтобы разнообразные пользователи (от новичков в области компьютеров до самых опытных) могли взаимодействовать с данными на основе общей модели (не запрещая добавлять пользовательские представления в специальных целях) Упростить потенциально огромную работу администратора базы данных Ввести теоретическую основу (хотя бы небольшую) в управление базами данных (область, в которой, к сожалению, отсутствуют надежные принципы и руководства) Объединить области выборки фактов и управления файлами, чтобы впоследствии можно было обеспечить соответствующие услуги в мире коммерции Переместить прикладное программирование с использованием баз данных на новый уровень - уровень, на котором множества (и, более конкретно, отношения) трактуются как операнды, а не обрабатываются поэлементно.
И он добавляет: "В связи со второй [ из перечисленных целей] важно помнить, что базы данных появились, чтобы приносить пользу конечным пользователям, а не для прикладных программистов, которые сегодня выступают в качестве посредников (middle-men [sic]) при удовлетворении потребностей обработки данных".
Кодд повторяет те же цели в статье про Великое Сражение и добавляет, что реляционный подход состоит из "четырех основных компонентов":
До предела упростить типы структур данных, используемых в принципиальной схеме (или общем представлении) Ввести мощные операции, обеспечивающие и программистов и непрограммистов возможностями хранения и выборки данных без потребности "навигации" [в оригинале подчеркнуто] Ввести диалоговую поддержку естественного языка (например, английского) для обеспечения эффективного взаимодействия с базой данных случайных (возможно, далеких от мира компьютеров) пользователей Выражать требования авторизации и ограничения целостности отдельно от структур данных (поскольку они подвержены изменениям).
"Обсуждения реляционного подхода часто замыкаются на первом [из этих компонентов] в ущерб остальным трем... Для обоснования этого подхода все четыре компонента должны рассматриваться в одном пакете." [3]
Наконец, в статье, написанной по поводу получения Тьюринговской премии (вполне заслуженной) в 1981 г. за работы Кодда в связи с реляционной моделью [5], он утверждает, что истинная реляционная система может:
Сделать многие приложения доступными для непрограммистов в тех случаях, когда ранее программисты бы необходимы Увеличить производительность программистов во многих (хотя и не всех) приложениях баз данных (немного перефразировано).
Мне кажется, что эти разные списки целей и связанных с ними предметов совместно составляют впечатляющее свидетельство огромных достижений Кодда. Я не думаю, что кто-либо может серьезно утверждать, что (a) какая-либо из этих целей нежелательна и (b) реляционная модель - за одним исключением - не может их достичь.Возможным исключением является "добавление впоследствии соответствующих услуг для мира коммерции". Обеспечение таких услуг все еще является (насколько мне известно) вопросом, адресуемым рынку СУБД. Тем не менее, имеются все основания считать, что реляционная модель действительно обеспечивает правильную основу для таких услуг по причине отмечавшейся в предыдущей заметке тесной связи с логикой предикатов.
Итак, что же такое реляционная модель?
В предыдущей заметке я отмечал, что, как это не странно, Кодд не определял термин "реляционная модель" до 1979 г. [1] Возможно, еще более странно, что он не определял более общий термин "модель данных" до 1981 г. ! В статье под названием "Модели данных в управлении базами данных" [6] он определяет модель данных как комбинацию трех компонентов:
Коллекции типов объектов данных, образующих базовые строительные блоки для любой базы данных, соответствующей модели Коллекции общих правил целостности, ограничивающих набор экземпляров тех типов объектов, которые законным образом могут появиться в любой такой базе данных Коллекции операций, применимых к таким экземплярам объектов для выборки и других целей (немного перефразировано).
Кстати, замечу, что здесь слово "объект" используется не в современном ограниченном смысле.
Строго говоря, такого рода замечания не слишком осмысленны. Если учесть, что отсутствует точное определение термина объект в "современном ограниченном смысле", то тем более непонятно, что означает этот термин (или это не термин?) в старом добром смысле Кодда. (Примечание С.Кузнецова.)
Далее в статье обсуждается, для достижения каких целей предназначены модели данных в целом и реляционная модель, в частности, и приводятся данные в пользу того, что - в отличие от распространенного представления - реляционная модель была в действительности первой определенной абстрактной моделью данных. (Как мы видели в предыдущей заметке, так называемые иерархическая и сетевая "модели" были определены путем абстрагирования уже существующих реализаций. Хотя интересно заметить, что сам Кодд использует словосочетание "иерархическая и сетевая модели" в двух самых первых статьях, датированных 1969-м и 1970-м годами!)
Но, видимо, возникает вопрос: "Что же в точности представляет собой реляционная модель?". Если внимательно просмотреть серию статей Кодда, то можно заметить, что его собственные определения эволюционизировали с 70-х до начала 80-х гг. (И на самом деле, изменялись.) Одним из последствий этого было то, что критики смогли обвинить самого Кодда и реляционный подход в целом в том, что "створки ворот раздвигаются" слишком сильно.
Например, Майкл Стоунбрейкер написал [7], что " можно видеть четыре разных версии" модели:
Версия 1: Определена в статье в CACM в 1970 г. [8] Версия 2: Определена в статье по поводу Тьюринговской преми в 1981 г. Версия 3: Определена 12-ю правилами Кодда и оценочной системой [9] Версия 4: Определена в книге Кодда [10].
Вероятно, по причине того, что нас немного задела такая критика, мы с Хью Дарвеном постарались привести в Третьем Манифесте свою собственную аккуратную формулировку того, что такое реляционная модель (или чем она должна быть!). Действительно, мы хотели, чтобы Манифест отчасти рассматривался бы как такая определительная формулировка. За подробностями следует обращаться к самой книге; здесь же хотелось бы только сказать, что мы видим свой вклад в этой области прежде всего как расстановку всех точек над i и черточек на t, которые не были расставлены должным образом в работах Кодда. Мы не нисколько не отклонились от видения Кодда в каких-либо существенных аспектах; весь Манифест в очень большой степени следует духу идей Кодда и развивает основанное им направление.
Когда расширение не является расширением?
When's an extension not an extension?
C.J. Date
()
С самого начала по отношению к реляционной модели наблюдался необычайно высокий уровень критики. Более конкретно, в течение многих лет утверждалось, что (a) в модели не хватает тех или иных возможностей и, следовательно, (b) ее необходимо некоторым образом расширять. В этой заметке я хочу достаточно детально исследовать суть дел, связанных с "расширением реляционной модели". В частности, мне хочется представить свои соображения по поводу собственной расширенной версии Кодда, известной под названием RM/T.
Литература
E.F. Codd and C.J. Date. "Interactive Support for Nonprogrammers: The Relational and Network Approaches." IBM Research Report RJ1400 (June 6th, 1974). Republished in Randall J. Rustin (ed.), Proc. ACM SIGMOD Workshop on Data Description, Access, and Control, Vol. II, Ann Arbor, Michigan (May 1974). Also in C.J. Date, Relational Database: Selected Writings, Reading, Mass.: Addison-Wesley (1986). Date, C.J. and E.F. Codd. "The Relational and Network Approaches: Comparison of the Application Programming Interfaces." IBM Research Report RJ1401 (June 6th, 1974). Republished in Randall J. Rustin (ed.), Proc. ACM SIGMOD Workshop on Data Description, Access, and Control, Vol. II, Ann Arbor, Michigan (May 1974). Also in C.J. Date, Relational Database: Selected Writings. Reading, Mass.: Addison-Wesley (1986). Date, C.J. "Support for the Conceptual Schema: The Relational and Network Approaches." In C.J. Date, Relational Database Writings 1985-1989. Reading, Mass.: Addison-Wesley (1990). Codd, E.F. "Normalized Data Base Structure: A Brief Tutorial." Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control, San Diego, Calif. (November 11th-12th, 1971). Date, C.J. "Why Relational?" In C.J. Date, Relational Database Writings 1985-1989. Reading, Mass.: Addison-Wesley (1990). Date, C.J. "Essentiality." In C.J. Date, Relational Database Writings 1991-1994. Reading, Mass.: Addison-Wesley (1995).
Date, C.J. "Don't Mix Pointers and Relations!" and "Don't Mix Pointers and Relations - Please!". In C.J.Date, Hugh Darwen, and David McGoveran: Relational Database Writings 1994-1997. Reading, Mass.: Addison-Wesley, 1998. Date, C.J. and Hugh Darwen. Foundation for Object/Relational Databases: The Third Manifesto. Reading, Mass.: Addison-Wesley, 1998. Codd, E.F. "Extending the Relational Database Model to Capture More Meaning." IBM Research Report RJ2599 (August 6th, 1979). Republished in ACM Transactions on Database Systems 4(4), December 1979. Codd, E.F. The Relational Model for Database Management Version 2. Reading, Mass.: Addison-Wesley, 1990. Pin-Shan Chen. :The Entity-Relationship Model - Toward a Unified View of Data". ACM Transactions on Database Systems 1(1), March 1976. Republished in Michhael Stonebraker (ed.): Readings in Database Systems (2nd edition), San Mateo, Calif.: Morgan Kaufmann, 1994. Date, C.J. "The Extended Relational Model RM/T." In C.J.Date, Relational Database Writings 1991-1994. Reading, Mass.: Addison-Wesley, 1995. Date, C.J. and Hugh Darwen. A Guide to the SQL Standard (4th edition). Reading, Mass.: Addison-Wesley, 1997.
Codd, E.F. "Extending the Relational Database Model to Capture More Meaning." IBM Research Report RJ2599 (August 6th, 1979). Republished in ACM Transactions on Database Systems 4(4), December 1979. Codd, E.F. "A Data Sublanguage Founded on the Relational Calculus." IBM Research Report RJ893 (July 26th, 1971). Republished in Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control, San Diego, November 1971. Codd, E.F. "Interactive Support for Nonprogrammers: The Relational and Network Approaches." IBM Research Report RJ1400 (June 6th, 1974). Republished in Randall J. Rustin (ed.), Proc. ACM SIGMOD Workshop on Data Description, Access, and Control, Vol. II, Ann Arbor, Michigan, May 1974. Also in C.J. Date, Relational Database: Selected Writings. Reading, Mass.: Addison-Wesley, 1986. Codd, E.F. "Recent Investigations into Relational Data Base Systems". IBM Research Report RJ1385 (April 13rd, 1974). Republished in Proc. 1974 Congress (Stockholm, 1974). New York, N.Y.: North-Holland, 1974. Codd, E.F. "Relational Database: A Practical Foundation for Productivity." IBM Research Report RJ3339 (December 21st, 1981. Republished in CACM 25(2), February 1982. Codd, E.F. "Data Models in Database Management. Proc. Workshop in Data Abstraction, Databases, and Conceptual Modelling (Michael L. Brodie and Stephen N. Zilles, eds.), Pingree Park, Colo. (June 1980): ACM SIGART Newsletter No. 74 (January 1981); ACM SIGMOD Record 11(2), February 1981; ACM SIGPLAN Notices 16(1), January 1981. Stonebraker, Michael. Introduction to Chapter 1 ("The Roots"). Readings in Database Systems (2nd edition). San Mateo, Calif.: Morgan Kaufmann, 1994. Codd, E.F. "A Relational Model of Data for Large Shared Data Banks." CACM 13(6), June 1970. Republished in Milestones of Research -- Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26(1), January 1983. Codd, E.F. "Is Your DBMS Really Relational?"; "Does Your DBMS Run By The Rules?" Computerworld (October 14th, 1985; October 21st, 1985). Codd, E.F. The Relational Model For Database Management Version 2. Reading, Mass.: Addison-Wesley, 1990. Date, C.J. and Hugh Darwen. Foundation for Object/Relational Databases: The Third Manifesto. Reading, Mass.: Addison-Wesley, 1998.
E.F. Codd: "Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks." IBM Research Report RJ599 (August 19th, 1969). E.F. Codd: "A Relational Model of Data for Large Shared Data Banks." CACM 13, No. 6 (June 1970). Republished in Milestones of Research - Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26, No. 1 (January 1983). E.F. Codd: "Relational Completeness of Data Base Sublanguages" (presented at Courant Computer Science Symposia Series 6, "Data Base Systems", New York City, N.Y., May 24th-25th, 1971). IBM Research Report RJ987 (March 6th, 1972). Republished in Randal J. Rustin (ed.), Data Base Systems: Courant Computer Science Symposia Series 6, Englewood Cliffs, N.Y.: Prentice-Hall (1972). C.J. Date: "An Introduction to Database Systems (6th edition). Reading, Mass.: Addison-Wesley (1995). C.J. Date: "Tables with No Columns". Database Programming & Design 6, No. 3 (March 1993). Republished in Relational Database Writings 1991-1994, Reading, Mass.: Addison-Wesley (1995). C.J. Date: "Divide-and Conquer?". Database Programming & Design 7, No. 4 (April 1994). Republished in Relational Database Writings 1991-1994, Reading, Mass.: Addison-Wesley (1995). C.J. Date: "Relations Beyond Compare". Database Programming & Design 7, No. 5 (May 1994). Republished (as "Relational Comparisons") in Relational Database Writings 1991-1994, Reading, Mass.: Addison-Wesley (1995). C.J. Date: "Nested Relations". Part 1, Database Programming & Design 8, No. 3 (March 1995); Part 2, Database Programming & Design 8, No. 4 (April 1995).
Ложные и истинные расширения
Некоторые утверждения о недостатках реляционной модели правильны, другие - нет. Соответственно некоторые предложенные расширения являются правильными в том смысле, что они действительно добавляют полезную функциональность; однако имеются и ложные расширения в том смысле, что они либо (a) не добавляют никакую новую функциональность, либо (b) функциональность, которую они добавляют, не является полезной. В число примеров правильных расширений входят операции EXTEND и SUMMARIZE, операции реляционного сравнения и теория обновления базы данных через представления. (Уверен, что можно согласиться с тем, что все эти примеры действительно обеспечивают новую полезную функциональность.) Примеры ложных расширений включают такие вещи как запросы с квотами, поддержку дат и времени и "тип данных REF" (REF = reference). Позвольте развить эту мысль:
Запросы с квотами полезны с прагматической точки зрения, но по существу они являются всего лишь синтаксической сокращенной записью для уже существующей функциональности. Если говорить более точно, то имея в виду ложные расширения, я не утверждал, что это обязательно плохо - я всего лишь имел в виду, что это на самом деле не расширение модели. Поддержка дат и времени также полезна. Более того, это не просто сокращенная синтаксическая запись для того, что уже существует - действвительно обеспечивается новая функциональность. Однако это все-таки не расширение модели, поскольку вопрос о том, какие типы данных поддерживаются, не имеет ничего общего с моделью ("типы ортогональны таблицам"). Но "тип данных REF" является ложным расширением, поскольку он бесполезен! На самом деле, это возвращает в модель все эти указатели и связанные с ними вещи. Кодд сознательно отказался от этого много лет тому назад [1]. Ложные расширения - когда они действительно провозглашаются расширениями - приводят к искаженному пониманию истинной сути модели. Конечно, это в особенности свойственно сообществу SQL; конечно, из этого происходят недостатки SQL; многие проблемы SQL пытаются связать с "недостатками реляционной модели", а решение пытаются искать в "расширениях объектной модели". (Как я уже много раз писал раньше, наибольшей проблемой SQL является как раз то, что в этом языке не поддерживается реляцтонная модель.) Самым свежим и, видимо, наиболее вопиющим примером является так называемая объектно/реляционная модель, которая кратко обсуждается в следующем разделе.
"Объектно/реляционная" модель
Несколько поставщиков основанных на SQL СУБД пытаются (должен заметить, что с разной степенью успеха) расширить свои продукты, внедрив в них некоторую разновидность объектной функциональности. Они заявляют, что при этом расширенные продукты поддерживают "расширенную" версию реляционной модели, которую они называют "объектно/реляционной моделью" (для краткости - O/R).
Но это заявление абсурдно! Как мы вместе с Хью Хагеном показали в Третьем манифесте [2], объектная функциональность и реляционная модель полностью ортогональны. Цитирую: "Реляционная модель не нуждается в расширении, коррекции и дополнительных допущениях, и это не противоречит возможности [поддержки объектной функциональности]. Все, что требуется, это должная поддержка доменов отношений (что никогда не делалось в SQL) с пониманием того, что, по своей сути, это абстрактные типы данных (ADT). Другими словами, так называемая O/R модель - это всего лишь реляционная модель, чистая и простая; для нее не требуются какие-либо (истинные) "расширения реляционной модели".
Обзор
Эта статья - которую я буду теперь называть "статьей о полноте" - является, по всей видимости, наиболее формальной статьей Кодда. Определенно, она наиболее трудна для среднего читателя. Однако она фундаментальна, поскольку обобщает материал первых двух статей [1, 2], определяя то, что теперь мы считаем исходным реляционным образом действий.
Подобно предшествующим статьям [1, 2], в статье о полноте по-прежнему полагается, что реляционная модель содержит только структурные аспекты: "В предыдущих статьях ... мы предложили реляционную модель данных ..." пишет Кодд. "[Теперь] мы определяем набор операций над отношениями ...". Другими словами, эти операции не считаются частью самой реляционной модели. Конечно, сегодня мы считаем эти операции составной частью модели; в статье о полноте предлагаются альтернативные, но эквивалентные формализмы для этой части.
Что достигается в статье о полноте? Цитируем аннотацию: "В близком будущем мы можем ожидать появления величайшего разнообразия [предложений языков баз данных]. В этой статье [обеспечивается] теоретический базис, который может использоваться для определения того, насколько полные возможности выборки предоставляются в [таком языке]". Этим теоретическим базисом является "реляционная полнота" из названия статьи; язык является реляционно полным, если он обладает такой же мощностью, что и реляционное исчисление (говоря несколько вольно). Позже в статье Кодд категорически заявляет, что любой язык баз данных общего назначения должен обладать не меньшей мощностью; в частности, он отмечает, что используя такой язык вы должны иметь возможность формулировать запросы без использования "программных циклов и любых других видов ветвления - важное соображение для работы с базой данных с терминала" (и как мы все теперь знаем, для доступа из прикладных программ).
Языки должны быть "по меньшей мере" реляционно полными, поскольку по Кодду такая полнота является единственной базовой мерой мощности языка.
В практических языках требуется наличие и других возможностей.
Статья состоит из пяти основных разделов:
Введение Реляционная алгебра Реляционное исчисление Редукция Сравнение исчисления и алгебры
Как обещается во введении, в статье приводится формальное определение реляционной алгебры -- часто теперь называемой реляционной алгеброй Кодда, чтобы отличать ее от других алгебр, определенных в разное время - и реляционного исчисления.
Затем в статье определяется реляционная полнота в терминах реляционного исчисления. Далее представляется алгоритм ("алгоритм редукции Кодда") для преобразования произвольного выражения исчисления в эквивалентное алгебраическое выражение, что доказывает, что алгебра по меньшей мере обладает мощностью исчисления и реляционно полна. Наконец, Кодд приводит некоторые соображения о сравнительных достоинствах алгебры и исчисления как базиса для разработки практического языка баз данных.
Обзор статьи
Конечно, сейчас битва между реляционным и сетевым подходами кажется древней историей. (Победили хорошие парни.) Несмотря на это, статья Кодда -- написанная более 25 лет тому назад -- по-прежнему представляет собой великолепный пример ясных рассуждений. Действительно, замечательным фактом является то, что в то время, когда нормой являлось беспорядочное мышление, Кодд оказался в состоянии разорвать замкнутый круг и сосредоточиться на действительно важных предметах. Позвольте уточнить:
Прежде всего, Кодд понимал, что сравнение весьма конкретных спецификаций CODASYL и гораздо более абстрактной реляционной модели напоминало бы сравнение яблок с апельсинами и привело бы ко множеству недоразумений. Поэтому было необходимо сначала определить абстрактную "сетевую модель". Тогда можно было бы выполнить сравнение в разумной манере.
Исходя из этого, Кодд приступает к определению абстракции такой модели. (И, конечно, после этого он переходит к сравнению этой абстракции с реляционной моделью.)
Таким образом, Кодд представляет собой первого человека, который попытался дать формальное определение не только реляционной модели (конечно, он сделал это), но также и сетевой модели! Конечно же, ни в одном из документов CODASYL такая попытка не предпринималась. (На самом деле, статья вышла в свет вовремя, хотя к этому времени основные сражения закончились. Теперь мы опять видим старые добрые проблемы в связи с объектными СУБД. Как отмечают некоторые авторы, объектные СУБД в некоторых аспектах напоминают CODASYL. Это тот случай, когда незнание истории усугубляет ситуацию.)
В любом случае, наиболее значительное достижение статьи "Interactive Support for Nonprogrammers: The Relational and Network Approaches", вероятно, состоит в введении понятия существенности, понятия, которое является критическим для правильного понимания моделей данных в целом и различия между отношениями и сетями, в частности. (В действительности, именно главным образом по этой причине мне захотелось поговорить об этой статье в данной серии.)
Помимо введения понятия существенности, в статье Кодда также поднимается ряд вопросов относительно уместности использовния сетевых структур в качестве компонента того, что он называет "принципиальной схемой" - вопросов, на которые, насколько мне известно, до сих пор нет ответов в доступной литературе. Цитирую: "В прошлом многих разработчиков проограммного обеспечения ... смущало различие между двумя совершенно различными понятиями: с одной стороны, расширениями возможностей и, с другой стороны, общностью приложения." Как верно! "Критическим аспектом систем управления базами данных является то, что это богатство возможностей (т.е. их изменчивость) структур данных ... должно поддерживаться принципиальной схемой. Если возможности этих структур данных ... выходят за пределы некоторого минимума, нужно задать следующие вопросы ... "Мне не хочется здесь подробно обсуждать эти вопросы, однако я уже говорил об этом в одной из предыдущих публикаций [3]).
Между прочим, эта цитата напоминает мне другую, которая взята из вводной статьи Кодда о нормализации [4]. "В нескольких существующих системах допускается разнообразие физических представлений заданной логической структуры... Сложность физических представлений, поддерживаемых этими системами, видимо, невозможно понять, поскольку эти представления выбираются в расчете на повышение эффективности... Еще менее понимаема тенденция к все более и более усложняемым структурам данных, с которыми ... непосредственно имеют дело пользователи. Конечно же, при выборе логических структур данных должно присутствовать только одно соображение - удобство большинства пользователей." Опять, как это верно!
Вернемся к "Interactive Support". В статье содержится приложение, в котором сравниваются версии CODASYL/COBOL и relational/Alpha простого приложения управления магазином. Это сравнение убедительно демонстрирует простоту реляционного подхода (конечно, с точки зрения пользователя). Полные подробности сравнения содержатся в реальном программном коде обоих решений.
Я отсылаю вас к исходному тексту статьи; при этом мне хочется повторить некоторые замечания из одной из моих предыдущих статей [5], в которой обсуждался тот же самый пример. Вот некоторая статистика:
| CODASYL | relational | |
| GO TO | 15 | 0 |
| PERFORM UNTIL | 1 | 0 |
| currency indicators | 10 | 0 |
| IF | 12 | 0 |
| FIND | 9 | 0 |
| GET | 4 | 1 |
| STORE / PUT | 2 | 1 |
| MODIFY | 1 | 0 |
| MOVE CURRENCY | 4 | 0 |
| other MOVEs | 9 | 1 |
| SUPPRESS CURRENCY | 4 | 0 |
| total statements | > 60 | 3 |
Этот пример проясняет и еще один вопрос. Цитируя Кодда, "Предостерегаем читателя от попытки сравнения [разных] подходов исключительно на основе основных различий в [структурах данных]. Достаточное внимание должно уделяться ... и операторам." И далее он добавляет: "В обсуждениях реляционного подхода часто преобладают аспекты компонента [структур данных] в ущерб [другим компонентам]. Для обоснования этого подхода все ... компоненты должны рассматриваться в одном пакете."
Операции реляционной алгебры
В соответствии с Chambers Twentieth Century Dictionary алгебра - это "некоторая система, в которой используются символы и осмысленным образом применяются связи и операции". Более конкретно, алгебра состоит из набора объектов и набора операций, удовлетворяющих некоторым аксиомам или законам (таким, как замкнутость, коммутативность или ассоциативность). Слово "алгебра" в конечном счете происходит от арабского "al-jebr", означающего сборку (чего-либо разобранного) или комбинирование.
В реляционной алгебре объектами являются отношения; определяются такие операции как ограничение, проекция и соединение, и имеется несколько аксиом или законов, включающих замыкание - исключительно важную аксиому. Результатом любой реляционной операции всегда является другое отношение. Как я всегда говорю (например, см. [4]), важным следствием замкнутости реляционной алгебры является возможность составлять вложенные реляционные выражения.
Алгебраические операции предназначены только для чтения. (Все они служат для образования некоторого отношения из других отношений.) Следовательно, они оперируют точно определенным образом над значениями отношений. С точки зрения реляционной алгебры нет нужды в реляционных переменных - и не предполагается их существование. Конечно, в реальном языке баз данных потребуются и операции обновления, а потому также и реляционные переменные, но это не является частью реляционной алгебры.
Для "удобства обозначений и пояснений" в статье Кодда предполагается, что "домены отношений" - на самом деле он имеет в виду атрибуты или столбцы - идентифицируются порядковой позицией, а не именем (хотя он понимает, что на практике лучше использовать имена). В результате он не ставит вопрос об именах столбцов результата, что является важным аспектом замкнутости, и не обсуждает потребность в операции переименования столбца. (Подробное обсуждение этих проблем см. в [4].) Далее я буду использовать имена столбцов, а не их номера.
В статье - по моему мнению, очень неудачно! -- говорится, что "для целей баз данных достаточно иметь дело с данными, состоящими из целых значений и символьных строк".
Это замечание, возможно, могло привести к неправильному пониманию, заключающемуся в том, что реляционные системы могут работать только с такими простыми данными как числа и строки. (В статье также говорится, что "могут включаться другие типы примитивных элементов", но это замечание всего лишь возвращает нас к трудному вопросу о том, чем могут быть "примитивные" или "атомарные" данные [8]). Удивительно то, что в статье нигде не используется предположение о "простоте данных", по крайней мере, каким-либо существенным образом.
Кодд определяет следующие алгебраические операции:
Декартово произведение Объединение, пересечение и вычитание O-ограничение Проекция O-соединение и естественное соединение Деление Факторизация
Я не собираюсь приводить здесь определения всех этих операций, потому что такие определения можно найти во многих других источниках (см., например, [4]). Однако в комментариях к соответствующим частям раздела я отмечу несколько расхождений между определениями Кодда и теми определениями, которые обычно используются сегодня.
Декартово произведение: Строго говоря, Декартово произведение двух отношений есть множество пар в виде (a, b), где a - это кортеж первого отношения-операнда, а b - кортеж второго отношения-операнда. (Статья о полноте, как кажется, была первой, в которой Кодд использует термин "кортеж" в качестве аббревиатуры для термина "n-кортеж".) Однако для достижения замкнутости мы хотим, чтобы результат являлся отношением. Кодд определяет расширенный вариант Декартова произведения, которое производит множество кортежей, а не множество пар. Более точно, там, где обычное Декартово произведение дало бы пару (a, b), расширенный вариант производит кортеж, состоящий из всех компонентов a вместе со всеми компонентами b. Операция расширенного произведения - в отличие от обычной - коммутативна и ассоциативна, из чего следует, что мы можем однозначно говорить о произведении n отношений для любого n. (Можно даже допустить нулевое значение n, хотя Кодд явно не обсуждает такие возможности.)
Объединение, пересечение, вычитание: Эта статья была первой, в которой обращалось внимание на специальные реляционные варианты этих операций. Требовалась "совместимость по объединению" операндов (опять же, чтобы результат всегда являлся отношением). Объединение и пересечение (но не вычитание) коммутативны и ассоциативны.
O-ограничение: "O" означает любую используемую операцию сравнения (=, Заметим, что это определение отличается от того, которое приводится в [2].
Заметим также, что допускаются "составные" атрибуты - например, простые атрибуты STREET, CITY. STATE и ZIP можно рассматривать как составной атрибут ADDR - хотя Кодд не поднимает вопрос о том, что означает сравнение "A < B", если A и B - составные в этом смысле атрибуты.
Проекция: Кодд делает важное замечание о том, что проекция представляет собой алгебраического двойника квантора существования реляционного исчисления.
Замечание: В статье предполагается, что результатом проекции отношения R на пустой набор атрибутов является R. Это соглашение неудачно, поскольку результатом такой проекции должно быть отношение нулевой степени - конкретно, TABLE_DEE или TABLE_DUM [5].
O-соединение и естественное соединение: Кодд определяет естественное соединение в терминах O-соединения (более точно, как проекцию эквисоединения). Сегодня у нас имеется тенденция относиться к естественному соединению как к более фундаментальной операции (настолько фундаментальной, что неуточненный термин "соединение" обычно используется в смысле естественного соединения). Действительно, вы могли бы заметить, что "O-соединения" даже и не упоминались в первых двух статьях Кодда [1, 2]. Далее, Кодд отмечает, что можно определить O-соединение в терминах O-ограничения, так что это не примитивная операция. (На самом деле, верно и обратное - т.е. можно определить O-ограничение в терминах O-соединения. Выбор набора примитивных операций в некоторой степени произвольно зависит от нашей позиции.
В один из общепринятых наборов примитивов входят ограничение, проекция, произведение, объединение и вычитание.) Подобно операциям (расширенного) произведения, объединения и пересечения, естественное соединение коммутативно и ассоциативно.
Деление: В статье о полноте впервые упоминалась эта операция. В действительности, понятно, что Кодд ввел ее как "алгебраического двойника квантора всеобщности". Он говорит, что операция не является примитивной; ее можно определить в терминах уже описанных операций. (На самом деле, определение не совсем такое, какое мы используем сегодня, но различия незначительны. Можно определить вариант операции - отличающийся от определяемого в статье - допускающий деление любого отношения на любое другой; см. [6].)
Не интересует ли вас, почему операция называется "делением"? Причину демонстрирует следующее тождество:
( R TIMES S ) DIVIDEBY S = R
Деление - это операция, в некотором смысле обратная Декартову произведению, и это не только двойник квантора существования, чем, как казалось, она являлась. С операцией связаны проблемы пустых множеств и связанные с ними [6]. На самом деле, Кодд предлагает пример, иллюстрирующий проблему: Пусть имеется отношение SP {S#, P#, ...}, показывающее, какие поставщики поставляют какие детали. Кодд утверждает, что выражение SP {S#, P#} DIVIDEBY SP {P#} выдаст номера поставщиков, поставляющих все детали. Однако, если не имеется никаких деталей, это выражение выдаст неверный результат. (Не будет выдано ни одного номера поставщика, хотя следует выдать их все.)
Более хорошую основу для обхождения с теми разновидностями проблем, для решения которых было предназначено реляционное деление, дают реляционные сравнения - но исходная реляционная модель, определенная Коддом, вообще не включает таких сравнений [7].
Факторизация: Эта операция (сегодня более часто называемая гнездованием [nesting]) преобразует нормализованное отношение в ненормализованную форму. Например, для заданного отношения EMP с атрибутами EMP# и DEPT# можно было бы использовать эту операцию для получения ненормализованного отношения с атрибутами DEPT# и SET_OF_EMPS, в котором каждый кортеж содержит номер отдела и множество всех соответствующих номеров служащих.Эта операция не используется в основной части статьи; Кодд выносит ее в приложение, полагая, что это может быть полезно "для целей презентации". Наше понимание истинной природы нормализации нормализации улучшилось с 1971 г.; мы теперь относимся ко всем отношениям как к нормализованным. "Ненормализованное отношение" является противоречивым сочетанием терминов. Однако на самом деле отношения, включающие значения-отношения, часто являются противопоказанными.
Реляционная модель выдержит испытание временем
The relational model will stand the test of time
C.J. Date
()
Я посвятил несколько заметок историческому обзору и анализу нескольких статей Кодда о реляционном подходе (по крайней мере, наиболее важных статей). Более конкретно, обсуждались следующие статьи:
"Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks" "A Relational Model of Data for Large Shared Data Banks" "Relational Completeness of Data Base Sublanguages" "A Data Base Sublanguage Founded on the Relational Calculus" "Further Normalization of the Data Base Relational Model" "Interactive Support for Nonprogrammers: The Relational and Network Approaches" Extending the Relational Data Base Model to Capture More Meaning"
Время от времени я касался и других статей.
Пришло время завершить эту серию. В заключительной заметке я хотел бы сформулировать основные цели, которые ставились при создании реляционной модели, и обсудить, насколько хорошо она удовлетворяет этим целям (или не удовлетворяет). Кроме того, я хотел бы коротко обсудить, что в точности представляет собой реляционная модель и в каком направлении она могла бы развиваться. Мне хочется, чтобы серия целиком рассматривалась как дань уважения огромным достижениям Кодда в создании, больше частью, в одиночку практически всей области современного управления базами данных - области, в которой все мы напряженно трудимся и из которой черпаем средства для существования. Спасибо, Тед!
Статья про RM/T: основные идеи
Обратимся к некоторым интересным истинным расширениям модели. В 1979 г. Кодд опубликовал еще одну важную статью под названием "Extending the Relational Database Model to Capture More Meaning" [3]. Я буду называть эту статью статьей про RM/T по причинам, которые скоро станут понятны. Как следует из названия статьи, ее основной задачей является введение набора "семантических" расширений исходной модели. Однако статья начинается с обзора базовой модели (по состоянию на 1979 г.), и мне хотелось бы сделать по этому поводу несколько замечаний, прежде чем переходить к деталям предложенных расширений.
Прежде всего, думаю, что не ошибусь, утверждая, что статья про RM/T была первой статьей Кодда, где было введено явное определения термина реляционная модель! Вот это определение:
Реляционная модель состоит из:
Коллекции изменяемых во времени табличных отношений (с отмеченными выше свойствами - особо отметим ключи и домены) Правил вставки-обновления-удаления (Правила 1 и 2, упомянутых выше) Реляционной алгебры, описываемой ... ниже.
Отклоняясь от основной темы, я хочу привести несколько комментариев по поводу этого определения:
Может быть, это не столь важно, но мне кажется немного странным, когда говорят, что реляционная модель включает "коллекцию ... отношений" (разве коллекция отношений это не база данных?). Мне кажется более правильным говорить, что модель включает генератор типов RELATION, который дает пользователям возможность определения значений и переменных отношений (конечно, я предпочитаю термин "переменная отношения" термину Кодда "изменяемое во времени табличное отношение". "Правила 1 и 2, умомянутые выше" - это правила целостности сущности и ссылочной целостности. В более ранних статьях эти правила использовались более или менее неявно, не формулировались и не получали названий. Замечание: В действительности, формулировка правила ссылочной целостности была несколько дефектной, поскольку в ней не упоминалась возможность вхождения в состав внешнего ключа неопределенных значений.
Но конечно, это не является важным для вас, как и для меня, если мы не считаем появление понятия первичного ключа событием первостепенной важности. Реляционная алгебра, "описываемая ниже", включает обычные операции, а также дополнительные операции для работы с "неопределенными значениями" [sic]. В статье определяются следующие дополнительные операции: MAYBE O-JOIN, MAYBE DIVIDE, OUTER O-JOIN, NATURAL O-JOIN, OUTER NATURAL JOIN и OUTER UNION ("аналогичным образом можно было бы определить также OUTER-версии для INTERSECTION и DIFFERENCE"). Этот список операций порождает много вопросов - например, вопросы, связанные с ортогональностью и полнотой - но опять же, я не думаю, что это очень важно, поскольку считаю неопределенные значения и все, что с ними связано, ошибкой (по моему мнению, единственной большой ошибкой Кодда за все время его работы).
Также в статье про RM/T Кодд впервые явно упоминает идею реляционного присваивания. Однако это делается только в связи с предлагаемыми семантическими расширениями: присваивание не является частью приведенного определения "базовой реляционной модели", хотя, конечно, это часть базовой модели в ее современном понимании. Более того, не обсуждается тот факт, что операции INSERT, UPDATE и DELETE представляют собой лишь сокращенную форму записи некоторых реляционных присваиваний.
В третьих, в статье говорится следующее: "С реляционной моделью тесно связаны различные [семантические понятия]... Примерами являются ... (естественные) соединения без потерь и функциональные зависимости, многозначные зависимости и нормальные формы". Здесь мы имеем явное утверждение о той позиции Кодда, что эти понятия следует рассматривать в отрыве от модели как таковой (хотя я думаю, что впоследствии он изменил свою точку зрения по этому вопросу [4]).
В четвертых, в статье про RM/T Кодд также впервые использует идею суррогатов - т.е. определяемых системой идентификаторов. (Снова эта идея подается только в связи с предлагаемыми семантическими расширениями, хотя нет никаких оснований не использовать ее в базовой модели, и в пользу этого имеется много веских аргументов.) Однако, к сожалению, в статье утверждается, что суррогаты должны быть скрыты от пользователей - очевидное нарушение приведенного ранее в этой статье определения реляционной базы данных, в котором говорится, что все данные в базе данных должны быть доступны (авторизованным) пользователям.
На самом деле, можно было привести тот аргумент, что сокрытие суррогатов нарушает собственный Информационный Принцип Кодда, который устанавливает, что вся информация в базе данных должна явно представляться в терминах отношений и никак иначе.
(Отклоняясь от темы, позволю себе напомнить, что - как мы видели в моей заметке прошлого месяца - отношения являются единственными существенными конструкциями данных, допустимыми в реляционной базе данных. И я добавлю теперь, что отношения являются также единственными несущественными конструкциями, и тогда мы, в сущности, приходим к Информационному Принципу.)
Наконец, в статье про RM/T отведен один краткий (слишком краткий) раздел связи между реляционной моделью и логикой предикатов: "База данных [представляет собой] набор [высказываний] логики предикатов первого порядка... [Мы можем] вынести за скобки предикат, общий для набора простых высказываний, и затем трактовать [высказывания] как n-арное отношение, а этот предикат - как имя отношения". Кодд далее называет "пропозициональную" часть базы данных экстенсиональной, а предикатную часть - интенсиональной (оба эти слова являются техническими терминами логики). "Можно ... представлять интесиональную часть как набор ограничений целостности." И далее кратко сравниваются интерпретации замкнутого и открытого миров. (В интерпретации замкнутого мира отсутствие данной строки в данном отношении означает, что соответствующее высказывание ложно; в интерпретации открытого мира это означает, что мы не знаем, истинно высказывание или ложно.)
Статья про RM/T: Расширения
Как уже отмечалось, основная часть [3] посвящена расширенной версии реляционной модели, названной RM/T ("T - в честь Тасмании, где эти идеи были впервые представлены"). Статья начинается несколькими интересными предварительными замечаниями по поводу семантических расширений и "семантического моделирования данных" вообще:
"В действительности, задача поддержания смысла данных бесконечна. Поэтому термин "семантический" не должен интерпретироваться в каком-либо абсолютном смысле. Более того, модели баз данных, разработанные ранее (и иногда подвергаемые критике как "синтаксические"), не лишены семантических черт (возьмите, например, домены, ключи и функциональные зависимости). Цель [семантического моделирования], тем не менее, исключительно важна, поскольку даже незначительный успех может способствовать пониманию и порядку в области проектирования баз данных."
(Как приятно это отличается от преувеличенных заявлений, так часто встречаемых в области семантического моделирования!)
Далее Кодд делает другое хорошее замечание:
"В современных статьях о семантическом моделировании данных основной упор делается на структурные аспекты, иногда в ущерб манипуляционным аспектам. Структура без соответствующих операций и методов вывода - это что-то вроде анатомии без физиологии."
Хорошая аналогия!
Вернемся конкретно к RM/T. RM/T в целом относится к той же широкой категории, что и более хорошо известная "модель сущность/связь" (для краткости - E/R модель) [5]. Хотя и не реализованная в свое время (и, насколько мне известно, никогда позже), модель RM/T может служить - как и модель E/R - основой систематизированной методологии проектирования баз данных; на самом деле, лично я для использования в этих целях предпочитаю ее модели E/R, поскольку считаю, что она более точно определена. Некоторые очевидные различия между двумя этими моделями состоят в следующем:
В RM/T не проводится излишнее различие между сущностями и связями - связь рассматривается как специальный тип сущности. Структурные и целостные аспекты RM/T являются более мощными и более точно определенными, чем в модели E/R. RM/T включает собственные специальные операции, дополняющие набор операций базовой реляционной модели (хотя в этой области требуется дополнительная работа).
Коротко говоря, RM/T работает следующим образом:
Сущности (включая "связи") представляются E-отношениями и P-отношениями, которые являются специальными формами n-арных отношений общего вида. E- отношения используются для регистрации того факта, что некоторая сущность существует, P-отношения используются для регистрации свойств этих сущностей (все E-отношения имеют степень один, степень P-отношений не меньше двух). Между сущностями может существовать множество связей; например, типы сущностей A и B могут быть связаны в ассоциацию (термин RM/T для обозначения связи многие-ко-многим), или тип сущности Y может быть подтипом типа сущности X. RM/T включает формальную структуру каталога, с помощью которого такие связи могут быть сделаны известными системе. Тем самым система получает возможность поддержки различных ограничений целостности, порождаемых существованием таких связей. Как уже отмечалось, обеспечивается ряд операций высокого уровня для манипулирования различными объектами RM/T (E-отношениями, P-отношениями, отношениями-каталогами и т.д.).
В RM/T также обеспечивается схема классификации сущностей, которая во многих отношениях представляет собой наиболее значительный аспект - или, по крайней мере, наиболее видимый аспект - всей модели. Более конкретно, сущности классифицируются (хотя, заметьте, только неформально) в три категории, называемые ядрами, характеристиками и ассоциациями:
Ядра: Ядерные сущности - это сущности, обладающие независимым существованием; они говорят о том, "что это за база данных". Другими словами, ядра - это сущности, не являющиеся ни характеристикой, ни ассоциацией (см. ниже). Примерами являются поставщики и детали (но не поставки) в обычной базе данных поставщики-и-детали. Характеристики: Характеристическая сущность - это сущность, основное назначение которой состоит в описании или "характеризации" некоторой другой сущности. Примером могут служить отдельные пункты заказа в заказе клиента. Существование характеристик зависит от описываемой ими сущности.
Описываемая сущность может быть ядром, характеристикой или ассоциацией. Ассоциации: Ассоциативная сущность - это сущность, функция которой состоит в представлении связи многие-ко-многим (или многие-ко-многим-ко-многим...) между двумя или более другими сущностями. Примером являются поставки в знакомой базе данных поставщики-и-детали. Ассоциируемые сущности могут быть ядрами, характеристиками или ассоциациями.
Кроме того:
Сущности (все зависимости от их категории) могут обладать свойствами; например, детали имеют цвет, пункты заказа - стоимость, у поставок имеется объем поставки. В частности, любая сущность (снова вне зависимости от категории) может иметь свойство, указывающие на некоторую другую связанную сущность; например, заказы указывают на клиентов. Указание представляет связь многие-к-одному между двумя сущностями. Замечание: В действительности, идея указаний была добавлена позже [6] - ее не было в первой статье про RM/T. Поддерживаются супертипы и подтипы сущностей. Если B является подтипом A, то B - это ядро, характеристика или ассоциация в зависимости от того, представляет ли собой A ядро, характеристику или ассоциацию. Замечание: Однако в статье про RM/T абсолютно ничего не говорится по поводу связанного (и важного!) понятия наследования. Понятие супертипов и подтипов в RM/T больше похоже на понятие "супертаблиц и подтаблиц", предлагаемое в SQL3, чем на истинное наследование типов, обсуждаемое, например, в Третьем Манифесте.
Упомянутые понятия можно связать (не слишком точно) с их аналогами в E/R следующим образом: Ядро соответствует "регулярной сущности" E/R; характеристика - "слабой сущности" E/R; ассоциация - "связи" E/R (только для связей многие-ко-многим).
Замечание: В дополнение к аспектам, кратко обсужденным выше, RM/T также включает поддержку (а) временного измерения и (b) различных видов агрегации данных. Более подробное обсуждение можно найти в статье Кодда [3] или во вводном описании RM/T [6].
СУЩЕСТВЕННОСТЬ
Несмотря на важность этого понятия, исходя из собственного опыта, я считаю, что с этим понятием реально знакомы лишь немногие профессионалы в области баз данных. Поэтому эта заметка представляет собой в основном введение в этот предмет. Замечание: Следующий далее материал частично основан на одной из моих предыдущих статей [6].
Прежде всего, "всем известно", что единственной структурой данных, используемой в реляционной модели, является отношение. Однако, чтобы понять значимость этого факта, требуется знать по крайней мере одну другую структуру данных, например, структуру связей, поддерживаемую в иерархических и сетевых системах. Рассмотрим пример. На Рис. 1 показаны (a) реляционный проект простой базы данных "отделы-сотрудники" и (b) сетевой эквивалент этого проекта. (На самом деле, пример прост по той причине, что в сетевом исполнении проект представляет собой скорее иерархию, но это не важно для нашей цели. Иерархии и сети в большей степени похожи друг на друга, чем на отношения.)
Рис. 1. Отделы и сотрудники: реляционный и сетевой проекты
В сетевом проекте использован "набор (set) в смысле CODASYL" (не нужно путать это понятие с понятием математического множества!). Каждый экземпляр этого набора включает строку DEPT, множество соответствующих строк EMP и экземпляр связи ("DEPTEMP"), соединяющей эти строки DEPT и EMP. (Я использую здесь термин "строка" вместо более принятого слова "запись", чтобы обойти несущественные вопросы, связанные с различием в терминологии этих двух подходов.) Можно представлять ссылку в данном наборе CODASYL как цепочку указателей - указатель от строки DEPT на первую строку EMP для этого отдела, указатель от этой строки EMP на следующую строку для того же отдела и т.д., и, наконец, указатель от последней строки EMP на исходную строку DEPT. Замечание: Эти указатели не обязательно представляются на физическом уровне хранения как реальные указатели, но пользователи обязаны отоситься к ним как к реальным указателям. (Такова сетевая модель!)
Заметим теперь, что строки EMP в сетевом проекте не включают столбец DEPT#. Поэтому для того, чтобы найти, в каком отделе числится данный служащий, нам требуется пройти по экземпляру связи DEPTEMP от требуемой строки EMP к соответствующей строке DEPT; аналогично, чтобы найти служащих данного отдела, нам нужно пройти по экземпляру связи EMPDEPT от требуемой строки DEPT к соответствующим строкам EMP. Другими словами, информация, которая была бы представлена внешним ключом в реляционном проекте, представляется ссылкой в сетевом проекте; ссылки являются сетевым аналогом внешних ключей (вольно выражаясь).
Рассмотрим теперь пару запросов по отношению к этой базе данных. Для каждого запроса я покажу реляционную формулировку (SQL) и ее сетевой эквивалент с использованием гипотетической расширенной версии SQL, в которой поддерживаются связи.
Q1: Получить номера и имена служащих с заработной платой, большей 20K.
| Реляционная формулировка: | Сетевая формулировка: |
| SELECT EMP#, ENAME | SELECT EMP#, ENAME |
| FROM EMP | FROM EMP |
| WHERE SALARY > 20K ; | WHERE SALARY > 20K ; |
| Реляционная формулировка: | Сетевая формулировка: |
| SELECT EMP#, ENAME | SELECT EMP#, ENAME |
| FROM EMP | FROM EMP |
| WHERE SALARY > 20K | WHERE SALARY > 20K |
| AND DEPT# = 'D3' ; | AND ( SELECT DEPT# FROM DEPT OVER EMP ) = 'D3' ; |
Таким образом, Q2 иллюстрирует тот важный момент, что для сетей определенно требуются дополнительные операции доступа к данным.
Отметим также, что эти операции являются дополнительными; реляционные операции, как показывает Q1, по-прежнему необходимы. Более того, заметим, что это замечание относится не только ко всем операциям манипулирования данными (включая операции обновления), но также и к операциям определения, операциям обеспечения безопасности, операциям обеспечения целостности и т.д. Следовательно, связи в сетевых структурах данных определенно добавляют сложность. Однако они не дают дополнительной мощности - нет ничего, что можно было бы представить с помощью сетей и нельзя было бы представить с помощью отношений; нет такого запроса, который можно было бы представить сетевой системе и нельзя бы представить системе реляционной.
Иногда говорят, что можно уменьшить сложность путем добавления к EMP компонента DEPT# (внешнего ключа), как это показано на Рис. 2. В этом доработанном варианте запрос Q2 (сетевая версия) может формулироваться без конструкции OVER; на самом деле, формулировка эквивалента реляционной. Причина этого состоит в том, что DEPT и EMP в этом пересмотренном проекте означают то же самое, что и в реляционном варианте; база данных такая же, что и реляционная, если не принимать во внимание связь DEPTEMP. Но эта связь является полностью избыточной - она не представляет какую-либо информацию, которая не представлена также и внешним ключом. Поэтому мы можем игнорировать эту связь без потери какой-либо функциональности.
Сеть: связь DEPTEMP не является существенной
Рис. 2. Отделы и сотрудники: сетевой проект с внешним ключом EMP.DEPT#
Теперь (наконец!) я поясню смысл понятия существенности. Конструкция, связанная с данными, существенна, если ее утрата вызывает потерю информации - вполне точно, я понимаю это так, что перестанет достигаться некоторое отношение. Например, в реляционном варианте базы данных отделов и сотрудников все конструкции данных в этом смысле существенны. Аналогично, в начальной сетевой версии (Рис. 1) все конструкции (все строки, все столбцы и все связи) тоже существенны.
Но в пересмотренном сетевом варианте (Рис. 2) строки и столбцы продолжают быть существенными, а связь - нет. Нет такой информации, которую можно было бы получить из сети и нельзя было бы получить только из строк и столбцов; вообще отсутствует логическая потребность в связи.
Замечание: Некоторые люди думают, что имеет место обратная ситуация - существенна именно связь, а не внешний ключ. Но это противоречит тому, что поскольку некоторые строки и столбцы должны быть существенными и ничего больше не требуется, то зачем нам нужно что-то еще?
Теперь (наконец) я могу пояснить, в чем состоит принципиальное различие между реляционной базой данных и базой данных другого рода, скажем, сетевой. В реляционной базе данных единственной существенной конструкцией данных является отношение. В других базах данных должна присутствовать по меньшей мере одна дополнительная существенная конструкция данных (такая, как существенная связь). Если бы это было не так, то база данных была бы по существу реляционной с явной демонстрацией некоторых путей доступа. (Не требуется, чтобы пользователи явно применяли эти пути доступа; единственный вопрос состоит в том, почему мы показываем эти пути доступа, а другие не делают этого.) И именно эти дополнительные существенные конструкции данных в основном (но не полностью) приводят к сложности нереляционных баз данных.
Замечание: Конкретно, в случае CODASYL имеется, по меньшей мере, четыре дополнительных конструкции, которые могут использоваться для существенного сохранения информации. Однако рассмотрение подробностей этих конструкций могло бы завести нас слишком далеко.
В каком направлении развивается реляционная модель?
В первой заметке из этой серии я говорил, что ожидаю, что в течение сотен лет системы баз данных будут основываться на реляционном фундаменте, заложенном Коддом. И я надеюсь, что в течение нескольких последних месяцев вы увидели, на чем основаны мои ожидания. Реляционный подход действительно является надежной основой, опираясь на математику и логику предикатов. (Конечно, я не имею в виду, что модель разрешает все известные проблемы и не нуждается в каких-либо расширениях; как мы видели в прошлом месяце, расширения, конечно, возможны и иногда желательны. Я имею в виду только то, что это надежная основа.)
Мне хочется закончить сводкой аргументов, который представил сам Кодд (под заголовком "Whther Database Management?") в статье про Великое Сражение, рассматривая возможные альтернативы будущего систем баз данных. Начнем с предположения наличия простейшего ориентированного на программиста интерфейса с базой данных (интерфейса на уровне записей). Тогда:
Если мы добавляем операции высокого уровня (соединение и т.д.), то получаем автоматическую навигацию - значит, даже непрограммисты смогут достичь своих целей без чьей-либо помощи. Наоборот, если мы не добавляем такие операции, а добавляем новые стрктуры данных, такие как связи, то непосредственная навигация становится необходимой - значит, для достижения целей конечных пользователей необходимы программисты. Если мы добавляем и операции, и структуры, то получаем ненужную сложность - значит, программистам и администратору базы данных придется принимать намного больше решений (и, следует добавить, при отсутствии каких-либо хороших руководств о том, как принимать такие решения).
Заключение очевидно.
Заключительные замечания
В заключение позвольте мне вернуться к стаптье Кодда про "великое сражение". Кодд отмечает, что "недостаточно принимать во внимание подходы, используемые сегодня -- нам нужно ясно осознавать будущее развитие событий". Он говорит, что существенно возрастет роль "случайных" пользователей систем баз данных (в действительности, скоро они будут представлять большинство), и мы должны уделять внимание другим подходам, требуемым для поддержки таких пользователей. Вот некоторые цитаты:
"Таким пользователям, очевидно, требуется простое понятие организации данных, чтобы проще было формулировать запросы или операции модификации". "Следует упомянуть отсутствие в сетевом подходе операций уровня алгебры или исчисления, поскольку такие операции жизненно важны для поддержки действий [случайного пользователя] … Особенно печально отсутствие в [предложениях CODASYL] каких-либо намерений по поддержке работы не-программистов". "Поддержка общего назначения для таких пользователей должна обеспечивать реляционно полную возможность выборки без потребностей в ветвлениях, явных циклов или курсоров. Понятно, как можно реализовать эту возможность с использованием реляционного подхода -- неважно, с применением формального или неформального языкового интерфейса. Непонятно, каким образом этой цели можно достичь на основе сетевого подхода, поскольку принципиальная схема [с наборами CODASYL] обладает свойством информационной существенности".
И сегодня эти наблюдения нуждаются лишь в незначительных корректировках.
Замечание относительно упорядоченности
Понятие существенности позволяет мне объяснить, почему важно то, что строки отношений не упорядочены. В упорядоченном файле порядок сам по себе может быть существенным в упомянутом выше смысле. Например, файл регистрации температуры мог бы поддерживаться в том порядке, в котором производились наблюдения. Этот порядок уже несет информацию, которая может быть потеряна при другом устройстве файла -- точно так же, как если уронить колоду карт, то мы потеряем информацию о предыдущем порядке карт в колоде. (Если вы чересчур молоды, чтобы что-нибудь знать о колодах карт и их порядке, вы можете проигнорировать этот пример.) И для существенного порядка, равно как и для существенных связей требуются дополнительные операции -- "найти n-тую запись", "вставить запись между n-той и (n+1)-ой и т.д. По этой причине упорядоченность не допускается в реляционной модели.
В отличие от сказанного выше, иногда люди считают, что несущественное упорядочение является приемлемым. Файл является несущественно упорядоченным, если он упорядочен на основе значения (значений) некоторого (некоторых) поля (полей) -- например, файл с информацией о служащих может быть упорядочен по значениям номеров служащих, но никакая информация не должна быть потеряна при перемещении записей. В действительности, некоторые "реляционные" системы поддерживают упорядочивание в этом смысле. Однако заметим, что отношения не упорядочены по определению; было бы правильнее относиться к "упорядоченному отношению" как к совсем другому предмету -- возможно, как к последовательному файлу. В этом смысле, операцию ORDER BY языка SQL лучше считать операцией преобразования отношения в такой файл, а не "упорядочиванием отношения".
В любом случае, все несущественные конструкции данных могут вызывать проблемы, поскольку они несут информацию, даже если они не существенны. Например, они могут нарушать требования безопасности. Предположим, что файл служащих упорядочен (несущественно) в порядке возрастания заработной платы. Тогда тот факт, что запись о вашем менеджере появляется после вашей личной записи, что-то вам говорит, даже если вам не дано право видеть реальные размеры заработной платы.
