Sequels to SQL

[c8ne]

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

SQL это внешний DSL для работы с данными. Как таковой, он удобен для достаточно большого количества задач, но он не проектировался как полноценный язык программирования. Даже встроенные процедуры были стандартизованы относительно недавно, и этот стандарт поддерживается далеко не везде. Однако, с точки зрения анализа используемых инструментов сознания - это не важно. Язык оценивается не по тому, как и какие языки с ним взаимодействуют, а по внутренней логике языка. А здесь у SQL большие проблемы с уровнем абстракции, которые с одной стороны снижают барьер входа, а с другой стороны лишают разработчиков необходимых инструментов. И скидок на то, что он DSL, здесь я давать не собираюсь.

Так же, нужно разобраться с термином поддерживает. Теоретически, на SQL можно выразить любую структуру данных, но некоторые структуры, требуют, чтобы в голове программиста хранилась более абстрактная организованная структура, чем воплощенная в коде (это в принципе верно для любого языка программирования). То есть, программист работает как компилятор из данной абстрактной структуры в SQL. Примером являются структуры в виде дерева, которые SQL прямо не поддерживает, но которые можно выразить с помощью отношения parent-child, и транслировать логику обхода дерева в операторы вроде TCLOSE или CONNECT BY. Это называется - не поддерживает.

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

Давайте рассмотрим сложность используемых инструментов, по разным категориям:
Типы Данных

Изначально, типы данных организованны как фиксированный набор примитивных типов значений. У некоторых типов есть параметр размер, к параметрам типа можно еще отнести nullable флаг. Типов множеств значений фактически нет. Достаточно долго нельзя было добавлять новые типы. Ограничение по размерам задаются достаточно жестко, и обычно есть ограничения по суммарному размеру данных в одной строке. Данный подход четко соответствует уровню 2: сочетания и шаблоны. Фактически, это уровень раннего Фортрана.

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

В последующих версиях стандарта появились составные типы данных, и даже массивы (SQL99)  и мультимножества (SQL 2003), но на это накладываются многочисленные ограничения. Например, тип не может ссылаться на самого себя и нельзя иметь многомерные массивы. Отсутствие поддержки рекурсивных структур данных, ставит крест даже на уровне 3-. Составные типы данных переводят SQL на уровень 2+, но это максимум, что ему можно дать.
Выражения и Предложения Языка

С предложениями изначальной версии все достаточно просто, фактически они делятся на следующие группы:

• Запросы
• Изменение данных
• Изменение структуры

Потом еще добавились хранимые процедуры и функции, но их мы рассмотрим позже.

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

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

Центральным оператором является “SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY ...”. Оператор достаточно монструозный и выполняет достаточно много задач, я не буду их все здесь описывать. Формально, оператор поддерживает иерархическую структуру запросов, но здесь есть много тонкостей. Подзапросы нужно писать в том месте, где они понадобились. В основном, это FROM и WHERE части. В результате, вложенные запросы в основном случаются в середине оператора. Это достаточно неудобно воспринимать. В сложной системе, запросы могут занимать сотни строчек, и у меня был случай, когда запрос на 210 строчек был по делу, и больше не уменьшался (хотя там и было 3 повторяющихся подзапроса на 17 строчек). То есть даже при наличии иерархической структуры, SQL не поддерживает иерархическую декомпозицию.

На данном этапе можно поставить только уровень 2+.
Хранимые Процедуры

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

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

То есть, наличие процедур формально позволяет иерархическую декомпозицию исполнения, но рекурсия не поддерживается. Здесь, по-хорошему, тот же уровень 2+, но можно немного завысить до уровня 3-, на основании формальных критериев.
Расширения Языка

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

Сравните, с языками уровня С или Pascal, где основной механизм расширения - это все-таки библиотеки. Но это сильно похоже на стратегию расширения языков как раз 2-ого уровня (PL/I, COBOL, FORTRAN).
Общий Уровень SQL.

То есть мы получаем общий уровень языка:

Структура: 2+

Динамика: 3-

Это достаточно грустно на общем фоне, с учетом того, что OOFP языки (Scala, Groovy, C# 4, Java 8), достаточно полноценные 4/4. Одна из проблем объектного-реляционного отображения, это разрыв между уровнями. Фактически приходится организовывать трансляцию через уровень, проблемы взаимодействия при этом неизбежны.
Язык Tutorial D

К. Дейт пропагандирует язык Tutorial D, как язык, лишенный недостатков SQL. Этот язык действительно исправляет многие существующие недостатки SQL, и упрощает работу с запросами. Но это не влияет на общий уровень языка. В частности, вместо полноценных рекурсивных запросов, предлагается TCLOSE оператор (семантический аналог CONNECT BY). Убежденность Дейта в своей правоте несколько заражает, но это просто «SQL done right».

Язык Tutorial D поддерживает иерархическую декомпозицию запросов гораздо в большей степени, и я бы даже поставил ему здесь практически полный третий уровень. Но при отсутствии полноценных рекурсивных структур данных, эта возможность практически бесполезна.
NoSQL Системы Управления Данными

У NoSQL систем общее это то, что они не поддерживают SQL или поддерживают его только в весьма ограниченном виде. Соответственно, нельзя их однозначно оценить с точки зрения эволюционной логики.

Часть NoSQL систем родилась в ответ на задачу масштабирования, они и задали моду на этот термин. Это достигалось за счет отката на более простые способы взаимодействия с системой. Первым делом резались те зачатки 3-ого уровня которые были в SQL (соединения, подзапросы, и т.д.). Некоторые даже отрубали саму возможность использовать язык запросов, и давали только возможность использовать API (map-reduce). Однако многие такие системы постепенно восстанавливают возможности SQL.

Другая часть пошла по направлению увеличения сложности модели данных (графовые базы данных, базы документов). И они гораздо более интересны, и я затрону их в следующем разделе.
Post-SQL Языки Управления Данными

Если, SQL не соответствует современному развитию языков программирования, и застрял во временах раннего Фортрана, то каким же должен быть язык управления данных более высокого уровня?

Я этого прямо сейчас сказать не могу, но можно сформулировать некоторые критерии, которым должен соответствовать такой язык, и некоторые языки этим критериям уже соответствуют. Я не буду останавливаться на критериях для языка уровня 2, так как SQL этим критериям более-менее соответствует, и уже является пройденным этапом развития. Критерии для языка 5-ого уровня так же туманны, так как пока нет языков общего назначения этого уровня. А вот промежуточные уровни достаточно понятны.
Уровень 3: Структурное Программирование

Язык программирования третьего уровня должен поддерживать рекурсивные структуры данных и рекурсивную обработку этих данных. В качестве теста на возможности, можно взять эту чудесную книжку, и попытаться реализовать все алгоритмы. Если они реализуются достаточно прямолинейно, и без особых извращений, то этот тест более-менее пройден. Если требуются извращения, то тест не пройден. Из взгляда на код, его рекурсивная структура исполнения должна быть очевидной (внимание, TCLOSE и CONNECT BY - неочевидны).

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

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

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

• Закрытые объединения (tagged union)
• Структуры
• Последовательности
• Множества
• Ссылки или их аналоги (безопасные)

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

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

• С точки зрения реализации, нужно думать о базе данных как о постоянно работающей программе, которая должна переживать остановку виртуальной машины и даже обновление виртуальной машины. DDL - это фактически язык патчей программы, без остановки этой программы. Эта программа может жить десятки лет, меняя не только версии среды исполнения, но возможно даже производителя в процессе миграции, так что должна быть возможность восстановления среды исполнения с нуля до любой точки.
• Нужно четко разделять исполнение на эфемерную часть и постоянную часть. Шаблоны использования на сочетание этих частей могут сильно помочь внедрению. Эфемерную часть можно всегда убить без последствий, при обновлении.
• Лучше иметь нормальные транзакции с самого начала, потом их прикручивать очень сложно. Так же ссылочная целостность должна быть достаточно дешевой.
• SQL в качестве начальной точки - это приглашение к проблемам. Если так уж хочется, можно язык Tutorial D, по крайней мере не нужно будет бороться с косяками SQL. А еще лучше Datalog, который поддерживал рекурсивные запросы.
• Лучше минимизировать систему типов (и лучше даже встроенные типы определить, как предопределенные структуры). При наличии хорошего ядра системы и возможностей расширения, и пользователи сами будут производить расширения увеличивая полезность этой системы.
• Иерархическую модульность и сокрытие данных лучше вводить с самого начала. На практике, потом это с трудом прикручивается (см. печальный опыт языка С).
• При попытке реализовать полноценный объектно-ориентированный язык запросов, рано или поздно будет переход на следующий уровень сложности. Просто в этом случае придется отрубать хвост по кусочку (как было в случае создания С++, который скорее язык уровня 3.8, чем 4). В этом случае, лучше сразу начинать с более сложных и согласованных требований.
• Реляционная алгебра - это, как максимум, ассемблер для системы этого уровня, ограничиться ей не получится. Это не идол. Аналоги запросов SQL должны эффективно выполняться в новой системе и формулироваться с такой же или меньшей сложностью, оно обратное не верно. Некоторые запросы в системе этого уровня могут потребовать нетривиальных преобразований, временных таблиц, и прочей ереси, для того, чтобы выполнить их поверх реляционной базы данных. Это нормально.

Уровень 4: Объектно-Ориентированное и Функциональное Программирование

Системы 4-ого уровня будут еще более сложными. И появятся следующие возможности.

Появятся классы. А именно объекты, которые объединяют и данные и поведение. Класс приблизительно соответствует не записи в таблице, а скорее схеме реляционной базы данных (так же как объект в языке «С++» приблизительно соответствует модулю языка «С» с процедурами и локальными статическими данными). Только классов больше чем схем в традиционной базе данных, и они существенно меньше. Их экземпляры можно создавать и уничтожать на лету и связывать между собой. В теории типов, классам соответствуют existential types. Экземпляры классов должным быть очень дешевыми. Аналоги таблицы могут ссылаться на экземпляры классов, а классы соответственно могут иметь аналоги таблиц в качестве полей. И все это должно быть достаточно дешевым. Классы также являются аналогом открытого объединения (по контрасту с закрытыми объединениями 3-ого уровня).

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

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

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

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

• Необходимо хорошее основание 3-ого уровня. Графовые базы данных выглядят хорошим кандидатом. Первые версии можно сделать просто компилятором в графовые базы данных, но для нормальной производительности, придется разрабатывать другие подходы. В частности нужно учесть печальный опыт реализации ООП языков, и их детские проблемы с производительностью.
• Лучше сразу реализовать сборку мусора. Чем дальше в лес, тем сложнее будет ее прикрутить. Она влияет на все понемножку. И сразу же нужно вводить слабые ссылки и финализацию. Так же, имеет смысл сразу вводить поколения, и задумываться о распределенной сборке мусора.
• Прототип с динамической типизацией может хорошо помочь при проектировании статической системы типов. И лучше не повторять ошибки с примитивными типами у Java (сразу делать объекты). Опциональные значения можно через соответствующий тип данных (null, как показала практика, не очень хорошее решение).
• При введении статической типизации, нужны параметризованные типы. Их придется добавить, но потом будут проблемы с переходом как у C# и Java. Особенно если вы хотите обратной совместимости.
• Такая система будет медленней традиционных баз данных по крайней мере несколько лет (здесь достаточно много нетривиальных задач оптимизации, начиная от сборки мусора до хранения поведения). Возможно более оптимальным будет начать с включенных сценариев, но нужды распределенной версии лучше учитывать с самого начала.
• Для структур управления и запросов может быть полезным сразу использовать лямбда выражения, а потом компилировать и оптимизировать их. Лучше сразу рассчитывать на асинхронную работу, и делать CPS-rewrite в процессе компиляции запросов.
• Сервер как внутренний DSL внутри основного языка скорее всего не взлетит, все равно понадобится слишком много преобразований.
• Имеет смысл, наряду с аналогом таблиц, иметь аналог очередей. В частности, через очереди можно делать поддержку финализации, например, объект который финализируется, может добавлять в очередь некоторое событие. Очереди могут быть основой для сохранения состояния исполнения между перезапусками системы.
• Имеет смысл не поддерживать встроенные процедуры на внешних языках, за исключением быстрых вызовов без модификации состояния (вроде вычисления синуса). Лучше использовать очереди для исходящей коммуникации с внешними системами. Как только появляются более сложные вещи (вроде прямого вызова веб сервисов), то постепенно умирает возможность оптимизаций, основанных на глобальном знании о системе, и язык превращается в язык общего назначения (а таких уже и так много).
• Для простоты анализа, лучше иметь один статический корень графа объектов в системе, и стеки исполнения. Все остальное, через него.
• При попытке построить модель безопасности на списках контроля доступа вас ждет много сюрпризов (так как модель ACL, это модель безопасности 3-ого уровня). В Java и С# адекватную модель не смогли реализовать на этой основе, и ее просто практически везде отключают. Имеет смысл сразу использовать мандатную модель (capability security model). Это модель безопасность 4-ого уровня, и соответствует уровню системы.

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

Современные файловые системы с точки зрения структуры, это достаточно полноценные структуры 3-ого уровня (ну может быть 3-). Так как SQL, это в лучшем случае 2+, то получается разрыв, который делает достаточно сложным реализацию файловой системы поверх базы данных, предоставляя заодно и возможности SQL. Microsoft сделала несколько попыток в этом направлении, и все закончились закономерной неудачей.

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

Если вы не готовы прям сразу начать писать свой сервер баз данных 4-ого поколения, то я все-таки советую начать изучать графовые базы данных, и пытаться применять их в своих проектах. Это будет требовать большего усилия ума в процессе (из-за более высокого уровня абстракции), но вы постепенно сможете решать все более сложные задачи. Графовые базы данных имеют потенциал для гораздо более компактной кодировки решений, и выигрыш будет увеличиваться с их развитием. В случае SQL, неприемлемый уровень сложности достигается гораздо быстрее, и в некотором смысле технологии объектно-реляционного отображения вроде EJB - это попытка получить интерфейс, соответствующий графовой базе данных, поверх реляционной.