neithere

Python, Music, Laziness

О базах данных

дата
2009-02-13, UPD: 2009-02-21.
see also
http://neithere.livejournal.com/431474.html – duck typing for data

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

Реляционные СУБД

Реляционная модель позволяет сконцентрировать информацию о неком объекте в виде ячеек одной строки таблицы и установить связи между строками разных таблиц. Модель имеет серьезный недостаток: заранее жестко фиксируется и типизируется набор свойств объекта. В результате сфера применения такой модели относительно узка. Тем не менее, на практике реляционные СУБД используются повсеместно ценой значительной костылеёмкости (к которой мы настолько привыкли, что не осознаем всей нелепости универсального применения этой модели). Иногда для повышения гибкости БД практикуется создание EAV-хранилищ поверх реляционной СУБД. Таким образом значительно снижается производительность, но обеспечивается гибкость.

Triplestore

Хранилище фактов (triplestore) в виде триплетов (объект,предикат,субъект) – очень гибкий способ управляемого хранения данных. Факты образуют семантическую сеть. С помощью правил нетрудно автоматически вывести новые факты из имеющихся. Если в реляционных СУБД строка таблицы содержит в себе данные, то в семантической сети узел не содержит ничего кроме идентификатора. Зато можно найти факты, ссылающиеся на данный узел: эти факты и есть описание узла.

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

? В каком году родился Джон? : (john born_in ?) ? Кто родился в 1900 году? : (? born_in 1900) ? Когда кто родился? : (? born_in ?) ? Что происходило в 1900 году? : (? ? 1900)

Итак, мы используем простой шаблон и получаем по нему набор фактов. Что характерно, при составлении запроса мы не обязаны учитывать особенности распределения этих данных по таблицам. Нормализация данных вообще не требуется, поэтому структура “идеальна” и способна вместить любую информацию. Нет ограничений на количество свойств узла и количество значений свойства (если только это явным образом не указано в метаданных). Безусловно, это очень удобно.

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

Например, нам нужно узнать имена родившихся в 1900 году. Запрос (? born_in 1900) вернет нам факты с искомыми идентификаторами объектов:

(john born_in 1900), (mary born_in 1900), ..., где john и mary – идентификаторы.

Затем нужно будет сделать целый ряд дальнейших запросов для получения дополнительных свойств этих объектов:

name_facts = []
for birth_fact in get_facts('? born_in 1900'):
    name_facts += get_facts('%s name ?', birth_fact._id)
names = [f.object for f in name_facts]

Для сокращения числа запросов следует внедрить в нотацию переменные:

(?person born_in 1900)-->(?person name ?)

Это эквивалентно join’ам или подзапросам в SQL. Уже в таком базовом случае мы отходим от полностью декларативной нотации. Сложность запросов возрастает в соответствии с количеством узлов и свойств, по которым проводится отбор данных. Приведем один из компактных, но трудных случаев. Запрос на русском языке: “Как люди с фамилией Джонсон связаны с городом Нью-Йорк?”. Тот же запрос в виде триплетов с промежуточными переменными:

(?person ? ?city) where
(?person type 'person'; last_name 'Johnson')
(?city type 'city'; name 'New York')

Ответом будет набор фактов, где искомым параметром является тип связи.

Языки запросов. SQL рожден мертвым

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

  • декларативный язык запросов (à la SQL) с поддержкой промежуточных переменных;
  • обработка данных средствами высокоуровневых языков общего назначения:
    • на стороне сервера или
    • на стороне клиента.

Усилия по адаптации SQL к триплетам привели к появлению, например, SPARQL. Им можно пользоваться, но трудно утверждать, что он достаточно прост. В целом он весьма близок к последнему примеру, но добавьте туда указание пространств имен для каждого элемента и получите весьма непростой для чтения синтаксис. Кроме того, параллельное существование одних нотаций для записи данных (таких как N-Triples, N3, Turtle) и совершенно иных для их поиска (SPARQL) вызывает сомнения в уместности как тех, так и других.

Следует отметить, что и сам SQL трудно назвать удачным языком. Целевая аудитория не пишет запросы, она пользуется ссылками и кнопками. А программисты предпочли бы написать запрос на языке программы, над которой работают. Попытка создать универсальный и понятный всем язык напоминает рассказы середины прошлого века, где умная машина в две тысячи энном году общается с человеком путем распечатки рубленых фраз на бумаге. Нет, всё не так. SQL слишком примитивен для разработчика и слишком сложен для пользователя. Поэтому пользователь вообще его игнорирует, а разработчик возводит леса костылей.

Автор заметки полагает, что наиболее перспективной является разработка хорошего API для полноценных языков программирования (как на стороне клиента, так и на стороне сервера) в сочетании с сериализацией данных в JSON.

Сериализация данных

Языки

Наиболее популярными языками сериализации данных являются XML и JSON. Они описывают ориентированные графы.

XML для сериализации является, возможно, чересчур гибким, поскольку невозможна однозначная интерпретация (литерал может быть атрибутом узла или вложенным узлом). Для устранения этой проблемы используются <http://xmlhack.ru/texts/02/followNose/followNose.html> схемы.

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

Источники

Сериализация таблиц реляционных баз данных требует полного структурного соответствия источника получателю (или механизмов трансляции <http://en.wikipedia.org/wiki/Extract,_transform,_load>); кроме того, важны соглашения о том, где при сериализации по внешнему ключу произойдет агрегация, а где ключ останется в виде числа.

Сериализация триплетов значительно проще. Граф заведомо смешанный, поэтому есть смысл в следующих вариантах:

  1. список фактов, где каждый факт состоит из трех URI (напр. в виде пар namespace+id) – удобно для передачи атомарных изменений при регулярной синхронизации;
  2. список узлов, где в информацию об узле входит не только ключ, но и все свойства, включая исходящие связи (т.е. факты, где данный узел является объектом).

Интересно, что второй пункт точно соответствует принципам документных (document-oriented) баз данных. Более того, указанная структура данных в формате JSON лежит в основе одной из _реализаций_ этих принципов.

Document-oriented

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

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

Одной из перспективных реализаций документоориентированного подхода является CouchDB. Что характерно, она позволяет проводить выборку средствами любого языка программирования на стороне сервера БД. Это означает, что можно использовать весьма выразительные средства обработки данных. Другие реализации, достойные упоминания – MongoDB и StrokeDB. К числу ДОБД можно отнести и Tokyo Cabinet/Tyrant при условии, что используется тип хранилища “table”.

Различные нотации для описания триплетов вполне могут использоваться и с документоориентированной моделью как язык сериализации.

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

Схемы для “бессхемных” хранилищ

TODO

(см. мой пост о динамической типизации данных и представлении их в моделях.)

Заключение

– Да это всё понятно; ты мне лучше скажи, как повидло в конфеты засовывают!

Дальнейшие темы

В заметке не затронута проблема описания сложных концептов. Например, “кот Васька сидит на коврике” или “Первые опыты по хромированию собак провел румынский академик Петрович”. Затруднительно выразить эти мысли триплетами, документами и так далее. Одно из решений – концепт-графы (см. также работы John Sowa: Conceptual Graphs including Examples).