В чем разница между реляционной и нереляционной базой данных

O(1) vs O(n2)

В настоящее время многие разработчики не заботятся о временной сложности алгоритмов … и они правы!


Но когда вы имеете дело с большим количеством данных (я не говорю о тысячах) или если вы боретесь за миллисекунды, становится критически важным понять эту концепцию. И как вы понимаете, базы данных должны иметь дело с обеими ситуациями! Я не заставлю вас потратить больше времени, чем необходимо чтобы ухватить суть. Это поможет нам позже понять концепцию оптимизации на основе затрат (cost based optimization).

Концепция

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

Например, когда я говорю «этот алгоритм имеет сложность O (some_function() )», это означает, что для обработки определенного объема данных алгоритму требуется some_function(a_certain_amount_of_data) операций.

При этом важно не количество данных**, а то, ** как увеличивается количество операций при увеличении объема данных. Сложность по времени не дает точное количество операций, но хороший способ для оценки времени выполнения

На этом графике вы можете увидеть зависимость числа операций от объема входных данных для различных типов временных сложностей алгоритмов. Я использовал логарифмическую шкалу, чтобы отобразить их. Другими словами, количество данных быстро увеличивается с 1 до 1 млрд. Мы можем увидеть, что:

  • O(1) или постоянная сложность остаются постоянными (иначе это не будет называться постоянной сложностью).
  • O(log(n)) остается низкой даже с миллиардами данных.
  • Наихудшая сложность — O(n2), где количество операций быстро растет.
  • Две другие сложности так же быстро увеличиваются.

Примеры

При небольшом количестве данных разница между O(1) и O(n2) незначительна. Например, предположим, что у вас есть алгоритм, который должен обрабатывать 2000 элементов.

  • Алгоритм O (1) обойдется вам в 1 операцию
  • Алгоритм O (log (n)) обойдется вам в 7 операций
  • Алгоритм O (n) обойдется вам в 2 000 операций
  • Алгоритм O (n * log (n)) обойдется вам в 14 000 операций
  • Алгоритм O (n2) обойдется вам в 4 000 000 операций

Как я уже сказал, по-прежнему важно знать эту концепцию при работе с огромным количеством данных. Если на этот раз алгоритм должен обработать 1 000 000 элементов (что не так уж много для базы данных):

  • Алгоритм O (1) обойдется вам в 1 операцию
  • Алгоритм O (log (n)) обойдется вам в 14 операций
  • Алгоритм O (n) обойдется вам в 1 000 000 операций
  • Алгоритм O (n * log (n)) обойдется вам в 14 000 000 операций
  • Алгоритм O (n2) обойдется вам в 1 000 000 000 000 операций

Я не делал расчетов, но я бы сказал, что с помощью алгоритма O (n2) у вас есть время выпить кофе (даже два!). Если вы добавите еще 0 к объему данных, у вас будет время, чтобы вздремнуть.

Идем глубже

Для справки:

  • Поиск в хорошей хеш-таблице находит элемент за O (1).
  • Поиск в хорошо сбалансированном дереве дает результат за O (log (n)).
  • Поиск в массиве дает результат за O (n).
  • Лучшие алгоритмы сортировки имеют сложность O (n * log (n)).
  • Плохой алгоритм сортировки имеет сложность O (n2).

Примечание: в следующих частях мы увидим эти алгоритмы и структуры данных.

Есть несколько типов временной сложности алгоритма:

  • сценарий среднего случая
  • лучший вариант развития событий
  • и худший сценарий

Временная сложность часто является наихудшим сценарием.

Я говорил только о временной сложности алгоритма, но сложность также применима для:

  • потребления памяти алгоритмом
  • потребления дискового ввода / вывода алгоритмом

Конечно, есть сложности хуже, чем n2, например:

  • n4: это ужасно! Некоторые из упомянутых алгоритмов имеют такую сложность.
  • 3n: это еще хуже! Один из алгоритмов, которые мы увидим в середине этой статьи, имеет эту сложность (и он действительно используется во многих базах данных).
  • факториал n: вы никогда не получите свои результаты даже с небольшим количеством данных.
  • nn: если вы столкнетесь с этой сложностью, вы должны спросить себя, действительно ли это ваша сфера деятельности …

Подходы

Я пришел к выводу, что целесообразно выделить подходы:

  1. Сравнение схем целевой БД и БД-источника.
  2. Сравнение заскриптованной схемы (и данных) с целевой БД.
  3. На основе последовательных (инкрементальных) ручных SQL-скриптов.
  4. На основе ручных независимых SQL-скриптов, структура которых повторяет схему БД.

В этом списке подходы отсортированы по увеличению полезности.

  1. https://habrahabr.ru/post/121265/ — описывает кратко подходы 2, 3. Еще есть подход с последовательностью идемпотентных изменений, но я его откидываю ввиду слишком высокой сложности поддержки идемпотентности скриптов, когда их количество велико. Не считая того, что просто запустить 1000 скриптов, даже если они ничего не будут в итоге изменять, тоже занимает время (и размер лог-файла наката). Тут должен быть подход «если изменение уже накатано, не надо его накат повторять» (п5).
  2. https://habrahabr.ru/post/258005/ – комбинация подходов 3 и 1 — на основе redgate SQL Source Control и redgate SQL Compare. (статья плохо описывает работу с БД, в основном она о любви к Atlassian) – как я понял, сначала, при коммите, они накатывают скрипты на DB QA, потом сравнением схемы оно переносится на prod.
  3. https://habrahabr.ru/post/312970/ — хорошая длинная статья, подход очень похож на предыдущую статью. Используют CI, чтобы на каждый коммит накатывались изменения на БД QA, и выкатывался артефакт-накопительный скрипт изменений БД для наката на prod. Смысл этого артефакта не очень понятен, если сами скрипты в коммите. Квинтэссенция в картинке.

В целом к идеи автоматизации наката скриптов по коммиту я бы отнесся крайне настороженно – иногда бывает, что коммиты делаются неготовыми или неполными. Дисциплинарное правило «коммить в мастер только готовый код» на практике работает очень плохо. Лучше его избегать улучшением инструментария – для этого существует класс инструментов continuous integration (например, TeamCity от JetBrains или совсем бесплатный Jenkins). Я за то, чтобы накат скриптов на БД происходил исключительно осознанно человеком-программистом и только в нужные моменты времени – которые никак не должны быть связаны с коммитом.

Результаты

Итак, исходные результаты — это логи YCSB, с каждого клиента. Выглядят эти логи примерно так (показан финальный кусочек файла):

Как видишь, здесь есть количество операций определенного типа (в данном примере — чтения), средняя, минимальная и максимальная задержки, задержка, в которую уложились 95 и 99% операций, количество успешных операций (код возврата 0), общее время теста, общее количество всех операций и среднее количество операций в секунду. Нас больше всего интересует средняя задержка (AverageLatency) и количество операций в секунду (Throughput).

С помощью очередного скрипта на Python данные из кучи логов собирали в табличку, а по табличке строили красивые графики.

Скорость вставки на SSDСкорость вставки в памятьПроизводительность при интенсивной записи на SSDПроизводительность при интенсивной записи в памятиПроизводительность при 95% чтения на SSDПроизводительность при 95% чтения в памяти 

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

Ведущими СУБД в настоящее время являются реляционные, прогноз 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, я бы отметил, что подобные реализации одной модели поверх другой не кажутся удачными в первую очередь с точки зрения языкового дизайна. Требуется расширять один язык другим, языки не вполне «ортогональны», правила сочетаемости могут быть довольно причудливы.

Примечания

  1. ↑ .
  2. ↑ .
  3. В частности, ничто не препятствует визуально представить отношение таблицей, в которой столбцы будут соответствовать не атрибутам, а кортежам, а строки — не кортежам, а атрибутам. То есть соотнесение кортежей отношения со строками таблицы, а атрибутов отношения со столбцами таблицы является лишь данью традиции, но не имеет никакой теоретической обусловленности.
  4. Необходимо помнить, что «таблица» чаще всего означает не «отношение» как , а визуальное представление отношения на бумаге или экране. Некорректное и нестрогое использование термина «таблица» вместо термина «отношение» нередко приводит к недопониманию. Наиболее частая ошибка состоит в рассуждениях о том, что реляционная модель данных имеет дело с «плоскими», или «двумерными» таблицами, тогда как таковыми могут быть только визуальные представления таблиц. Отношения же являются абстракциями, и не могут быть ни «плоскими», ни «неплоскими».
  5. С. J. Date. What First Normal Form Really Means //С. J. Date. Date on database: Writings 2000—2006, Apress, 2006, ISBN 978-1-59059-746-0

Мир объектов, систем и решений

Реальные объекты и действующие системы объединяются в области применения человеком, принимающим решения. Сам факт посещения ресурса, обращения к объекту, использование системы имеет цель и полученный результат.

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

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

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

Представления о преимуществах и недостатках

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

Одни авторы относят к преимуществам:

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

Другие смотрят на преимущества иначе:

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


Недостатки определяют обычно так:

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

Фактически области применения обуславливают различные объекты базы данных, что формирует отличия в критериях оценки преимуществ и недостатков. То что не имеет значения в одной области применения, крайне актуально в другой. Одна и та же база данных может стать причиной успеха или испортить все дело.

SQL vs. NoSQL: MySQL или MongoDB

Разобравшись с ключевыми структурными различиями SQL и NoSQL баз данных, стоит внимательно рассмотреть их функциональные особенности на примере MySQL и MongoDB.

MySQL: реляционная СУБД

Преимущества MySQL:

  • Проверено временем: MySQL — крайне развитая СУБД, что означает наличие большого сообщества вокруг неё, множество примеров и высокую надёжность;
  • Совместимость: MySQL доступна на всех основных платформах, включая Linux, Windows, Mac, BSD и Solaris. Также у неё есть библиотеки для языков вроде Node.js, Ruby, C#, C++, Java, Perl, Python и PHP;
  • Окупаемость: Это СУБД с открытым исходным кодом, находящаяся в свободном доступе;
  • Реплицируемость: Базу данных MySQL можно распределять между несколькими узлами, таким образом уменьшая нагрузку и улучшая масштабируемость и доступность приложения;
  • Шардинг: В то время как шардинг невозможен на большинстве SQL баз данных, MySQL является исключением.

MongoDB: нереляционная СУБД

Преимущества MongoDB:

  • Динамическая схема: Как упоминалось выше, эта СУБД позволяет гибко работать со схемой данных без необходимости изменять сами данные;
  • Масштабируемость: MongoDB горизонтально масштабируема, что позволяет легко уменьшить нагрузку на сервера при больших объёмах данных;
  • Удобство в управлении: СУБД не нуждается в отдельном администраторе базы данных. Благодаря достаточному удобству в использовании, ей легко могут пользоваться как разработчики, так и системные администраторы;
  • Скорость: Высокая производительность при выполнении простых запросов;
  • Гибкость: В MongoDB можно без вреда для существующих данных, их структуры и производительности СУБД добавлять поля или колонки.

Какую СУБД выбрать?

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

Разница между реляционной и нереляционной базой данных

Определение

Реляционная база данных — это база данных, основанная на реляционной модели данных, предложенной EF Codd в 1970 году. Нереляционная база данных, с другой стороны, представляет собой тип базы данных, которая обеспечивает механизм для хранения и извлечения данных, которые моделируются таким образом, кроме табличных отношений, используемых в реляционных базах данных.

Synonms

Реляционные базы данных также называются базами данных SQL, в то время как нереляционные базы данных также называются базами данных NoSQL.

присоединяется

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

Типы

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

использование

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

Примеры

MySQL, SQLite3 и PostgreSQL — это некоторые СУБД, использующие реляционные базы данных. Cassendra, Hbase, MongoDB и Neo4 — некоторые нереляционные базы данных.

Заключение

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


С этим читают