Проектируем мультипарадигменный язык программирования. Часть 6 — Заимствования из SQL

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

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

В области работы с данными неоспоримым лидером является язык SQL. Некоторые его возможности, оказавшиеся очень удобными на практике, такие как агрегация, позже перекочевали в логическое программирование. Поэтому будет полезным позаимствовать из SQL как можно больше возможностей и для компоненты моделирования. В этой статье я хочу показать, как в определения понятий можно встроить вложенные запросы, внешние соединения (outer join) и агрегацию. Также расскажу о еще одном типе понятий, которое описывается с помощью функции, генерирующей объекты (сущности) в алгоритмическом стиле не прибегая к логическому поиску. И покажу, как с его помощью можно использовать массивы объектов в качестве родительских понятий по аналогии с SQL операцией UNNEST, преобразовывающей коллекции в табличный формат и позволяющей соединить их с другими таблицами в секции FROM.

Анонимные определения понятий

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

Иногда нужно немного модифицировать понятие, выбрать отдельные его атрибуты, отфильтровать значения. Если эта модификация нужна только в одном месте, то тогда создавать отдельное понятие с уникальным именем не имеет смысла. Такая ситуация часто встречается, когда понятия являются аргументами функций, например, таких как exists, find или findOne, выполняющих проверку выводимости понятия, нахождения всех или только первого объекта (сущности) понятия. Здесь можно провести аналогию с анонимными функциями в функциональных языках программирования, которые часто применяются в качестве аргументов таких функций как map, find, filter и др.

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

Попробуем пояснить выше написанное с помощью нескольких примеров. С помощью функции exists можно проверить выводимость или не выводимость вложенного понятия:

concept freeExecutor is executor e where not exists (
    task t where t.executor = e.id and t.status in ('assigned', 'in process')
)

В данном примере анонимное понятие:

(task t where t.executor = e.id and t.status in ('assigned', 'in process'))

на самом деле представляет собой понятие, наследующее все атрибуты понятия task:

(concept _unanimous_task_1 as task t where t.executor = e.id and t.status in ('assigned', 'in process'))

Функция find позволяет вернуть в виде списка все значения понятия, которые затем могут быть связаны с атрибутом:

concept customerOrdersThisYear is customer c with orders where c.orders = find(
    (id = o.id, status = o.status, createdDate = o.createdDate, total = o.total) 
    from order o where o.customerId = c.id and o.createdDate > '2021-01-01'
)

В данном примере мы расширяем понятие customer списком заказов, которые представляют собой объекты, содержащие выбранные атрибуты понятия order. Мы указали список атрибутов анонимного понятия, а его имя пропущено.

Условия в секции where анонимного понятия могут включать атрибуты других родительских или дочернего понятий, в данном случае это c.id. Особенностью анонимных понятий является то, что все подобные внешние переменные и атрибуты должны быть обязательно связаны со значениями на момент запуска поиска решений. Таким образом объекты анонимного понятия могут быть найдены только после нахождения объектов понятия customer.

Внешние соединения

Анонимные определения понятий можно использовать и в секции from, где они будут представлять родительские понятия. Более того, в определение анонимного понятия можно перенести часть условий, связывающих его с другими понятиями, что будет иметь особый эффект. Эти условия будут проверены на этапе поиска решения анонимного понятия и не будут влиять на процесс логического вывода дочернего понятия. Здесь можно провести аналогию между условиями в секции where анонимного понятия и условиями в секции JOIN ON языка SQL.

Таким образом, анонимные понятий могут быть использованы для реализации аналога внешних соединений (left outer join) языка SQL. Для этого понадобится три вещи.

1. Во-первых, заменить нужное родительское понятие анонимным понятием на его основе и перенести в него все связи с остальными родительскими понятиями.
2. Во-вторых, указать, что неудача вывода этого понятия не должна приводить к автоматической неудаче вывода всего дочернего понятия. Для этого нужно пометить это родительское понятие с помощью ключевого слова optional.
3. А в-третьих, в секции where дочернего понятия можно проверить, существуют ли решения данного анонимного понятия.

Разберем небольшой пример:

concept taskAssignedTo (task = t, assignee = u, assigneeName) 
from task t, optional (user where id = t.assignedTo) u 
where assigneeName = if(defined(u), u.firstName + ' ' + u.lastName, 'Unassigned') 

Атрибуты понятия taskAssignedTo включают в себя объекты задачи, ее исполнителя и отдельно имя исполнителя. Родительскими понятиями являются task и user, причем значение последнего может быть пустым, если задача еще не имеет исполнителя. Оно обвернуто в определение анонимного понятия, перед которым стоит ключевое слово optional. Процедура логического вывода сначала найдет объекты понятия task, затем на основе user создаст анонимное понятие, связав его с конкретным значением атрибута assignedTo понятия task. Ключевое слово optional указывает процедуре вывода, что в случае неудачи вывода этого понятия, его объект будет связан со специальным значением UNDEFINED. А проверка результата его вывода на уровне дочернего понятия позволяет атрибуту assigneeName задать значение по умолчанию. Если ключевое слово optional не было бы указано, то неудача вывода анонимного понятия привела бы к неудаче текущей ветви поиска дочернего понятия. И такой вариант был бы аналогичен внутреннему объединению (inner join) языка SQL.

Поскольку условия в секции where анонимного понятия включают атрибут assignedTo другого родительского понятия task, то поиск объектов понятия user возможен только после связывания объектов task со значениями. Их нельзя поменять местами:

from optional (user where id = t.assignedTo) u, task t 

Поскольку на начальном этапе значение t.assignedTo будет неизвестным, то создать определение анонимного понятия не получится.

Если в SQL порядок таблиц в секции from не имеет значения, то в Prolog порядок предикатов в правиле однозначно определяет последовательность обхода дерева решений. То же можно сказать и о компоненте моделирования, правило вывода которой основано на SLD резолюции, используемой в Prolog. В ней результат вывода объектов левого понятия определяет ограничения для вывода объектов правого. Из-за этого, к сожалению, не получится реализовать операции right outer join и full outer join таким же естественным образом. Поскольку мощность множества результатов правого родительского понятия может быть больше, чем левого, то в них потребуется вывод в противоположном направлении — от правого понятия к левому. К сожалению, особенности выбранной процедуры логического вывода накладывают свои ограничения на функциональность языка. Но операцию full outer join можно сэмулировать соединив внутреннее, левое и правое объединения:

concept outerJoinRelation( 
concept1Name, 
concept2Name, 
concept1Key,
concept2Key,
concept1 = c1,
concept2 = c2
) from <concept1Name> c1, <concept2Name> c2
where c1.<concept1Key> = c2.<concept2Key>;

concept outerJoinRelation(
concept1Name, 
concept2Name, 
concept1Key,
concept2Key,
concept1 = c1,
concept2 = null
) from <concept1Name> c1
where not exists( <concept2Name> c2 where c1.<concept1Key> = c2.<concept2Key>);

concept outerJoinRelation(
concept1Name, 
concept2Name, 
concept1Key,
concept2Key,
concept1 = null,
concept2 = c2
) from <concept2Name> c2
where not exists( <concept1Name> c1 where c1.<concept1Key> = c2.<concept2Key>);

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

Агрегирование

Агрегирование является неотъемлемой частью как реляционной алгебры, так и логического программирования. В языке SQL секция GROUP BY позволяет сгруппировать строки, имеющие одинаковые ключевые значения, в итоговые строки. Она позволяет удалить повторяющиеся значения и обычно используется с агрегатными функциями, такими как sum, count, min, max, avg. Для каждой группы строк агрегатные функции возвращают ординарное значение, рассчитанное на основе всех строк этой группы. В логическом программировании агрегирование имеет более сложную семантику. Это связано с тем, что в некоторых случаях рекурсивного определения правил SLD резолюция попадает в бесконечный цикл и не способна завершиться. Как и в случае отрицания как отказа проблему рекурсии в операции агрегации решают с помощью семантики стойких моделей или хорошо обоснованной семантики. Об этих подходах я попытался кратко рассказать в предыдущей статье. Но поскольку семантика компоненты моделирования должна быть как можно проще, то стандартная SLD резолюция более предпочтительна. А проблему избегания бесконечной рекурсии лучше решить путем переформирования связей между понятиями.

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

concept <имя понятия> <псевдоним понятия> (
    <имя атрибута> = <выражение>,
    ... 
)
group by <имя атрибута>, ... 
from 
    <имя родительского понятия> <псевдоним родительского понятия> (
        <имя атрибута> = <выражение> ,
        ...
    ),
    ...
where <выражение отношений>

Секция group by, так же, как и в SQL, содержит список атрибутов, по которым выполняется группировка. Выражение отношений также может включать функции агрегации. Выражения, содержащие такие функции будут считаться неопределенными, пока не будут найдены значения всех родительских понятий и выполнена группировка. После этого их значения могут быть вычислены для каждой группы, связаны с атрибутами и/или использованы для фильтрации групп. При таком отложенном подходе к вычислениям и проверке условий нет необходимости в секции HAVING, отделяющей условия фильтрации до и после группировки. Среда исполнения сделает это автоматически.

Основными функциями агрегации являются count, sum, avg, min, max. Назначение функций можно понять из их названия. Поскольку компонента моделирования умеет естественным образом работать c составными типами данных, то также можно добавить функцию, возвращающую сгруппированные значения в виде списка. Назовем ее group. Ее входным аргументом является выражение. Функция возвращает список результатов вычисления этого выражения для каждого элемента группы. Комбинируя ее с другими функциями можно реализовать любую произвольную функцию агрегации. Функция group будет удобнее, чем такие SQL функции как group_concat или json_arrayag, которые часто используются в качестве промежуточного шага для получения массива значений поля.

Пример группировки:

concept totalOrders (
    customer = c,
    orders = group(o),
    ordersTotal = sum(o.total)
) group by customer
from customer c, order o 
where c.id = o.customerId and ordersTotal > 100

Атрибут orders будет содержать список всех заказов пользователя, ordersTotal – общую сумму всех заказов. Условие ordersTotal > 100 будет проверено уже после выполнения группировки и вычисления функции sum.

Понятие, определенное с помощью функции

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

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

concept <имя понятия> (
<имя атрибута>, ... 
)
by <функция генерации объектов>

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

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

Результатом вычисления функции должен быть список объектов понятия. Но, поскольку процедура логического вывода, основанная на поиске с возвратом, будет потреблять эти значения по одному, то можно выходным аргументом функции сделать не сам список, а итератор к нему. Это сделало бы определение понятия более гибким, например, позволило бы при необходимости реализовать ленивые вычисления или бесконечную последовательность объектов. Можно использовать итератор любой стандартной коллекции либо создать свою произвольную реализацию. Элементом коллекции должен быть ассоциативный массив со значениями атрибутов понятия. Сущности понятия будут созданы на их основе автоматически.
Вариант с использование итератора в качестве типа возвращаемого значения имеет свои недостатки. Он более громоздкий и менее удобный по сравнению с простым возвратом списка результатов. Поиск оптимального варианта, сочетающего универсальность, простоту и удобство работы — это задача на будущее.

В качестве примера рассмотрим понятие, описывающее временные интервалы. Предположим, нам нужно разбить рабочий день на 15-и минутные интервалы. Мы можем сделать это с помощью довольно простой функции:

concept timeSlot15min (id, hour, minute) by function(query, mode) {
    var timeSlots = [];
    var curId = 1;
    for(var curHour = 8; curHour < 19; curHour += 1) {
        for(var curMinute = 0; curMinute < 60; curMinute += 15) {
            timeSlots.push({
                id: curId,
                hour: curHour,
                minute: curMinute;
            });
            curId++;
        }
    }
    return timeSlots.iterator();
}

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

concept freeTimeSlot is timeSlot15min s where not exists (bookedSlot b where b.id = s.id)

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

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

В качестве примера рассмотрим понятие, определяющее значения некой экспоненциальной шкалы.

concept expScale (value, position, required limit) by function(query, mode) {
return {
    _curPos = 0,
    _curValue = 1,
    next: function() {
        if(!this.hasNext()) {
            return null;
        }
        var curItem = {value: this._curValue, position: this._curPosition, limit:  query.limit};
        this._curPos += 1;
        this._curValue = this._curValue * Math.E;
        return curItem;
    },
    hasNext: function() {
        return query.limit == 0 || this._curPos < query.limit; 
    }
}}

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

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

Развертывание вложенных коллекций (Flattening nested collections)

Некоторые диалекты SQL, умеющие работать с данными в объектной форме, поддерживают такую операцию как UNNEST, которая преобразует содержимое коллекции в табличный формат (набор строк) и добавляет получившуюся таблицу в секцию FROM. Обычно она используется, чтобы объекты со вложенными структурами сделать плоскими, другими словами, развернуть или сгладить (flatten) их. Примерами таких языков являются BigQuery и SQL++.

Предположим, мы храним информацию о пользователях в виде JSON объекта:

[ {
"id":1,
"alias":"Margarita",
"name":"MargaritaStoddard",
"nickname":"Mags",
"userSince":"2012-08-20T10:10:00",
"friendIds":[2,3,6,10],
"employment":[{
    "organizationName":"Codetechno",
    "start-date":"2006-08-06"
},
{
    "organizationName":"geomedia",
    "start-date":"2010-06-17",
    "end-date":"2010-01-26"
}],
"gender":"F"
},
{
"id":2,
"alias":"Isbel",
"name":"IsbelDull",
"nickname":"Izzy",
"userSince":"2011-01-22T10:10:00",
"friendIds":[1,4],
"employment":[{
    "organizationName":"Hexviafind",
    "startDate":"2010-04-27"
}]
}, 
…]

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

SELECT u.id AS userId, u.name AS userName, e.organizationName AS orgName
FROM Users u UNNEST u.employment e
WHERE u.id = 1;

Результатом будет:

[ {
"userId": 1,
"userName": "MargaritaStoddard",
"orgName": "Codetechno"
}, {
"userId": 1,
"userName": "MargaritaStoddard",
"orgName": "geomedia"
} ]

Более подробно эта операция рассмотрена здесь.

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

Поскольку полное определение понятия через функцию слишком громоздко для использования в качестве анонимного понятия:

concept conceptName(attribute1, attribute2, ...) by function(query, mode) {...}

нужно найти способ его сократить. Во-первых, можно избавиться от заголовка определения функции с параметрами query и mode. На позиции родительского понятия аргумент mode всегда будет равен «найти все значения понятия». Аргумент query всегда будет пуст, так как зависимости от атрибутов других понятий можно встроить в тело функции. Ключевое слово concept тоже можно выкинуть. Таким образом получаем:

conceptName(attribute1, attribute2, ...) {…}

Если имя понятия не важно, то его можно опустить, и оно будет сгенерировано автоматически:

(attribute1, attribute2, ...) {…}

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

{…}

Итак, пример с пользователями и их местами работы в виде понятия будет выглядеть следующим образом:

concept userEmployments (
    userId = u.id,
    userName = u.name,
    orgName = e.orgName
) from users u, {u.employment.map((item) => {orgName: item.organizationName}).iterator()} e

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

concept userEmployments (
    userId = u.id,
    userName = u.name,
    orgName = e. organizationName
) from users u, {u.employment.iterator()} e

Выводы

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

Анонимное понятие — это сокращенная форма определения понятия, предназначенная однократного для использования в качестве аргументов функций (find, findOne и exists) или в качестве вложенного определения понятия в секции where. Его можно рассматривать как аналог анонимных определений функций в языках функционального программирования.

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

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

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

Полный текст в научном стиле на английском языке доступен по ссылке: papers.ssrn.com/sol3/papers.cfm?abstract_id=3555711

Ссылки на предыдущие публикации:

Проектируем мультипарадигменный язык программирования. Часть 1 — Для чего он нужен?
Проектируем мультипарадигменный язык программирования. Часть 2 — Сравнение построения моделей в PL/SQL, LINQ и GraphQL
Проектируем мультипарадигменный язык программирования. Часть 3 — Обзор языков представления знаний
Проектируем мультипарадигменный язык программирования. Часть 4 — Основные конструкции языка моделирования
Проектируем мультипарадигменный язык программирования. Часть 5 — Особенности логического программирования