What Goes Around Comes Around - это увлекательная статья о (циклической) истории моделирования данных. Его написали два эксперта по базам данных: Джозеф Хеллерстайн, профессор компьютерных наук Калифорнийского университета в Беркли, и Майкл Стоунбрейкер, основатель Ingres и Postgres и обладатель премии Тьюринга 2014 года.

Эта статья привлекла мое внимание как первая статья, обсуждаемая в Чтениях по системам баз данных (или Красной книге, также частично написанной Майклом Стоунбрейкером), которую мне дал коллега из Grakn Labs. Книга оказалась для нас очень хорошим ориентиром для проверенных методов и архитектур в системах управления базами данных.

Написанный в 2005 году, он представляет удивительно актуальный взгляд на текущее состояние баз данных и моделей данных: тенденции, которые он описывает, все еще сохраняются, а такие модели, как JSON и графы свойств, прочно укоренились в описываемой им «полуструктурированной» эпохе.

В статье мы рассмотрим девять эпох моделей данных:

  • Иерархический (IMS): конец 1960-х и 1970-е годы.
  • Сеть (CODASYL): 1970-е гг.
  • Отношения: 1970-е и начало 1980-х годов.
  • Сущность-отношения: 1970-е годы
  • Расширенные отношения: 1980-е годы
  • Семантика: конец 1970-х и 1980-е годы.
  • Объектно-ориентированный: конец 1980-х - начало 1990-х годов.
  • Объектно-реляционные: конец 1980-х - начало 1990-х годов.
  • Полуструктурированный (XML): конец 1990-х годов по настоящее время

Читая статью, становится ясно, что из каждой эпохи можно извлечь определенные уроки. Одни вещи явно работали, другие - нет, и это показывает, что инновации не всегда легко внедряются. Более того, также очевидно, что одни и те же проблемы возникают и снова возникают, и одни и те же уроки продолжают извлекаться заново.

Чтобы проиллюстрировать эти исторические закономерности в теории баз данных и инновациях, авторы используют классический пример поставщиков и запчастей от Codd:

Supplier (sno, sname, scity, sstate)
Part     (pno, pname, psize, pcolor)
Supply   (sno, pno ,  qty,   price )

Это представлено в виде реляционной схемы. Каждая строка представляет собой отношение (или таблицу) с атрибутами в скобках. Итак, в данном случае у нас есть набор поставщиков и набор деталей. Также существует отношение «поставки», указывающее, что конкретная деталь поставляется определенным поставщиком с заданным количеством и ценой.

IMS Era

IMS (Система управления информацией) была выпущена в 1968 году. Она структурировала данные по типам записей с полями, аналогичным реляционной таблице выше. Каждый тип записи (кроме корневой) имеет один родительский тип записи. Точно так же каждому экземпляру типа записи нужен родительский элемент, который является экземпляром родительского типа записи. Это называется иерархической моделью, потому что она формирует иерархию типов записей и экземпляров.

Эта модель настолько ограничена, что мы даже не можем правильно представить наш пример!

Наши варианты - сделать Part дочерним элементом Supplier (слева) или Supplier дочерним элементом Part (справа). Обратите внимание, что в первом случае мы дублируем информацию о детали, если одна и та же деталь продается разными поставщиками. В последнем случае мы будем дублировать информацию о поставщике, если один и тот же поставщик продает разные детали.

Эта избыточность является проблемой как с точки зрения эффективности хранения, так и с точки зрения согласованности. Если одни и те же данные хранятся в двух местах, необходимо уделить особое внимание тому, чтобы обе части данных не вышли из синхронизации.

В первом случае также нельзя смоделировать деталь, которая не продается ни одним поставщиком. Точно так же в последнем случае нельзя моделировать поставщика, который не продает детали.

IMS был запрошен запись за раз путем навигации по иерархии. Например, чтобы найти все красные детали, поставляемые поставщиком 16:

get unique Supplier (sno = 16)
until failure:
    get next within parent (pcolor = red)

Это очень похоже на императивный язык программирования: у нас есть пошаговые инструкции, состояние и поток управления. По сути, мы должны явно описать алгоритм, который нужно выполнить, чтобы завершить запрос. Разобраться в том, как быстро выполнить запрос, может быть непросто. Даже такая простая вещь может иметь более быстрый метод выполнения в определенных обстоятельствах (например, если у нас есть индекс для поиска красных частей, но не индекс для номеров поставщиков).

Кроме того, IMS поддерживает несколько способов хранения записей на основе ключа (уникального упорядоченного идентификатора записи): вы можете хранить их последовательно, индексировать с помощью B-дерева или хешировать. Это означало, что вы могли выбрать то, что обеспечит наилучшую производительность для вашего варианта использования.

Однако выбранный метод хранения фактически отключит определенные операции. Например, вы не могли вставить одну запись, когда они хранились последовательно. Если вы используете метод хеширования, вы не можете использовать «получить далее», как в запросе выше. Это демонстрирует отсутствие физической независимости данных - мы не можем изменить физический уровень данных, не изменив также уровень логических данных. Это становится очень важным для баз данных, которые обслуживаются в течение длительного времени: меняются бизнес-требования, хранимые данные изменяются и увеличиваются. В какой-то момент может потребоваться другое физическое представление данных для повышения производительности. Это мотивировало использование реляционной модели, о которой мы поговорим позже.

IMS действительно предлагала небольшую поддержку логической независимости данных - это означает, что мы можем расширить уровень логических данных, не затрагивая приложения, построенные на нем. Это позволяло отображать только подмножество типов записей (по сути, поддерево иерархии). Это означало, что можно было добавлять новые типы записей, не нарушая представления данных.

IMS видела несколько расширений своей модели, чтобы она могла (своего рода) обрабатывать более сложные модели, такие как наш пример. Фактически он все еще используется и поддерживается сегодня (последний выпуск был в 2015 году). В общем, пользователи выглядят как устаревшие системы, в которых затраты перевешивают преимущества перехода на что-то более современное.

Итак, вот уроки IMS:

  1. Физическая и логическая независимость данных крайне желательна
  2. Модели данных с древовидной структурой очень строгие
  3. Это сложная задача - обеспечить сложную логическую реорганизацию данных с древовидной структурой.
  4. Пользовательский интерфейс с постоянной записью заставляет программиста выполнять оптимизацию запросов вручную, а это часто бывает сложно.

Эра CODASYL

Независимо от IMS, CODASYL (Комитет по языкам систем данных) создал несколько отчетов между 1969 и 1973 годами, описывающих сетевую модель, более гибкую модель, которая позволяет типу записи иметь несколько родительских элементов.

В нашем примере мы вводим две стрелки: Supplies и Supplied_by. Они называются типами наборов. Стрелка переходит от типа записи владелец к типу записи дочернего. Экземпляр типа владельца имеет набор экземпляров дочернего типа (это немного отличается от математического набора, потому что набор должен иметь владельца). Итак, в нашем примере выше Supplier может иметь любое количество Supply потомков через набор Supplies.

Эта дополнительная гибкость позволила нам полностью исключить избыточность. Кроме того, вполне возможно иметь Supplier без каких-либо Part и наоборот - у них просто не будет Supply дочерних элементов.

Как и IMS, CODASYL использует язык запросов с постоянной записью:

find Supplier (SNO = 16)
until no-more:
    find next Supply record in Supplies
    find owner Part record in Supplied_by
    get current record
    check current record (color = red)

В этом случае у нас есть несколько «курсоров», указывающих на записи - курсор для Supplier, курсор для Supply, курсор дляPart и курсор для текущей записи. При написании запроса CODASYL программист должен учитывать расположение всех этих разных курсоров в своей голове. В документе это объясняется лучше всего: «один из способов думать о программисте CODASYL - это то, что он должен программировать, глядя на настенную карту сети CODASYL, украшенную булавками разного цвета». Как вы понимаете, это не так уж просто или интуитивно понятно!

Дополнительная проблема с сетевой моделью - загрузка данных. Создание наборов записей может занять много времени, и часто порядок загрузки может иметь большое значение с точки зрения производительности. Определить порядок загрузки вещей нетривиально.

По-прежнему существуют некоторые базы данных, основанные на CODASYL, такие как IDMS, однако они, похоже, не получили широкого распространения.

Уроки от CODASYL:

5. Сети более гибкие, чем иерархии, но более сложные.

6. Загрузка и восстановление сетей сложнее, чем иерархии.

Эра отношений

Реляционная модель была предложена Тедом Коддом в 1970 году, частично мотивированным созданием лучшей модели, чем IMS, для независимости данных. Данные структурированы как отношения - наборы кортежей. Язык запросов устанавливается по времени, выполняется для всех отношений с использованием таких операторов, как select σ и join ⋈:

σ[sno=16 ∧ pcolor=red](Supply ⋈ Supplier ⋈ Part)

Эта комбинация простой модели и языка высокого уровня обеспечивает гораздо лучшую логическую и физическую независимость данных: используя реляционные операторы, мы можем описывать логические отношения в терминах физических (тех, которые фактически хранятся на диске). Приложениям не нужно знать разницу.

В отличие от рассмотренных ранее моделей, в реляционной модели использовался более теоретический подход: она (сознательно) меньше ориентирована на реализацию и, следовательно, не предлагает физического хранилища. Вы можете использовать любое подходящее хранилище (будь то хранение в неупорядоченном виде, индексирование с помощью B-дерева или и то, и другое).

Более того, эта алгебра более высокого уровня позволяет системе использовать правила замены для оптимизации запроса. Например, используя такие правила, как коммутативность ⋈, мы можем переписать запрос как:

σ[sno=16](Supplier) ⋈ Supply ⋈ σ[pcolor=red](Part)

Система базы данных может определить, будет ли это быстрее, используя знания о хранилище, такие как любые доступные индексы и размер рассматриваемых отношений.

Эта новая модель положила начало «великой дискуссии» между Тедом Коддом (поддерживающим реляционную модель и в основном поддерживаемым академиками) и Чарли Бахманом (поддерживающим CODASYL и в основном поддерживаемым пользователями СУБД).

CODASYL критиковали за то, что он одновременно слишком сложный и слишком негибкий, чтобы представлять обычные ситуации. Программирование с одновременной записью также считалось слишком сложным для оптимизации.

Сторонники CODASYL отреагировали на эту критику, представив свои собственные языки запросов, устанавливаемые по времени, которые также позволили бы улучшить физическую и логическую независимость данных. Также были попытки очистить модель, чтобы облегчить понимание.

Реляционную модель критиковали за то, что она слишком академична: запросы реляционной алгебры было нелегко читать или понимать. Кроме того, в реляционной модели не было предложения о физическом хранилище, поэтому изначально не было ясно, можно ли построить эффективную реализацию.

Сторонники реляционных отношений ответили на это созданием «естественных» языков запросов, основанных на реляционной алгебре, таких как SQL. Такие реализации, как System R и INGRES, в конечном итоге доказали, что модель жизнеспособна и что автоматическая оптимизация запросов может быть конкурентоспособной даже с очень опытными программистами.

Таким образом, два лагеря ответили на критику друг друга и попытались найти решения. На практике эти различия не имели такого большого значения, как можно было ожидать. Компания IBM, ранее полностью поддерживающая IMS, изменила свою настройку в 1984 году и объявила о двойной поддержке IMS и DB / 2 (ранней реляционной базы данных). DB / 2 была более новой и простой в использовании технологией, поэтому, естественно, она была выбрана вместо IMS. Этого преимущества было достаточно, чтобы решить проблему.

По существу, это также сделало SQL языком запросов. В настоящее время реляционный и SQL часто рассматриваются как синонимы, но в то время у SQL была конкуренция (например, QUEL). Есть люди, которые считают SQL не лучшим языком для реляционной модели, такие как Хью Дарвен и C. Дж. Дате , авторы Третьего манифеста . Одна из их критических замечаний в отношении SQL заключается в том, что он не совсем то же самое, что и реляционная модель. Например, SQL допускает дополнительное значение NULL для отсутствующей или неизвестной информации. Отношения SQL также допускают дублирование строк, то есть они не являются наборами.

Итак, наши уроки:

7. Постоянно устанавливаемые языки хороши, независимо от модели данных, поскольку они предлагают значительно улучшенную физическую независимость от данных.

8. Логическая независимость данных проще с простой моделью данных, чем со сложной.

9. Технические дебаты обычно разрешаются слонами на рынке, и часто по причинам, не имеющим ничего общего с технологиями.

10. Оптимизаторы запросов могут превзойти всех, кроме лучших программистов приложений СУБД.

В следующий раз…

Мы рассмотрели три эпохи моделей данных: IMS, CODASYL и реляционные. Мы убедились в важности физической и логической независимости данных, ограничениях иерархических моделей и преимуществах языков запросов высокого уровня, устанавливаемых одновременно.

В Grakn Labs мы создаем базу знаний и пытаемся следовать этим урокам. У нас есть высокоуровневый язык запросов, устанавливаемый во время, со встроенными логическими рассуждениями, обеспечивающими высокую логическую независимость данных. Кроме того, мы используем гибкую модель отношений сущностей (которую вы увидите в следующем посте) для структурирования наших данных.

Реляционные базы данных продолжают доминировать и остаются чрезвычайно популярной моделью данных даже тридцать лет спустя. Тем не менее, недавняя конкуренция со стороны других моделей, таких как графовые базы данных и NoSQL, сделала современный ландшафт баз данных намного более разнообразным и предоставила разработчикам новый набор инструментов. В следующем сообщении блога мы рассмотрим некоторые из ключевых пост-реляционных моделей:

  • Сущность-отношения
  • Расширенный реляционный
  • Семантический
  • Объектно-ориентированный
  • Объектно-реляционный
  • Полуструктурированный (XML)

Если вам понравилась эта статья, нажмите кнопку хлопка ниже, чтобы ее могли найти и другие. Если у вас есть какие-либо вопросы или комментарии, свяжитесь с нами, ниже, через наш канал сообщества Slack или через наш дискуссионный форум.

Узнайте больше на https://grakn.ai.

Изображение предоставлено: Крупный план разностной машины Бэббиджа №2 от Ларри Джонсона под лицензией CC BY 2.0