Sql или nosql

Введение

Объектно-ориентированное программирование (ООП) стало революционным
подходом в 1980-е годы []. В 1990-х годах применение ООП стало
важнейшей областью исследований и разработок применительно к реляционным системам
управления базами данных (СУБД) . В 1996
г. была выпущена объектно-реляционная СУБД Informix Universal Server

Несмотря на
важность и актуальность классической реляционной и объектно-реляционной моделей,
тем не менее остается много нерешенных проблем

В данной статье кратко описаны основные ограничения реляционных
и объектно-реляционных технологий, и для их разрешения предложена структура данных
в виде дерева объектов.

Ограничения реляционных баз данных

В реляционной модели каждая запись об объекте
находится в отношении с некоторым набором атрибутов. Количество атрибутов
(полей) в таблице может измеряться десятками и даже сотнями. С увеличением длины
записи (количества и размера атрибутов) падает производительность, поскольку требуется
больше дисковых операций ввода/вывода. Разбиение широкой таблицы на несколько узких
с меньшим числом атрибутов потребует операций соединения (join) и во многих случаях
является неэффективным.

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

exp (v_i) ~ n (1)

или

v_i ~ ln (n) , (2)

в то время как зависимость между скоростью последовательного
перебора и размером выборки пропорциональная:

v ~ n · k , (3)

где v — скорость последовательного перебора,
v_i — скорость поиска с использованием индекса
i, n — количество записей в таблице,k — количество колонок в таблице.

Применение индексов наиболее эффективно при большом количестве
узких записей, а не широких []. Вдобавок, индексы имеют свои
недостатки:

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

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

Конечно, есть дополнительные типы данных, определяемые пользователем,
а также большие двоичные BLOB и текстовые CLOB-объекты. Однако, и у них есть свои
ограничения. Например, поля BLOB и CLOB не могут быть упорядочены или проиндексированы
и должны обрабатываться на стороне клиента.

Использование преимуществ объектно-реляционных технологий

Informix Universal Server
— это СУБД объектно-реляционного типа, созданная путем внедрения технологии ООП
в популярную СУБД Informix Dynamic Server. Она обладает следующими свойствами ООП:

• абстрактные типы данных,
• наследование,
• иерархии данных и типов.

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

К тому же определение новых типов в СУБД Informix Universal
Server может вызвать отрицательные последствия, т. к. потребуются навыки опытных
программистов по разработке на языке C процедур и методов хранения, доступа и индексирования
данных.

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

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

Состав частей реляционной модели данных

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

Структурная часть

Структурная часть (аспект), отвечает за принцип построения структуры реляционной базы данных на нормализированном наборе n-арных отношений, в форме таблиц

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

Манипуляционная часть

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

Целостная часть

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

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

Мультимодельные СУБД на основе реляционной модели

Ведущими СУБД в настоящее время являются реляционные, прогноз Gartner нельзя было бы считать сбывшимся, если бы РСУБД не демонстрировали движения в направлении мультимодельности. И они демонстрируют. Теперь соображения о том, что мультимодельная СУБД подобна швейцарскому ножу, которым ничего нельзя сделать хорошо, можно направлять сразу Ларри Эллисону.

Автору, однако, больше нравится реализация мультимодельности в Microsoft SQL Server, на примере которого поддержка РСУБД документной и графовой моделей и будет описана.

Документная модель в MS SQL Server

О том, как в MS SQL Server реализована поддержка документной модели, на Хабре уже было две отличных статьи, ограничусь кратким пересказом и комментарием:

• Работаем с JSON в SQL Server 2016
• SQL Server 2017 JSON

Способ поддержки документной модели в MS SQL Server достаточно типичен для реляционных СУБД: JSON-документы предлагается хранить в обычных текстовых полях. Поддержка документной модели заключается в предоставлении специальных операторов для разбора этого JSON:

• для извлечения скалярных значений атрибутов,
• для извлечения поддокументов.

Вторым аргументом обоих операторов является выражение в JSONPath-подобном синтаксисе.

Абстрактно можно сказать, что хранимые таким образом документы не являются в реляционной СУБД «сущностями первого класса», в отличие от кортежей. Конкретно в MS SQL Server в настоящее время отсутствуют индексы по полям JSON-документов, что делает затруднительными операции соединения таблиц по значениям этих полей и даже выборку документов по этим значениям. Впрочем, возможно создать по такому полю вычислимый столбец и индекс по нему.

Дополнительно MS SQL Server предоставляет возможность удобно конструировать JSON-документ из содержимого таблиц с помощью оператора — возможность, в известном смысле противоположную предыдущей, обычному хранению. Понятно, что какой бы быстрой ни была РСУБД, такой подход противоречит идеологии документных СУБД, по сути хранящих готовые ответы на популярные запросы, и может решать лишь проблемы удобства разработки, но не быстродействия.

Наконец, MS SQL Server позволяет решать задачу, обратную конструированию документа: можно разложить JSON по таблицам с помощью . Если документ не совсем плоский, потребуется использовать .

Графовая модель в MS SQL Server

Поддержка графовой (LPG) модели реализована в Microsoft SQL Server тоже вполне предсказуемо: предлагается использовать специальные таблицы для хранения узлов и для хранения ребер графа. Такие таблицы создаются с использованием выражений и соответственно.

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

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

Проиллюстрируем сказанное примером. Пусть графовые данные имеют схему как на приведенном рисунке. Тогда для создания соответствующей структуры в базе данных нужно выполнить следующие DDL-запросы:

Основная специфика таких таблиц заключается в том, что в запросах к ним возможно использовать графовые паттерны с Cypher-подобным синтаксисом (впрочем, «» и пр. пока не поддерживаются). Также на основе измерений производительности можно предположить, что способ хранения данных в этих таблицах отличен от механизма хранения данных в обычных таблицах и оптимизирован для выполнения подобных графовых запросов.

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

Подводя итог описанию реализаций документной и графовой моделей в MS SQL Server, я бы отметил, что подобные реализации одной модели поверх другой не кажутся удачными в первую очередь с точки зрения языкового дизайна. Требуется расширять один язык другим, языки не вполне «ортогональны», правила сочетаемости могут быть довольно причудливы.

Примеры типичных операторов поиска данных

• найти указанное дерево БД;
• перейти от одного дерева к другому;
• найти экземпляр сегмента, удовлетворяющий условию поиска;
• перейти от одного сегмента к другому внутри дерева;
• перейти от одного сегмента к другому в порядке обхода иерархии.

Примеры типичных операторов поиска данных с возможностью модификации:

• найти и удержать для дальнейшей модификации единственный экземпляр сегмента, удовлетворяющий условию поиска;
• найти и удержать для дальнейшей модификации следующий экземпляр сегмента с теми же условиями поиска;
• найти и удержать для дальнейшей модификации следующий экземпляр для того же родителя.

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

• вставить новый экземпляр сегмента в указанную позицию;
• обновить текущий экземпляр сегмента;
• удалить текущий экземпляр сегмента.

В иерархической модели автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя.

Иерархическая структура объектов

Дерево объектов [] представляет собой информационную
систему для хранения иерархической структуры объектов. Задача усложняется тем, что
у объектов допускается произвольное количество атрибутов — десятки, сотни и более,
каждый из которых может быть в Informix любого типа (целый, вещественный, десятичный,
строковый, дата/время и т. д.). Все это предусмотрено в представленной структуре
данных.

Система иерархических таблиц и расширенных типов данных построена
на базе Informix Universal Server и Informix Web DataBlade. Но при этом используются
стандартные методы доступа, т. е. нет необходимости программировать обработчики.
Поэтому данная структура данных может быть реализована как на платформе Informix
Universal Server, так и Informix Dynamic Server.

Структура данных () создана в СУБД
Informix посредством SQL и состоит из таблиц, описанных ниже. Для их модификации
разработаны хранимые процедуры. Пример создания таблиц и процедур их модификации
приведен в отдельном файле ().

Рис. 1. Структура данных для хранения иерархических объектов

Таблица objects_tree

Таблица objects_tree содержит информацию как об объектах-родителях,
так и объектах-потомках иерархического дерева.

Атрибуты (колонки) таблицы objects_tree:

obt_id — ID записи об объекте,dlv_id — ссылка на ID в таблице подразделений,obj_name — любой текст,ch_ar — символ-признак архивности записи, используемый для хранения информации
об удаленных объектах.

Для добавления, модификации и удаления объектов используются
хранимые процедуры. При удалении объекта не производится рекурсивное удаление всех
его потомков. Иначе говоря, если у объекта есть потомки, он не может быть удален.
Если потомки объекта не удалены, процедура возвращает код ошибки SQL. Это сделано
в целях безопасности данных. Реализация рекурсивного удаления потомков в хранимой
процедуре повысит вероятность случайного удаления целой ветви дерева объектов.

Таблица objects_parents

Каждая запись в таблице objects_parents () содержит ссылку на объект-родитель и соответствующий ему объект-потомок в
таблице objects_tree.

Оба поля — ID предка и ID потомка — ссылаются на таблицу objects_tree.
Новые отношения родитель-потомок добавляются посредством хранимой процедуры. Для
улучшения производительности родительский и дочерний объекты назначаются совместно.
Но модификации не допускаются, для этого соответствующая запись должна быть удалена
прямым вызовом SQL оператора а затем новая запись
добавляется путем вызова хранимой процедуры.

Каждый объект в структуре базы данных может иметь произвольное
количество потомков и предков, как показано в .

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

Управляющая часть иерархической модели

В рамках иерархической модели выделяют языковые средства описания данных (ЯОД) и средства манипулирования данными (ЯМД). Каждая физическая база описывается набором операторов, обусловливающих как её логическую структуру, так и структуру хранения БД. При этом способ доступа устанавливает способ организации взаимосвязи физических записей.

Определены следующие способы доступа:

• иерархически последовательный;
• иерархически индексно-последовательный;
• иерархически прямой;
• иерархически индексно-прямой;
• индексный.

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

Среди операторов манипулирования данными можно выделить операторы поиска данных, операторы поиска данных с возможностью модификации, операторы модификации данных. Набор операций манипулирования данными в иерархической БД невелик, но вполне достаточен.

Преобразование концептуальной модели в иерархическую модель данных

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

Преобразование связи типа «один ко многим» между предком и потомком осуществляется практически автоматически в том случае, если потомок имеет одного предка, и происходит это следующим образом. Каждый объект с его атрибутами, участвующий в такой связи, становится логическим сегментом. Между двумя логическими сегментами устанавливается связь типа «один ко многим». Сегмент со стороны «много» становится потомком, а сегмент со стороны «один» становится предком.

Ситуация значительно усложняется, если потомок в связи имеет не одного, а двух и более предков. Так как подобное положение является невозможным для иерархической модели, то отражаемая структура данных нуждается в преобразованиях, которые сводятся к замене одного дерева, например, двумя (если имеется два предка). В результате такого преобразования в базе данных появляется избыточность, так как единственно возможный выход из этой ситуации — дублирование данных.

Основные недостатки

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

Реляционные СУБД все еще доминируют в системах обработки финансовых транзакций, но сегодня компании все шире применяют СУБД новой архитектуры NoSQL — горизонтально масштабируемые, распределенные и разрабатываемые в открытых кодах. Примеры таких систем — Hadoop, MapReduce и VoltDB. По оценкам аналитиков Forrester, около 75% данных на предприятиях это либо полуструктурированная информация (XML, электронная почта и EDI), либо неструктурированная (текст, изображения, аудио и видео), и лишь 5% от этих данных хранится в реляционных СУБД, а остальное — в базах других типов или в виде файлов, и неподвластно обработке реляционными системами.

По мнению Блора, реляционные СУБД «могут умереть так, что этого никто не заметит» — например, если Oracle в своей СУБД попросту заменит SQL-механизм на NoSQL. Таким механизмом, считает аналитик, могла бы стать одна из существующих сегодня столбцовых СУБД.

Структурная часть иерархической модели

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

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

Иерархическая модель представляет собой связный неориентированный граф древовидной структуры, объединяющий сегменты. Иерархическая БД состоит из упорядоченного набора деревьев.

Что такое Иерархическая база данных?

В иерархической базе данных данные организованы в древовидной структуре. Каждая отдельная информация хранится в поле, а поля, в свою очередь, формируют записи. Доступ к этим данным осуществляется с помощью связей между ними. В этой структуре все записи данных связаны, наконец, с одной родительской записью. Он также называется записью владельца. Связи между записями часто описываются как отношения родитель-ребенок. Наилучшим использованием иерархической базы данных является ее развертывание в библиотечной системе, поскольку она хранит имена или номера книг, используя десятичную систему Dewey. Эта система напоминает древовидную структуру, разделяя одно и то же родительское число, а затем ветви, как деревья. Аналогично, мы можем использовать его для хранения имен в телефонной книге.

Мультимодельные СУБД «без основной модели»

На рынке также представлены СУБД, позиционирующие себя как изначально мультимодельные, не имеющие никакой унаследованной основной модели. К их числу относятся ArangoDB, OrientDB (c 2018 года компания-разработчик принадлежит SAP) и CosmosDB (сервис в составе облачной платформы Microsoft Azure).

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

Эти модели являются в указанных СУБД единственно доступными для использования, для работы с ними предназначены собственные языки запросов. Безусловно, такие модели и СУБД перспективны, однако отсутствие совместимости со стандартными моделями и языками делает невозможным использование этих СУБД в унаследованных системах — замену ими уже используемых там СУБД.

Про ArangoDB и OrientDB на Хабре уже была замечательная статья: JOIN в NoSQL базах данных.

ArangoDB

ArangoDB заявляет поддержку графовой модели данных.

Узлы графа в ArangoDB — это обычные документы, а ребра — документы специального вида, имеющие наряду с обычными системными полями (, , ) системные поля и . Документы в документных СУБД традиционно объединяются в коллекции. Коллекции документов, представляющих ребра, в ArangoDB называются edge-коллекциями. К слову, документы edge-коллекций — это тоже документы, поэтому ребра в ArangoDB могут выступать также и узлами.

OrientDB

В основе реализации графовой модели поверх документной в OrientDB лежит возможность полей документов иметь помимо более-менее стандартных скалярных значений еще и значения таких типов, как , , , и . Значения этих типов — ссылки или коллекции ссылок на системные идентификаторы документов.

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

Как и в ArangoDB, в OrientDB ребра представляются отдельными документами (хотя если у ребра нет своих свойств, его можно сделать легковесным, и ему не будет соответствовать отдельный документ).

Azure CosmosDB

В меньшей степени сказанное выше об ArangoDB и OrientDB относится к Azure CosmosDB. CosmosDB предоставляет следующие API доступа к данным: SQL, MongoDB, Gremlin и Cassandra.

SQL API и MongoDB API используются для доступа к данным в документной модели. Gremlin API и Cassandra API — для доступа к данным соответственно в графовой и колоночной. Данные во всех моделях сохраняются в формате внутренней модели CosmosDB: ARS («atom-record-sequence»), которая также близка к документной.

Но выбранная пользователем модель данных и используемый API фиксируются в момент создания аккаунта в сервисе. Невозможно получить доступ к данным, загруженным в одной модели, в формате другой модели, что иллюстрировалось бы примерно таким рисунком:

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

Техническое определение

Дерево представляет собой набор объектов, называемых узлами. Узлы соединены ребрами. Каждый узел содержит значение или данные, и он может иметь или не иметь дочерний узел.

Первый узел дерева называется корнем. Если этот корневой узел соединен с другим узлом, тогда корень является родительским узлом, а связанный с ним узел — дочерним.

Все узлы дерева соединены линиями, называемыми ребрами. Это важная часть деревьев, потому что она управляет связью между узлами.

Листья — это последние узлы на дереве. Это узлы без потомков. Как и в реальных деревьях, здесь имеется корень, ветви и, наконец, листья.

Другими важными понятиями являются высота и глубина.

Высота дерева — это длина самого длинного пути к листу.

Глубина узла — это длина пути к его корню.