Оператор SELECT в языке N-Declarative Language

Введение. Современные Model-driven engineering (MDE) технологии предназначены для улучшения коммуникаций между участниками проекта и для генерации программного кода на основе проектных диаграмм. Однако они повышают стоимость разработки и сопровождения программ из-за необходимости тратить усилия отдельно и на поддержку проектных диаграмм, и на создание программного кода. Источником проблемы здесь является невозможность полной автоматической генерации программного кода, а нотации, предназначенные для кодогенерации, настолько усложняются, что их коммуникативная ценность сводится к нулю, и их разработка не менее сложна, чем построение кода.

В статье [1] предложена N-модель данных, на основе которой разработаны декларативный язык запросов N-Declarative Language (NDL) [2] и визуально-декларативный язык проектирования N-Visulal Language (NVL) [3]. Принципы, заложенные в NVL, позволяют сократить цикл производства программного обеспечения информационных систем (ПО ИС) посредством полной автоматической кодогенерации структур данных и бизнес-логики и повысить коммуникативный эффект за счет более простого и понятного визуально-декларативного языка построения проектных диаграмм.

С другой стороны, стоимость сопровождения ПО ИС может быть существенно снижена путем уменьшения количества обращений пользователей за счет самостоятельного решения ими информационных задач. Этого можно добиться посредством увеличения числа запросов «ad-hoc», выполняемых пользователями без помощи программистов (возможно, с помощью соответствующих интерфейсов, например, интерактивных отчетов). Перспектива увеличения числа запросов «ad-hoc», выполняемых пользователями, видится в замене Structured Query Language (SQL) на более простой SQL-подобный язык без потери выразительной мощности. В качестве такого языка предлагается NDL.

Поскольку основным оператором любого языка, оперирующего структурированными данными, является оператор выборки SELECT, рассмотрению его синтаксиса и семантики в языке NDL и посвящена данная работа.

Синтаксис оператора SELECT в NDL [2]. SELECT в NDL состоит из предложений аналогичных предложениям оператором выборки в SQL: SELECT, FROM, WHERE, GROUP BY, HAVING и ORDER BY. Предложение SELECT определяет множество атрибутов, формирующих результат выборки. Предложение FROM определяет источник выборки. Здесь принципиальное отличие NDL состоит в том, что источником выборки может служить только один класс (или категория), а не набор таблиц, как в SQL. Предложение WHERE определяет предикат, ограничивающий результат выборки. Предложение GROUP BY задает группировку, а предложение HAVING ограничивает результат группировки предикатом, заданным на ее результате. Предложение ORDER BY реализует сорти- ровку результата. При этом сортировка может выполняться только по именованным атрибутам. В общем случае синтаксис оператора SELECT в NDL таков:

<выборка> ::=

SELECT [DISTINCT] [*] [<операционное задание> [AS “<имя>”]

(, <операционное задание> [AS <имя>]..)]

FROM <имя>

[WHERE <условие>]

[GROUP BY <имя> (,<имя>..)]

[HAVING <условие>]

[ORDER BY <имя> [DESC] (,<имя> [DESC]..)]

<операционное задание>::= {(<операционное задание>)| <операнд>}

[<операция><операционное задание>]

<операция> ::= {INTERSECT| MINUS| UNION| +| -| *| /| ’||’}

<операнд> ::= {<атрибут-операнд>| <значение>|

<унарная функция>| <бинарная функция>}

<атрибут-операнд>::={<имя>|{<имя>|PARENT}.<имя>| <имя>:<имя>} <значение>::={<целое число>| <вещественное число>| <литерал>} <бинарная функция>::= <имя> (<операнд>,<операнд>)

<унарная функция>::= {INV| COUNT| MIN| MAX| SUM|

AVG| ALL|<имя>} (<операнд>)

<условие> ::= {(<условие>)| NOT <условие> |<сравнение>}

[{AND|OR} <условие>]

<сравнение> ::= <операционное задание> {<операционное задание>

| BETWEEN <значение> AND <значение>

| IN <операционное задание>| ‘(‘<значение> (,<значение>..)’)’

| STARTING <значение>

| CONTAINING <значение>}

::= {=|<>|>|<|=>|<=}

<имя> ::= <буква>(<буква>|<цифра>)

<цифра>::= {0,1,2,3,4,5,6,7,8,9}

<буква>::= {a..z, A..Z, а..я, А..Я, }

Семантика оператора SELECT в NDL. Семантику оператора SELECT определим на основе базовых конструкций N-модели данных, описанных в [1]. Базовым понятием N-модели является объект, который рассматривается как множество образов. Объектам в реальном мире могут соответствовать конкретные предметы и явления, а также абстрактные понятия предметной области, причем не обязательно вербализованные в естественных языках. Поскольку объекты суть множества, на них определены базовые теоретико-множественные отношения и операции. Теоретикомножественное отношение нестрогого включения при этом трактуется как отношение наследования. Все объекты различимы и индексируются натуральными числами идентифицирующей функцией Id: X → N.

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

Поскольку атрибуты – это функции, они могут задаваться различным способом. Если атрибут задается перечислением пар <объект, значение>, то он называется исходным. Если атрибут задается формулой, то он считается расчетным. Формулы представляют собой инфиксную запись последовательности операций над атрибутами, определенных в [1].

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

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

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

Класс наследует от другого класса, если является его подмножеством. При этом каждый экземпляр класса-потомка является наследником (подмножеством) строго одного экземпляра класса-предка. Наследование может быть простым или кратным. В случае простого наследования (будем рассматривать именно такой случай) существует функция Parent: Id(X) → Id(X), которая по идентификатору экземпляра возвращает идентификатор его непосредственного предка.

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

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

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

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

Теперь перейдем непосредственно к семантике оператора SELECT. Оператор SELECT в применении к некоторому классу оперирует атрибутами потока этого класса.

Пусть C = {c 1 ,c 2 ,…,c n } n ∈ N – конечное множество классов, определенное в заданной схеме. На произвольном классе c i (1 ≤ i ≤ n) определено некоторое множество атрибутов ϒ i с тем же индексом. Множество атрибутов, определенных в классе c i или в его ветви наследования обозначим:

Ω i = {f / f ∈ ϒ j, c j = c i ∨ c j ⊂ c i ∨ c j ⊃ c i }.

Множество экземпляров класса c i обозначим Ext(c i ). Тогда рекурсивно поток s i класса c i – это s i = U Y j таких, что Y j c Q i или 3 g:

j

X → B(Ext(c k )) & Ext(c i ) ⊆ X &  ϒ j ⊆ s k .

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

Помимо значений атрибутов, определенных в ветви наследования класса, или полученных из них операцией композиции, оператор SELECT может возвращать значения атрибутов, полученных в результате применения над атрибутами потока любых других операций, описанных в [1]. Определим множество информативных на произвольном классе c i атрибутов ϑ i как множество атрибутов, соответствующих правилам P1 – P4 :

P1 . f ∈ Ω i ⇒ f ∈ ϑ i

P2 . f = h(g) ⇒ f ∈ ϑ i , где g ∈ ϑ i , Im g ∩ Def h ≠ ∅ , h ∈ s i .

P3 . f = • g ⇒ f ∈ ϑ i , где • – унарная операция или агрегация над атрибутом в смысле [1], g ∈ ϑ i .

P4 . f = g ο h ⇒ f ∈ ϑ i , где ο – бинарная или теоретико-множественная операция над атрибутами в смысле [1], g, h ∈ ϑ i .

Пусть c i – произвольный класс в базе данных, Ext(c i ) = {x 1 ,x 2 ,…,x q }, q ∈ N – множество его экземпляров в определенный момент времени, и ϑ i = {f 1 ,f 2 ,…,f m }, m ∈ N – множество информативных на нем атрибутов. Тогда можно построить отношение ℜ i , в котором каждый экземпляр x класса c i порождает ровно один кортеж (Id(x), Parent(x), f 1 (x), f 2 (x),…, f m (x)) и никаких других кортежей не содержится:

Id	Parent	f 1	f 2     …	fm m
Id(x 1 )	Parent (x 1 )	f 1 (x 1 )	f 2 (x 1 )    …	f m (x 1 )
Id(x 2 )	Parent (x 2 )	f 1 (x 2 )	f 2 (x 2 )    …	f m (x 2 )
Id … (x q )	Parent (x q )	f 1 … (x q )	f 2 … (x q )   …	f m (x q )

Можно было бы сказать, что результат оператора SELECT на произвольном классе ci – это результат применения операций реляционной алгебры и/или операций группировки и сортировки над отношением ℜi. Однако с отношением ℜi связана проблема практической интерпретации. Возникает она из-за того, что информативный на классе атрибут в общем случае может принимать на его экземплярах значения, по сути являющиеся множествами значений simple-типов данных. Если информативный атрибут на каждом экземпляре класса принимает строго одно значение simple-типа, то, согласно [1], он называется ординарным, в противном случае – множественным. Причем, если атрибут определен на классе как ординарный, то он является множественным на его классах-предках. Проблема собственно заключается в интерпретации множественных атрибу- тов, если они входят в ℜi.

Как вариант решения проблемы можно предложить ограничить множество атрибутов, из которых строится ℜ i , только ординарными на классе c i . Обозначим ϑ′ i ={f/f ∈ ϑ i , ∀ x ∈ Ext(c i ) |f(x)|=1}. Допустим, что для произвольного класса c i существует ϑ′ i = {f 1 ,f 2 ,…,f k }, k ∈ N. Тогда в отношении ℜ i каждый экземпляр x класса c i порождает ровно один кортеж (Id(x), Parent(x), f 1 (x), f 2 (x),…, f k (x)) и никаких других кортежей не содержится:

Id	Parent	f 1	f 2	f k
Id(x 1 )	Parent (x 1 )	f 1 (x 1 )	f 2 (x 1 )	f k (x 1 )
Id(x 2 )	Parent (x 2 )	f 1 (x 2 )	f 2 (x 2 )	f k (x 2 )
Id … (x q )	Parent (x q )	f 1 … (x q )	f 2 … (x q )	f k (x q )

Недостаток данного решения – ограничение выразительной мощности оператора SELECT.

На практике множественные атрибуты могут интерпретироваться как коллекции. В этом случае отношение ℜ i можно переопределить посредством функции кодирования Code: B(P) → N, определенной в булеане множества P значений simple-типов данных. Тогда в отношении ℜ i каждый экземпляр x класса c i порождает ровно один кортеж (Id(x), Parent(x), Code(f 1 (x)), Code(f 2 (x)),…, Code(f m (x))) и никаких других кортежей не содержится:

Id

Id(x 1 )

Id(x 2 )

Parent

Parent (x 1 )

Parent (x 2 )

f 1

f 2

fm m

Id(x q )

Parent (x q )

Code(f 1 (x 1 ) )

Code(f 1 (x 2 ) )

Code(f 1 (x q ) )

Code(f 2 (x 1 ) )

Code(f 2 (x 2 ) )

Code(f 2 (x q ) )

Code(f m (x 1 ) )

Code(f m (x 2 ) )

Code(f m (x q ) )

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

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

Последний вариант решения проблемы множественных атрибутов заключается в снятии неявного требования функциональной зависимости атрибутов f 1 ,f₂,...,f_m от Id в отношении ^ i . Отношение ^ ограничим таким образом, что каждый экземпляр X j класса c i продуцирует в отношении ^ множество кортежей равное декартову произведению значений функций Id, Parent, f 1 , f₂,_, f_m на этом экземпляре. Пусть c i - произвольный класс в базе данных, Ext(c i ) = {x 1 ,x₂,^,x q }, q е N -множество его экземпляров в определенный момент времени, ty = {f 1 ,f₂,...,f_m}, m е N - множество информативных на нем атрибутов. Тогда можно построить отношение:

j=q

R i = U ^Id ( x j ) ^xParent ( x j ) ^xfi ( x j ) ^xf2 ( x j ) ^x ^ ^xfm ( x j ) .                     ⁽¹⁾

j=1

Продемонстрируем построение ^i на примерах. Предварительно заметим, что число ин- формативных на классе атрибутов бесконечно, поскольку бесконечно число атрибутов, порож- даемых операциями. Поэтому в рассматриваемых примерах (и только в них) ограничим множество 9| атрибутами потока класса, который в любой момент существования базы данных конечен. Допустим, имеется класс c1, содержащий экземпляры x1 и x2, и на нем определены атрибуты f1 и f2.

При этом Id(x 1 ) = 91, Id(x 2 ) = 92, f 1 (x 1 ) = {1,0}, f 2 (x 1 ) = 10, f 1 (x 2 ) = 1, f 2 (x 2 ) = 20. Тогда отношение

^ 1 , построенное на классе с 1 , будет выглядеть так:

Id

f 1 f 2

1   10

0   10

1 20.

Теперь добавим в предыдущий пример класс c 2 , который наследует от класса с 1 . Допустим, что с 2 содержит экземпляры x 3 , x 4 и x 5 и Id(x 3 )=93, Id(x 4 )=94, Id(x 5 )=95. При этом x 3 и x 4 наследуют от экземпляра x 1 класса с 1 , а x 5 наследует от x 2 . На с 2 определен атрибут f 3 : f 3 (x 3 )=300, f 3 (x 4 )=400, f 3 (x 5 )=500. Тогда отношение ^ 1 , построенное на классе с 1 , будет таким:

Id	f 1	f 2	f 3
91	1	10	300
91	1	10	400
91	0	10	300
91	0	10	400
92	1	20	500.

Отношение ^2, построенное на классе с2, будет выглядеть следующим образом: Id Parent f1 f2 f3 93 91 1 10 300 93 91 0 10 300 94 91 1 10 400 94 91 0 10 400 95 92 1 20 500. В последнем примере добавим к классам c1 и c2 класс c3 с экземплярами x6 и x7. Допустим, что Id(x6)=10, а Id(x7)=20. На с3 определен атрибут f4: f4(x6)=1000, f4(x7)=2000. Кроме того, атрибут f2, определенный на c1, будем трактовать как ссылку на класс c3. Тогда на c3 определен расчетный атрибут f5=Inv(c1,f2), что, согласно [1], означает обратную ссылку на класс c2, полученную в результате операции инволюции. Тогда отношение ^1, построенное на классе с1, таково:

Id	f 1	f 2	f 3	f 2 .f 4
91	1	10	300	1000
91	1	10	400	1000
91	0	10	300	1000
91	0	10	400	1000
92	1	20	500	2000.

Отношение ℜ 2 , построенное на классе с 2 :

Id	Parent	f 1	f 2	f 3	f 2 .f 4
93	91	1	10	300	1000
93	91	0	10	300	1000
94	91	1	10	400	1000
94	91	0	10	400	1000
95	92	1	20	500	2000.

Отношение ℜ 3 , построенное на классе с 3 :			f 5 .f 1	f 5 .f 3
Id	f 4	f 5
10	1000	91	1	300
10	1000	91	0	300
10	1000	91	1	400
10	1000	91	0	400
20	2000	92	1	500.

Главным недостатком последнего из предложенных здесь вариантов решения проблемы множественных атрибутов является «скрытая угроза» экспоненциального возрастания мощности результирующего отношения при увеличении числа таковых в запросе. Угроза является скрытой, поскольку декартово произведение при формировании результатов запроса выполняется неявно в зависимости от свойств атрибутов. Запрос, выдающий практически неприемлемый по мощности результат, в языке NDL выглядит довольно «невинно», в отличие от SQL, где аналогичный запрос будет иметь более громоздкую конструкцию с явным указанием операции соединения, продуцирующей декартово произведение.

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

Таким образом, здесь и далее мы будем использовать для ℜ i последнее определение. Это подразумевает, что в любой нашей реализации NDL оператор SELECT будет иметь следующую семантику:

• S1 .    Результат применения оператора SELECT к произвольному классу c i – это всегда некоторое отношение, полученное путем последовательного применения операций реляционной алгебры и/или операций группировки и сортировки над отношением ℜ i, которое определяется выражением (1).

Семантика предложений оператора SELECT в NDL. В соответствии с правилом S1 результат оператора SELECT на классе можно представить как результат применения операций реляционной алгебры и/или операций группировки и упорядочивания к отношению, содержащему значения информативных на этом классе атрибутов. Здесь и далее мы будем использовать операции реляционной алгебры Кодда.

Еще в «Третьем манифесте» [4] были четко сформулированы признаки нереляционности SQL. И хотя авторы манифеста посчитали это недостатком SQL, практика показала обратную картину: для выражения многих важных классов информационных запросов одной реляционной алгебры недостаточно. Хотя следующее высказывание может показаться противоречащим преды- дущему, мы поддерживаем мнение Дейта и Дарвена, что нереляционность SQL – это «зло». Но, хотим мы этого или нет, от этого «зла» никуда не деться. Во-первых, мы не можем уйти от упорядоченности результата запроса – порядок как по столбцам, так и по строкам часто критически важен не только для представления, но и для программной обработки результата запроса. Во-вторых, устранение кортежей-дубликатов в некоторых случаях приводит к невыразимости информационной потребности в запросе. В-третьих, многие аналитические запросы оперируют сгруппированными таблицами, которые нельзя получить посредством операций реляционной алгебры над исходным отношением. Поэтому мы сознательно вводим операции группировки и упорядочивания, семантика которых определена в стандарте SQL ISO/IEC-9075-01:2008 [5].

Кроме того, условимся обозначать name(z) – имя объекта z (атрибута или класса) в базе данных в произвольный момент времени.

• S2 .    Предложение FROM оператора SELECT определяет класс, на котором выполняется этот оператор.

• S3 .    Предложение SELECT оператора SELECT на классе c i реализует операцию проекции реляционной алгебры на отношении ℜ i (при этом явно задается порядок столбцов в результате): SELECT name(A), name(B),.., name(C) FROM name(c i ) →

PROJECT      ℜi{A,B,…,C}, где A,B,..,C – атрибуты, информативные на ci.