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

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

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

• -    реализация алгоритма трансляции ЕЯ-запросов для каждого языка запросов к БД трудоемка;

• -    различные реализации алгоритма могут быть несовместимы между собой;

• -    между реализациями алгоритма трансляции могут возникнуть семантические различия вследствие ориентации на конкретный язык запросов;

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

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

Как уже говорилось, построение естественно-языковых интерфейсов (ЕЯ-интерфейсов) к структурированным источникам данных сопряжено с принятием большого количества решений. В первую очередь необходимо определиться с подходом к построению ЕЯ-интерфейса. Выделяются три [1] подхода к построению ЕЯ-интерфейсов:

• -    подход, основанный на синтаксическом анализе;

• -    подход, основанный на семантическом анализе;

• -    подход, основанный на шаблонах.

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

Таким образом, при использовании любого подхода или их комбинации важным является решение о выборе промежуточного представления ЕЯ-запроса. Промежуточное представление должно обеспечивать выполнение таких требований, как семантическая эквивалентность ЕЯ-запроса и целевого запроса, устранение неоднозначностей ЕЯ-запроса, универсальность внутреннего представления, выразительная мощность и др. Подходы к выполнению данных требовании и к их практической реализации [4] известны и хорошо описаны. Однако универсальности как внутреннего представления ЕЯ-запросов, так и самих алгоритмов трансляции ЕЯ-запроса в целевой запрос уделяется второстепенная роль. Необходимо пояснить, что в данном случае под универсальностью следует понимать не только высокий уровень абстракции создаваемой модели или метода, но и потенциал его широкого практического применения.

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

Требования к промежуточному (абстрактному) языку запросов

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

• -    лексическую и семантическую выразительность (1);

• -    легкость преобразования в выражения, описываемые грамматиками распространенных языков запросов (2).

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

Для проведения исследования сформулируем более частные требования к языку про -межуточного представления:

• -    высокий уровень абстракции (1 а);

• -    легкость описания и обработки графов (1 б);

• -    легкость представления и обработки моделей баз знаний (1 в);

• -    пригодность к работе с распространенными моделями структурированных источников данных (1 г);

• -    хорошо проработанная и простая грамматика языка (2 а);

• -    наличие трансляторов или методов трансляции из данного языка в другие (2 б).

Частные требования (1 а), (1 б), (2 а) и (2 б) достаточно тривиальны и только детализируют общие требования (1) и (2). Однако на требованиях (1 в) и (1 г) следует остановиться более подробно.

Требование «Легкость представления и обработки моделей баз знаний» обусловлено тем, что преобразование семантико-синтаксического графа ЕЯ-запроса в промежуточное представление невозможно без использования лингвистической базы знаний (ЛБЗ) ЕЯ-транслятора. Поэтому если язык промежуточного представления ЕЯ-запроса будет базироваться на той же лингвистической базе знаний, что и сам ЕЯ-запрос, то это позволит уточнить семантику запроса, заранее спрогнозировать возможные варианты диалога ЕЯ-системы с пользователем, а также расширить саму лингвистическую базу знаний.

Требование «Пригодность к работе с распространенными моделями структурированных источников данных» связано с частными требованиями (1 а) и (2 б), поскольку под пригодностью следует понимать легкость преобразования промежуточного представления ЕЯ-запроса в запросы на целевых языках. При этом достаточно важным свойством такого представления является возможность построения промежуточного запроса так, чтобы было сведено к минимуму количество ситуаций, когда выражение на промежуточном языке не может быть транслировано в запрос на целевом языке.

Рис. Трансляция ЕЯ-запроса с использованием слоя промежуточного представления

Классификация моделей данных и выбор языков запросов к структурированным источникам данных

Существует несколько широко применяемых моделей данных и их сочетаний, поэтому категоризация языков запросов будет произведена исходя из типологий моделей данных, ко- торые можно разбить на четыре обобщенных типа: «Отношение», «Предикат», «Иерархия» и «Класс» (табл. 1).

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

Таблица 1

Обобщенные типы моделей данных

Обобщенный тип	Модели данных	Языки запросов к СИД
«Отношение»	реляционная, объектно-реляционная модели данных	SQL, Tutorial D, Dataphor, Rel, Opus, FoxPro, Clipper
«Предикат»	логическая модель представления (знаний), реляционная модель, интенсиональные базы данных	Prolog, Datalog
«Иерархия»	иерархическая и сетевая модели данных, данные в виде XML и JSON, графовые модели	XQuery, XPath, LINQ, API для процедурных и объектно-ориентированных языков
«Класс»	объектная модель данных, документно-ориентированные базы данных	LINQ, JPQL, HQL, COS, API для процедурных и объектно-ориентированных языков

На основании таблицы 1 можно сделать ряд выводов, на основании которых в дальнейшем можно перейти непосредственно к сравнению языков запросов:

• 1)    основным языком запросов для моделей типа « Отношение » является язык SQL , который в настоящее время наиболее развит и широко применяется на практике, а также является шаблоном для создания иных языков запросов. Также выделяется язык Tutorial / Industrial D , имеющий академический характер, однако компактнее и ближе к основам реляционной модели данных;

• 2)    основным языком запросов для моделей типа « Предикат » является язык Prolog . Данный язык достаточно сложен в изучении, но близок к нотации математической логики. В связи с этим целесообразнее рассмотреть при сравнении диалект языка Prolog – язык Datalog , который специализирован для работы со структурированными данными;

• 3)    языки запросов, относящиеся к типу « Иерархия », крайне разнородны, и их обзор далеко выходит за рамки настоящей статьи. В дальнейшем сосредоточимся на рассмотрении языка XPath (язык XQuery имеет сходные возможности). Такой выбор обоснован распространенностью формата данных XML , с которым и работает язык XPath . Отдельно необходимо оговориться, что в настоящее время широко распространен и формат JSON , однако такие языки запросов, как JaQL , JsonPath , Json Query на сегодняшний день являются специфичными и слабо распространенными;

• 4)    языки запросов, относящиеся к типу « Класс », являются либо некоторым подмножеством (расширением или даже библиотекой) объектно-ориентированных или процедурных языков, либо являются урезанными аналогами SQL с объектной спецификой ( JPQL , HQL ). Очевидно, что первая группа языков не подходит для анализа. Из второй группы достаточно интересен язык JPQL (язык HQL имеет сходные возможности). Отдельно необходимо выделить технологию LINQ , которая хотя и реализована как подмножество языка C #, однако предоставляет развитые средства единообразного построения запросов к различным моделям данных.

Таким образом, можно определить следующую группу языков, которые, во-первых, являются типичными представителями для каждого обобщенного типа, во-вторых, используются в современной практике и, в-третьих, явно не противоречат указанным выше требованиям: SQL , Tutorial D , Datalog , XPath , JPQL и LINQ .

Сравнительный анализ языков запросов

В таблице 2 приведен сравнительный анализ языков на соответствие выделенным ранее критериям.

На основании данных таблицы 2 можно провести обобщение сравнения по каждому критерию.

Результаты сравнения по критерию (1) свидетельствуют о том, что XPath , JPQL , LINQ проигрывают по выразительности в силу того, что применяются ограниченно и в сочетании с более мощными средствами императивного программирования.

Сравнение по частному критерию (1 а) подтверждает результаты сравнения по критерию (1), однако необходимо выделить язык Datalog как имеющий наибольший уровень абстракции, что, с одной стороны, увеличивает его универсальность, а с другой, - усложняет его применение для реальных задач. Сравнение по частному критерию (1 б) также показывает преимущества языка Datalog , в котором обработка графов осуществляется на уровне самого языка, а не на уровне реализации алгоритмов. Сравнение по частному критерию (1 в) всех языков дает практически одинаковые результаты, однако XPath и JPQL имеют более слабые показатели. Лидерами сравнения по частному критерию (1 г) являются SQL , Datalog и LINQ .

Таблица 2

Сравнительный анализ языков запросов

Критерии	SQL	Tutorial D	Datalog	XPath	JPQL	LINQ
(1)	Развитые средства описания и манипулирования данными	Средства описания и манипулирования реляционными данными	Единообразные средства описания и манипулирования данными	Средства получения данных	Средства получения данных	Средства частичного описания и манипулирования данными
(1 а)	Высокий уровень абстракции	Высокий уровень абстракции	Высокий уровень абстракции	Средний уровень абстракции	Средний уровень абстракции	Средний уровень абстракции
(1 б)	Обработка графов нетривиальна	Нет сведений	Хорошо подходит для описания и обработки графов	Обработка графов возможна	Обработка графов нетривиальна	Обработка графов возможна
(1 в)	Продукционные, фреймовые	Продукционные, фреймовые	Продукционные, логические и сетевые	Фреймовые	Фреймовые	Продукционные, фреймовые
(1 г)	Реляционная, объектнореляционная, частично объектная	Реляционная	Реляционная, логическая, частично сетевая и иерархическая	Иерархическая	Объектная	Объектная, иерархическая, частично реляционная
(2)	Легко	Возможно	Практически любые	Возможно	Возможно	Легко
(2 а)	Хорошо проработана стандартизирована	Хорошо проработана	Подмножество Prolog	Ограничена	Ограничена	Подмножество C#
(2 б)	Много	Существуют	Существуют	Существуют	Существуют	Существуют

Результаты сравнения по критерию (2) и частным критериям (2 а) и (2 б) свидетельствуют о том, что SQL, Tutorial D и Datalog имеют развитые грамматики, а также характеризуются наличием проработанных методов преобразования выражений в выражения на других языках запросов. Однако необходимо заметить, что даже стандарт SQL 92 описывает достаточно сложную грамматику, более того, в каждой реализации SQL имеются существенные расхождения со стандартами языка (хотя данный факт проявляет себя только при использовании продвинутых возможностей языка). Tutorial D можно характеризовать более простой грамматикой, однако его распространенность невелика, что не способствует созданию ясного представления о возможностях его реального применения. Datalog обладает наиболее простой грамматикой. Задача преобразования выражений средней сложности на языке Datalog в выражения других языков запросов представляется достаточно простой в силу высокой абстракции языка и простоты его идеи.

Отдельно необходимо сказать о частном критерии (2 б). Хотя большинство задач трансляции некоторого языка запросов в другой язык сводятся к получению SQL -выражений из выражений на ином языке, достаточно важным эмпирическим показателем является наличие трансляторов и методов трансляции в другие языки запросов. Данный показатель с практической точки зрения сможет охарактеризовать сложность выполнения этапа (В) схемы, приведенной на рисунке. Необходимо заметить, что существует большое количество практических и теоретических работ по трансляции SQL в другие языки запросов, в частности необходимо отметить различные промышленные средства объектно-реляционного отображения, а также интерфейсы к подмножествам языка Prolog . Большой интерес представляют теоретические и практические работы по трансляции языка Datalog в другие языки запросов. Среди них необходимо выделить библиотеку pyDatalog , предоставляющую готовые средства исполнения Datalog -запросов к различным СУБД. Говоря о методах трансляции остальных языков запросов, необходимо указать на то, что разработка данного вопроса в отношении языка Tutorial D носит преимущественно академический характер, а в отношении языков LINQ , JPQL , XPath – практический и узконаправленный.

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

Таблица 4 составлена исходя из стандартов, которые применяются в языке SQL, и реляционной модели данных. Согласно данному анализу языки XPath и JPQL еще раз подтвердили свою специфичность; язык LINQ имеет недостаток в том, что могут возникать ситуации, когда результат зависит от порядка обхода. Такие ситуации скорее исключение, однако эта особенность указывает на высокую императивную составляющую LINQ . Большая часть современных реализаций Datalog поддерживает все рассматриваемые особенности, на уровне стандартных предикатов, что обусловлено сущностью данного языка запросов.

Таблица 4

Особенности языков запросов

Параметр	SQL	Tutorial D	Datalog	XPath	JPQL	LINQ
Описание данных	да	да	да	нет	нет	частично
Запросы на выборку	да	да	да	да	да	да
Выборка именованных полей	да	да	зависит от реализации	да	частично	да
Условная часть запроса	да	да	да	да	да	да
Соединение выборок	да	да	зависит от реализации	частично	да	да
Объединение выборок	да	да	да	частично	да	да
Группировка	да	да	зависит от реализации	да	частично	да
Сортировка выборки	да	да	зависит от реализации	да	да	да
Влияние порядка обхода	нет	нет	нет	нет	нет	частично

Заключение

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

Язык SQL фактически является стандартом среди языков запросов. Для него хорошо разработана грамматика, имеется стандарт языка, а также много средств и методов, которые описывают преобразования выражений с SQL в выражения на других языках запросов. Нельзя не отметить и наличие научных работ, в которых описываются различные алгоритмы преобразования ЕЯ-запросов в запросы к источникам данных с использованием SQL. Однако при создании транслятора ЕЯ-запросов в запросы к структурированным источникам данных нельзя не учитывать проблемы семантического анализа. Также нельзя забывать о том, что на современном этапе развития структурированных источников данных появляется большое количество источников данных (например, Google Knowledge Graph ), которые основаны на нереляционных моделях и не ориентированы на использование языка SQL в качестве языка запросов. Таким образом, язык SQL может хорошо подходить в качестве промежуточного языка в том случае, если алгоритм трансляции не ориентирован на достаточно глубокий семантический анализ, а целевыми источниками данных являются реляционные или объектно -реляционные базы данных.

Язык D ( Tutorial D / Industrial D и диалекты) в целом имеет те же плюсы и минусы, что и язык SQL , но в силу большей абстрактности использование его в качестве промежуточного языка может облегчить трансляцию в языки целевых запросов, ориентированных на объектные базы данных и данные в форматах XML и JSON . Однако на практике язык D применяется достаточно редко и носит академический характер, поэтому его использование в качестве промежуточного языка может быть сопряжено как с проблемами взаимодействия с каким-либо подсистемами ЕЯ-транслятора (например, лингвистической базой знаний), так и с проблемами теоретического плана.

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

Формально язык XPath соответствует всем требованиям, сформулированным к языку промежуточного представления. Однако на практике данный язык является ориентированным в основном на иерархические модели данных. Эта проблема характерна для всех моделей типа «Иерархия» и вызвана как разнообразием самих моделей данных, так и недостаточной проработанностью теоретической базы. Поэтому невозможно однозначно утверждать об универсальности языков запросов, используемых для данных моделей. Таким образом, применение XPath как языка внутреннего представления нецелесообразно, хотя при создании ЕЯ-интерфейсов, ориентированных на иерархические модели данных, он может использоваться как язык целевых запросов.

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

LINQ – подмножество языка C #, реализующее технологию доступа к структурированным источникам данных. С точки зрения реализации ЕЯ-интерфейсов, этот факт является положительным, но с точки зрения реализации методов анализа и трансляции ЕЯ-запросов – неудовлетворительным, так как технология LINQ используется как расширение императивного языка программирования и только в тесной связке с ним. Таким образом использовать LINQ в качестве языка промежуточного представления удобно только в тех случаях, когда разрабатывается узкоспециализированный ЕЯ-интерфейс, оперирующий ограниченным набором видов и вариантов запросов, но имеющий доступ к структурированным источникам данных, реализующих разные модели данных.

Таким образом, с точки зрения баланса универсальности, простоты реализации, а также ориентированности на использование семантики ЕЯ-запросов, наиболее перспективным в качестве языка промежуточного представления является язык Datalog , а далее по степени уменьшения целесообразности – SQL и Tutorial D .