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

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

Бородин Д.С., Строганов Ю.В., МГТУ им. Н.Э Баумана demansen@yandex.ru, ukunsun@mail.ru

Аннотация

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

1 Введение

Задача автоматизации технологических процессов требует специальных техник обработки информации в составе диалоговых систем. В частности, для САПР стоит задача автоматизации обработки пользовательских запросов к базам данных в целях сокращения цикла обучения пользователей. Эта задача может быть решена при помощи методов автоматического перевода запросов пользователя на естественном языке на формальный язык запросов к базе данных (БД).

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

• преобразование предложений на естественном языке в информацию, пригодную для машинной обработки;

• транслирование запросов, составленных на основании извлечённой из текста информации, к БД.

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

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

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

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

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

При наличии БД, составленной из понятий, выделенных из выбранной предметной области, имеет смысл говорить о разработке методов преобразования естественно-языковых запросов в запросы к базам данных. Разрабатываемая система может быть описана следующей схемой (см. рис. 1).

Рис. 1. Условная схема генерации методов формирования запросов на естественном языке

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

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

• методы компьютерной лингвистики, которые позволяют осуществить преобразование информации на естественном языке в соответствующую «машинную» информацию;

• составление различных ограничений, налагаемых на запросы (позволяет однозначно определить входную и выходную информацию в преобразовании данных);

• выделение сущностей, соответствующих базе данных, из естественного языка

• выбор типа реализуемой базы данных, ограничений на выбранную базу данных, а также программных средств, реализующих работу с ней (позволяет определить, с какими данными, и в каком объеме будет работать конечный пользователь);

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

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

2.1

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

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

Можно отметить основные требования к организации данных [Дейт, 2005]:

• неизбыточность (присутствие в одном экземпляре);

• совместное использование многими пользователями;

• эффективность доступа (малое время отклика);

• целостность (соответствие внутренней логике);

• безопасность;

• восстановление после сбоев;

• независимость от прикладных программ.

В качестве основной характеристики баз данных предполагается исследовать преимущества и недостатки моделей данных соответствующих систем управления базами данных. На сегодняшний день имеется следующая классификация СУБД по модели данных:

• дореляционные, представленные инвертированными списками, иерархическими и сетевыми БД;

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

• постреляционные.

Рассмотрим эти классы подробно в совокупности с соответствующими СУБД.

3 Дореляционные базы данных

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

1. Системы управления такими базами данных использовались в течение довольно долгого времени. Одной из актуальных проблем работы с такими базами данных является совместное их использование с современными СУБД.

2. Такие системы не основывались на каких-либо абстрактных моделях - понятие абстрактной модели в ранних СУБД появились позже на основе анализа и выявления признаков различных систем.

3. Доступ осуществлялся на уровне записей.

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

5. После появления реляционных СУБД, ранние системы стали оснащаться «реляционными интерфейсами».

Дореляционные СУБД обладают следующими достоинствами.

1. Развитые средства управления данными во внешней памяти на низком уровне.

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

3. В сетевых системах - возможность экономии памяти за счет разделения подобъек-тов.

В то же время, дореляционные СУБД имеют следующие недостатки.

1. Слишком сложное использование.

2. Возникает необходимость знания о физической организации.

3. Прикладные системы зависят от физической организации СУБД.

4. Логика прикладных систем перегружена деталями организации доступа к базе данных.

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

4 Реляционные базы данных

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

Для лучшего понимания реляционных баз данных следует отметить три важных обстоятельства [Реляционные базы данных, 2015]:

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

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

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

данных:

• модель данных отображает информацию в наиболее простой для пользователя форме;

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

• позволяет создавать языки манипулирования данными, имеющие непроцедурную природу;

• манипулирование данными осуществляется на уровне выходной базы данных и позволяет производить изменения. Существующие недостатки реляционных

баз данных:

• самый медленный доступ к данным среди всех моделей данных;

• трудоемкость разработки.

5 Постреляционные базы данных

NoSQL (Not Only SQL) - термин для описания различных технологий, возникших для удовлетворения требований, таких как "Web-scale":

• много данных;

• огромное количество пользователей;

• сложные данные.

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

• обрабатываются огромные объемы данных, разделяемых между серверами;

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

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

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

• поколоночные;

• документно-ориентированные;

• хранилища «ключ-значение», кортежные хранилища;

• базы данных на основе графов;

• базы данных, основанные на других моделях данных.

Отдельного внимания в данной работе заслуживают графовые базы данных, реализующие сетевую модель в виде графа и его обобщений. По мнению некоторых авторов, для задач с естественной графовой структурой данных графовые системы управления базами данных могут существенно превосходить реляционные по производительности, а также иметь преимущества в наглядности представления и внесения изменений в схему базы данных [Robinson et al., 2013]. Так как задача обработки запросов на естественном языке с помощью методов автоматической обработки позволяет нам получить синтаксическое дерево, то таким образом можно сделать вывод о том, что графовые базы данных будут являться одним из возможных способов реализации базы данных.

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

• реляционная база данных (MSSQL, MYSQL и пр.);

• графовая база данных (постреляционная, например, GraphDB).

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

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

Объектом исследования компьютерной лингвистики являются различные тексты -образцы письменной или устной речи, несущие в себе определенный смысл и имеющие линейную структуру. При работе с текстами язык выступает в роли средства приема/передачи необходимой информации. Все тексты, будь то письменные или устные, состоят из определенного набора структурных единиц, которые на сегодняшний день могут быть разбиты на следующие уровни [Большакова и др., 2011]:

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

• морфологический уровень, представляющий собой уровень словоформ - слов в определенной грамматической форме (например, актером, актера, актер);

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

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

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

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

Условная схема лингвистического модуля, а также предполагаемых используемых компонентов, входных и выходных данных, представлена на рис. 2.

Под графематическим анализом подразумевается первоначальный этап обработки предложений на естественном языке, в ходе которого определяются токены - элементы грамматической структуры (слова, знаки препинания и т.д.) [Седунов, 2007]. При этом можно выделить следующие основные функции графематического анализа [Jackson, Moulinier, 2002]:

• разбиение текста на графемы;

• определение границ предложений;

• определение регистра слов;

• распознавание имен собственных и сокращений;

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

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

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

Немаловажной проблемой при обработке текстовой информации на естественном языке является распознавание смысла содержащихся в тексте слов и выражений, а также различных коллокаций, представляющих синтаксически и семантически неделимые единицы, выбор компонентов которых зависит от контекста [Архипов, 2015]. Эта проблема решается средствами семантического анализа, в котором производится оценка различного рода многозначностей, связанных с большой системностью естественного языка.

Добавим, что омонимия существенно проявляется на всех уровнях естественного языка. Укажем некоторые ее виды [Большакова и

др., 2011].

• Лексическая омонимия - одинаково звучащие и пишущиеся слова, не имеющие общего смысла (например, ключ - родник или средство открытия замков).

Рис. 2. Условная схема лингвистического модуля

• Морфологическая омонимия - совпадение форм одного и того же слова (лексем). Например, могут совпадать словоформы именительного и винительного падежей («прут»).

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

• Синтаксическая омонимия - неоднозначность синтаксической структуры, приводящая к различным интерпретациям (например, «Туристы из Москвы поехали в Брест»).

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

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

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

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

2. с помощью средств логического программирования.

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

Второй способ пригоден для работы как с графовыми, так и с реляционными БД, т.к. средства логического программирования позволяют представить синтаксическое дерево как в виде семантической сети, так и в виде различных таблиц, свойств и атрибутов, а также связей между таблицами. Более того, анализ доступных информационных источников показал, что на данный момент имеются весьма эффективные трансляторы из языка логического программирования в формальный язык работы с базами данных, что существенно упрощает процесс составления запросов [Draxler, 1993]. Однако упомянутый транслятор имеет ряд ограничений, которые впоследствии могут быть отброшены при соответствующей модификации.

На сегодняшний день существует достаточно много языков логического программирования, однако наиболее известным среди всех является Prolog. Это язык программирования для нечисловых вычислений, хорошо приспособленный для решения проблем, касающихся объектов и отношений между объектами. Prolog основан на языке предикатов математической логики дизъюнктов Хорна, являющихся подмножеством логики предикатов первого порядка. Условно, можно выделить следующие факты о данном техническом средстве [Введение в Пролог, 2016].

• Программирование на Prolog представляет собой процесс определения отношений и выдачи системе запросов об этих отношениях.

• Отношение может быть определено на основе фактов, представляющих собой n-элементный кортеж, а также на основе различных правил вывода.

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

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

• База знаний на Prolog состоит из совокупности фактов и правил. В процессе работы можно корректировать имеющуюся сово-

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

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

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

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

6 Общие выводы о разрабатываемой системе преобразования естественно-языковых запросов

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

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

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

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

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

Рис. 3. Условная схема методов получения запросов к базам данных

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

7 Заключение

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

Благодарности

Мы выражаем признательность преподавателям кафедры «Программное обеспечение ЭВМ и информационные технологии» МГТУ имени Н.Э. Баумана Волковой Л.Л. и Толпинской Н.Б., принявшим значительное участие в разработке данной работы. Без вашего труда нам было бы значительно сложнее составить этот документ.

Список литературы

Архипов А.В. Коллокации. Фонд знаний «Ломоносов» [Электронный ресурс], 2015. URL: http://www.lomonosov-

fund.ru/enc/ru/encyclopedia:0127195 (дата обращения 13.03.2016).

Большакова Е. И., Клышинский Э. С., Ландэ Д. В., Носков А. А., Пескова О. В., Ягунова Е. В. Автоматическая обработка текстов на есте-

ственном языке и компьютерная лингвистика: учебное пособие. М.: МГОМ, 2011. 272 с.

Введение в Пролог. Методическое пособие [Электронный ресурс], 2016. URL: http : //www. williamspublishing.com/PDF/5 -8459-0664-4/part.pdf (дата обращения 15.03.2016).

Дейт, К. Д. Введение в системы баз данных. М.: Вильяме, 2005. С. 41-75.

Клышинский Э.С., Кочеткова Н.А. Метод извлечения технических терминов с использованием меры странности. // Новые информационные технологии в автоматизированных системах: материалы семнадцатого научно-практического семинара. М.: ИПМ им. М.В. Келдыша, 2014. С. 365-370.

Компьютерная лингвистика. Энциклопедия Кругосвет. [Электронный ресурс], 2016. URL: http : //files. school-

collection.edu.ru/dlrstore/0032e870-dadd-5ab2-a83e-85e032c459b2/1009220A.htm (дата обращения 13.03.2016).

Кузнецов С.Д. Основы организации современных баз данных [Электронный ресурс], 2015. URL:

http://www.lcard.ru/~nail/database/osbd/contents .htm (дата обращения 13.03.2016).

Пруцков А.В., Розанов А.К. Методы морфологической обработки текстов // Прикаспийский журнал: управление и высокие технологии. № 3 (27), 2014. С. 119-133.

Реляционные базы данных: достоинства и недостатки. [Электронный ресурс], 2015. URL: https://sites.google.com/site/gosyvmkss12/bazy-dannyh/07-relacionnye-bazy-dannyh-dostoinstva-i-nedostatki (дата обращения 13.03.2016).

Седунов А. А. Модель графематического анализа в системе обработки естественного языка. // Воронежский государственный университет, Вестник ВГУ: системный анализ и информационные технологии, № 2, 2007.

Толпинская Н.Б. Информационная система для поддержания управления. // Проблемы информатики: сб. науч.-метод. статей, РГСУ, Ростов н/Д, 1999.

Draxler C. 1993. A powerful Prolog to SQL compiler. Center for Information and Language Processing, Munich, Germany.

Jackson P., Moulinier I. 2002. Natural Language Processing for Online Applications. Benjamins Publishing, Amsterdam, Netherlands.

Robinson I., Webber J., Eifrem E., 2013. Graph Databases. O'Reilly, Sebastopol, USA.