автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы

УДК 004.8

На правах рукописи

ЕВДОКИМОВА Инга Сергеевна

МЕТОДЫ И АЛГОРИТМЫ ТРАНСЛЯЦИИ ЕСТЕСТВЕННО-ЯЗЫКОВЫХ ЗАПРОСОВ К БАЗЕ ДАННЫХ В SQL-ЗАПРОСЫ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2004

Работа выполнена в Восточно-Сибирском государственном технологическом университете

Научный руководитель: кандидат технических наук,

доцент

Официальные оппоненты: доктор физико-математических

наук, профессор

Найханова Л.В.

Журавлев В.М.

доктор технических наук, профессор

Доррер ГА

Ведущая организация: Государственный научно-исследовательский

институт информационных технологий телекоммуникаций

Зашита состоится «25» ноября 2004 г. в часов на заседании

диссертационного совета Д 212.098.03 в Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, ауд 4-17, тел. (8-3912)-49-73-81, факс (8-3912)-49-79-90

С диссертацией можно ознакомиться в научной библиотеке Красноярского государственного технического университета.

Автореферат разослан «22» октября 2004 г.

Ученый секретарь Диссертационного совета,

кандидат технических наук, профессор КГТУ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задача интеллектуальной обработки текстов на естественном языке впервые появилась на рубеже 60-х—70-х гг. Работы последних лет связаны с решением проблемы анализа смысла языка в приложении к созданию систем диалога с программным обеспечением. Подходов к решению задачи понимания естественноязыковых запросов несколько. Наиболее распространенными являются подходы, основанные на синтаксическом, семантическом анализах и шаблонах. Первый подход основан на использовании синтаксических конструкций. Синтаксическое представление запроса строится на основе подлежащего, сказуемого, прямого дополнения и т.п., которые определяются с помощью морфологических характеристик. Такое представление ничего не говорит о смысле запроса.

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

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

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

К настоящему времени существующие естественно-языковые системы используют в основном два последних подхода. Второй подход реализован в достаточно распространенной системе ЗАПСИБ, разработанной в середине 80-х годов. Система позволяет вести общение на ограниченном подмножестве естественного языка. Развитием проекта является система InterBase, вышедшая в 1990 году. Система основана на семантически-ориентированном анализе и продолжает ряд естественноязыковых технологий лаборатории искусственного интеллекта ВЦ АН Новосибирска, затем фирмы «Интеллектуальные технологии», а теперь РосНИИ искусственного интеллекта. В 2001 году эта система была переработана и получила название InBASE в виде коммерческого продукта. Интересной особенностью InBASE является возможность моделирования предметной области на естественном языке: с помощью класса словарных статей «Толкование» смысл слова можно описать простой фразой. Это позволяет настраивать естественно-языковые интерфейсы людям, не обладающим навыками инженеров знаний. Основным недостатком данной системы является то, что кортежи базы данных продублированы в словарях - отдельных файлах. В базах данных больших объемов этот недостаток может стать проблемой.

Ярким представителем третьего подхода является система English Query. Система English Query от Microsoft основана на синтаксически-ориентированных шаблонах, связываемых с моделью предметной области, и, через нее - со схемой базы данных. Этот продукт позволяет строить естественно-языковые интерфейсы только для английского языка и работает только с Microsoft SQL Server, в этом смысле это лишь утилита, поставляемая с SQL-сервером, именно так она и позиционируется.

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

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

4

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

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

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

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

2. Разработка лингвистической модели транслятора;

3. Разработка интерпретационной модели задачи;

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

5. Разработка методов трансляции естественно-языковых запросов к базе данных, представленных в виде простых предложений русского языка, в SQL-запросы.

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

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

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

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

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

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

Публикации. Основные результаты диссертационной работы опубликованы в 9 печатных работах, из которых 5 статей, 2 тезиса докладов, 1 монография и 1 свидетельство об официальной регистрации программы для ЭВМ.

Результаты исследований вошли в материалы итогового отчета о научно-исследовательской работе по госбюджетной теме «Модель лингвистического

процессора ЕЯ-системы общения с БД» (ГР 01940007404, Инв. 0220,0003382,, 1999г.). Исследования были поддержаны грантом Правительства Республики Бурятия для молодых ученых Республики Бурятия 2002 года.

Апробация результатов исследования. Основные положения диссертационной работы докладывались и обсуждались на международной научно-технической конференции "Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и СИИ" (Вологда, 2001 г.), III Международной выставки-конференции "Информационные технологии и телекоммуникации в образовании" (Москва, 2001 г.), VI и VII всероссийской конференции по проблемам информатизации региона ПИР (Красноярск, 2000 и 2001 гг.), первой, третьей, четвертой и пятой конференциях «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2000, 2002, 2003 и 2004 гг.), внуривузовской научной конференции преподавателей, научных работников и аспирантов ВСГТУ (г.Улан-Удэ, 2000-2004 гг.), меж кафедральном семинаре «Концепции и методологии создания современных информационных систем» (СибГТУ, г. Красноярск, 22 сентября 2004 г.). Ряд положений диссертации был использован при подготовке учебного курса «Естественно-языковые системы» по специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем» и нашел применение в учебном процессе ВСГТУ.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и шести приложений. Работа содержит 109 страниц текста, 6 рисунков и 7 таблиц. Список литературы содержит 128 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

В работе в качестве исходной информации рассматриваются SQL-ориентированная база данных и запрос пользователя к ней, на написание которого накладываются следующие ограничения: запрос может состоять из одного или нескольких простых предложений на русском языке; если запрос содержит несколько простых предложений, то каждое последующее предложение должно содержать существительное, приведенное в одном из предыдущих предложений; в запросе должна затребываться информация, релевантная рассматриваемой базе данных; затребываемая в запросе информация должна иметь четкий характер, т.е. не должны использоваться указательные местоимения я, ты (вы), он (она, оно), они, этот, тот, такой, таков, столько и т.п., частицы «ли», «либо», «го» и другие; рекомендуется начинать запрос со специальных слов: Выдать, Показать, Перечислить, Как, Когда, Где, В какое время, Какой, Сколько.

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

Лингвистическая модель М содержит информацию о морфологии, синтаксисе и семантике подмножества естественного языка:

где — грамматическая модель; — интерпретационная модель; — модель трансляции, включающая семантический и проблемный анализы.

Граммагическая модель в свою очередь состоит из кортежа:

где модель морфологического анализа, модель синтаксического анализа.

Интерпретационная модель задается в виде вектора:

где М\ — модель метаописания базы данных^^модель проблемной среды.

Базовые механизмы и реализуют четыре основных отображения: Чу. Т-ьХ

(морфологический разбор); Ч,1: Х-ьв (синтаксический разбор); Ч^: (7->0

(семантический и проблемный анализы), Ч^: (3->() (трансляция), где Т - текст естественного языка в виде множества лексем; X - множество лексем с векторами

морфологической информации v; G - граф зависимостей, в вершинах которого

располагаются лексемы, а дуги отображают бинарные словосочетания; G - граф, в вершинах которого располагаются термины физической модели базы данных; Q - SQL-запрос в виде команды SELECT.

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

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

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

Тогда, формальное определение условия применимости представляется в виде:

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

принимающий значение V и 3, D,t - задает область интерпретации терма tr

Начальное состояние (входная ситуация) системы продукций содержит

конъюнкцию терминальных фактов: - высказывание, а

суть константы.

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

Лавленда, Р.Ковальского и Кюнера, для применения которого: во-первых, задается входная ситуация </„, во-вторых, выбирается продукция р^р^), р^еР^, Рг'еРг, где Рг - система продукций, /V - /-тая подсистема продукций, в-третьих, формируется множество дизъюнктов Г. Множество Г формируется из двух групп формул. Первая группа Г) включает формулы, описывающие закономерности проблемной среды и закономерности, определяющие метаописание базы данных. Во вторую группу Г2 включается множество дизъюнктов, полученных в результате преобразования формулы, задающей условие применимости продукции в скулемовской

стандартной форме (ССФ).

При выполнении линейной резолюции доказывается формула Гл£/0. При этом входные дизъюнкты выбираются из множества фактов, задающих Конъюнкция

фактов А Р1°(е1> ~>ет,), задающая </0, может быть представлена как:

£/0= |р/'(е|,...,е(),1 )| ( — количество фактам^ — длина кортежа ¡— того фактае} (4)

Таким образом, Со - это элемент множества <10, и он является первым центральным дизъюнктом при построении дерева вывода для доказательства истинности условия применимости некоторой (-той продукции для выбранного факта. Боковые дизъюнкты В выбираются из множества Г. Условием выбора является наличие в дизъюнкте РеГ литеры, контрарной самой левой литере центрального дизъюнкта С. Затем дизъюнкты С и В должны быть унифицированы.

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

Параметрический предикат: Рра,(х, ((р1,Уц1), ..., ..., 1{рт,Уи"')), где,—имя

понятия; /(/?„!)') — терм, задающий соответствие между р1 — именем /-того показателя понятия и его у'-тым значение'ммоличество показателей понятия х.

Предикат эквивалентности: Рц(}>, у) — предикат, задающий отношение тождества левого и правого элементов кортежа.

где х — первое понятие; у — второе понятие; ( — тип отношения г между ними.

Функциональный предикат: /^¡„(х;, ...,х„),у,/), где 1т(х/, ...,х„) - терм, задающий п входных переменных — выходная переменная; ссылка на функциональную процедуру Р, преобразующую входные переменные в выходную. Функциональная процедура Р реализует некоторый вычислительный алгоритм и активизируется при выполнении алгоритма унификации.

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

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

Третья глава посвящена методам и алгоритмам трансляции. В ней описываются интерпретационная модель транслятора М2, а также преобразования Ч^ и математической модели.

Интерпретационная модель представляется в виде закономерностей

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

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

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

где х - сущность в терминах физической модели данных; !{р,у}) — терм, задающий отношение характеризации в виде соответствия между - идентификатором атрибута физической модели данных и его у'-тым п р и з н ат^о/м - количество атрибутов, составляющих сущность х. Составные предикаты Ра(х,}', О используются для описания отношений типизации, перевода и конкретизации. Первый составной предикат описывает отношения типизации перевода и конкретизации между двумя объектами биноминативного предложения. Второй составной предикат позволяет описывать отношения типизации и перевода между двумя объектами биноминативного предложения, первый из которых представляется в виде нескольких понятий естественного языка:

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

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

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

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

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

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

1) отношение тождества между понятием проблемной среды и понятием логической модели данных;

2) отношение подобия между понятием логической модели данных и понятием -синонимом проблемной среды;

3) отношение подобия между понятием естественного языка, релевантным проблемной среде, и лексемой — синонимом данного понятия;

4) отношение номинации между понятием проблемной среды и множеством понятий логической модели данных;

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

6) отношение типизации между специальным понятием проблемной среды и его типом;

7) отношение перевода между специальным понятием проблемной среды и служебным термином базы данных SQL;

8) отношение агрегации понятий проблемной среды и термина логической модели данных.

Для представления закономерностей проблемной среды используются составные предикаты (5) и (7), а также составной предикат вида:

где х - понятие проблемной среды, у - понятие логической модели данных {уее!) или понятие проблемной среды (уеЕ'), í(zj,...,z/¡) — терм, задающий множество понятий логической модели данных или проблемной среды которые совместно с

переменной у составляют определение понятия х, r(verb) - отношение связи между у и выраженное глаголом естественного языка verb, - отношение номинации между понятием х и его определением.

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

Построение преобразования Для построения выполняется два

последовательных преобразования: - граф зависимостей в

терминах логической модели данных. Первое преобразование осуществляется на основе анализа VgeG и определения её значения принадлежности терминам логической модели данных lea1. В результате преобразования ^з строится граф G', в котором вершины составляют термины Для каждой вершины формируется вектор

признак, определяющий принадлежность множеству терминов логической модели данных Н1; zj -тин верши 1 - атрибут логической модели данных, 2 - сущность логической модели данных, 3 - операнд оператора SQL, 4-операция оператора SQL, 5 - вычислительная процедура, 6 - значение атрибута базы данных; тип признака понятия для атрибута логической модели данных (d-дифференциальный, в случае, если

вершина является сущностью.

Для построения графа осуществляется поиск транзитивного замыкания

преобразований вершин граф,

гомеоморфный графу G. Если транзитивное замыкание не найдено, то это соответствует ситуации, при которой вершина несет в себе вспомогательную информацию для формирования SQL-запроса. Для выполнения преобразований вершин g выдвигаются

12

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

1) специальным понятием проблемной среды;

2) термином логической модели данных <63*;

3) понятием проблемной среды <еЕ*.

Построение транзитивного замыкания выполняется последовательно для

каждой гипотезы путем задания входной ситуации (¡о, которой описывается вершина geG. Для доказательства каждой гипотезы формируется множество предикатов Г, на котором доказывается утверждение, описывающее ситуацию Если в результате текущего доказательства получается неуспех, то осуществляется переход к доказательству следующей гипотезы, в противном случае - переход на рассмотрение следующей вершины.

Доказательство первой гипотезы. Эта гипотеза предполагает, что лексема в вершине g является специальным понятием проблемной среды. Для её доказательства во множество Г включаются предикаты, задающие отношение типизации 1[р. Входная

ситуация при этом описывается предикатом (1(гР,(х,у,1'ир). Если доказательство проходит успешно, то в вершину соответствующую вершине заносится оператор, операнд или вычислительная процедура языка SQL, согласно отношению перевода 1'г, а также заполняется элемент

Доказательство второй гипотезы. При успешном доказательстве утверждения о том, что вершина является термином логической модели данных, вершине приписывается признак, который определяет тип термина (атрибут или сущность). Входная ситуация при этом задается в виде: с/о = Р,(х, у, Например,

или

В этом случае множество предикатов Г формируется из предикатов типизации, описывающих логическую модель данных (5) и (7), например:

Г={ Р, (фамилия, атрибут, 1,,р), Р1 (студент, сущность ,1[р),...,Р, (группа,сущность, 1'1р), Р,(специальность,сущность,1'1р),..., Рг{¡(телефон,домашний),атрибут,}.

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

Доказательство третьей гипотезы. Предположение о том, что вершина gsG является понятием проблемной среды порождает четыре дополнительные

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

1)лексема является понятием, тождественным некоторому термину логической модели данных;

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

3) лексема является составной частью определения некоторого понятия;

4) лексема является синонимом некоторою термина логической модели данных или понятия естественного языка, релевантного проблемной среде.

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

Вторая гипотеза нижнего уровня. Множество Г при доказательстве этой гипотезы составляют предикаты с отношениями агрегации t'v и обобщения . Если доказательство проходит успешно, то в элемент записывается

значение «6», которое указывает, что понятие является значением базы данных, а перед вершиной gдобавляется новая вершина g'. В добавленную вершину g' записывается агрегированное или обобщенное понятие логической модели данных, а для доказательства корректности проверяется вторая гипотеза верхнего уровня.

Третья гипотеза нижнего уровня. Для её доказательства формируется множество Г, состоящее из предикатов с отношениями номинации Если доказательство

проходит успешно, то осуществляется запись в вершину g' аргумента у предиката Р,(х, и добавление вершин ниже текущей, в которые

записываются значения

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

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

Второе преобразование заключается в переименовании

терминов логической модели данных, расположенных в оставшихся вершинах на термины физической модели данных. При этом каждой вершине приписывается вектор т, ~<x,i, х,2, х,з, х,4, x,i>, где x,i - тип вершины: 1- таблица, 2 -столбец, 3 — оператор; 4 - значение; х,2 - идентификатор таблицы, если Х/-2 или 4, в противном случае - идентификатор столбца, если в противном случае

х,4 - null или I - признак добавленной вершины; x,i - вид связи: 1 - связь «таблица -таблица», 2 — связь «атрибут - значение», 3 — связь «атрибут — логическая операция -значение», 4 — связь «вычислительная процедура - атрибут» , 5 — связь «атрибут -атрибут», 6 — связь «таблица — атрибут».

Построение преобразования 4V Для построения 4*4 необходимо выполнить

преобразования: G——в которь£к-граф зависимостей в терминах

физической модели данных, G - граф SQL-запроса, Q - SQL-запрос в виде команды SELECT.

Преобразование Физическая модель данных представляет собой граф Е,

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

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

вершинами графа соответствующих паре смежных вершин графа

зависимостей таких что, и добавлением их в граф

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

- существует прямая связь, когда паре смежных вершин графа соответствуют смежные вершины графа Е;

- существует непрямая связь, когда паре смежных вершин графа соответствуют несмежные вершины графа Е.

Гипотеза первая «Прямые связи вершин графа G». Здесь рассматриваются три ситуации, зависящие от комбинации типов вершин. Первая ситуация касается случая,

когда вершинами графа могут быть только идентификаторы таблиц. При этом связь

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

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

графа G могут быть только идентификаторы таблиц и столбцов, а третья ситуация

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

Гипотеза вторая «Непрямые связи вершин графа G». Гипотеза описывает ситуации, когда паре смежных вершин может соответствовать пара

несмежных вершин графа Е, т.е. расстояние между вершинами е^е^ больше одной дуги. Для доказательства гипотезы необходимо найти путь от ('-той таблицы к j-той таблице. В связи с тем, что граф Е задан множеством предикатов то путь от

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

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

дуги gi>gj и добавление новой вершинычто порождает новые дуги g,,gn,

gn>g/i которые составляют часть A(G ) - подграфы графа G , а полученный в

результате преобразования будет гомеоморфен графу

Преобразование заключается в построении SQL-запроса на основе

формирования:

1) объектной части SQL-запроса:

- заполнение списка select_Jisl ключевого слова «SELECT»;

- заполнение списка tablejsource ключевого слова «FROM»;

2) условной части SQL-запроса путем заполнения списка search condition ключевого слова «WHERE», который включает фильтр на выбираемые кортежи по равенству дифференциальных признаков вектора г смежных пар графа и фильтр по значению формируется из трех смежных вершин, содержащих идентификатор атрибута, операцию оператора SQL-запроса и значение базы данных.

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

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

ЗАКЛЮЧЕНИЕ

Получены следующие научные и практические результаты работы:

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

2. Разработана модель лингвистического транслятора естественно-языкового запроса в SQL-запрос базы данных, которая основывается на модели контекстного фрагментирования.

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

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

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

6. Разработаны методы и алгоритмы трансляции ЕЯ-запросов в SQL-запросы к базе данных.

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

1. Найханова Л.В., Евдокимова И.С. Метод трансляции ЕЯ-запросов в SQL-запросы // Теоретические и прикладные вопросы современных информационных технологий: Мат. I Всерос. науч.-тех. конф. - Улан-Удэ: Изд-во ВСГТУ, 2000. - С. 219-226.

2. Найханова Л. В, Евдокимова И С. Описание математической модели лингвистического процессора обработчика естественно — языковых запросов // Сб науч.тр. Сер. Технические науки. Вып.7.- Т.1. - Улан-Удэ: Изд-во ВСГТУ, 2000.- С. 7682.

3. Найханова Л.В., Евдокимова И.С. Обзор методов синтаксического анализа естественно-языкового предложения // Проблемы информатизации региона ПИР'2000: Тез. докл. VI Всерос. науч.-прак. конф. - Красноярск: Изд-во КГТУ, 2000. - С. 77-80.

4. Евдокимова И.С. Модель представления знаний синтаксического анализатора // Теоретические и прикладные вопросы современных информационных технологий: Мат. II Всерос. науч.-тех. конф. - Улан-Удэ: Изд-во ВСГТУ, 2001. - С. 206-211.

5. Найханова Л.В., Евдокимова И.С, Лубсанов ВА. О многовариантности синтаксического анализа // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и СИИ: Мат. междунар. науч.-тех. конф.- Вологда: Изд-во ВоГТУ, 2001. - С. 273-276.

6. Найханова Л.В., Евдокимова И.С, Шатунов А.А. Формирование тезауруса морфологического анализа ЕЯ-текста // Информационные технологии и телекоммуникации в образовании: Тез. докл. III междунар. выставки-конференции. — М., 2001.-С. 68-69.

7. Найханова Л.В., Евдокимова И.С. Аппарат описания формальных моделей лингвистического транслятора // Теоретические и прикладные вопросы современных информационных технологий: Мат. V Всерос. науч.-тех. конф. - Улан-Удэ: Изд-во ВСГТУ, 2004. - С. 96-99.

8. Найханова Л.В., Евдокимова И.С. Методы и алгоритмы трансляции естественноязыковых запросов к базе данных в SQL-запросы: Монография.- Улан-Удэ: Изд-во ВСГТУ, 2004.-148 с.

9. Найханова Л.В., Евдокимова И.С Программный комплекс по трансляции естественно-языковых запросов к базе данных в SQL-запросы. Свидетельство об официальной регистрации программы для ЭВМ № .-М.: Всероссийское агентство по патентам и товарным знакам, 2004.-1 с.

Соискатель

И.С. Евдокимова

Подписано в печать 14.10.2004 г.

Формат бумаги 60x84 1/16 Усл. печ. л. 1,16. Уч.-изд. Л. 0,8. Тираж 100 экз. Заказ № 148

Издательство ВСГТУ 670013, РБ, г.Улан-Удэ, ул.Ключевская 40, в.

»1945 J

ВВЕДЕНИЕ.

1. ОБЗОР И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ.

1.1. Структура лингвистического анализатора.

1.2. Анализ методов и подходов морфологического анализа.

1.3. Аналитический обзор методов синтаксического анализа.

1.4. Аналитический обзор семантических моделей.

1.5. Выводы и постановка задачи.

2. МОДЕЛЬ ЛИНГВИСТИЧЕСКОГО ТРАНСЛЯТОРА.

2.1. Математическая модель транслятора.

2.2. Аппарат описания формальных моделей.

2.2.1. Введение в системы продукций.

2.2.2. Описание формального аппарата.

2.3. Модель морфологического анализа.

2.3.1. Содержательное описание модели морфологического анализа.

2.3.1.1. Словари и таблицы совместимости.

2.3.1.2. Алгоритм морфологического анализа.

2.3.2. База правил морфологического анализа.

2.3.2.1. Сорта морфологического анализа.

2.3.2.2. Типовые предикаты условий применимости продукций морфологического анализа.

2.3.2.3. Система продукций морфологического анализа.

2.4. Модель синтаксического анализа.

2.4.1. Содержательное описание модели синтаксического анализа.

2.4.1.1. Алгоритм синтаксического анализа.

2.4.1.2. База знаний синтаксического анализа.

2.4.2. База правил синтаксического анализа.

2.5. Выводы по второй главе.

3. МОДЕЛЬ ТРАНСЛЯЦИИ.

3.1. Интерпретационная модель лингвистического транслятора.

3.1.1. Метаописание базы данных.

3.1.2. Описание знаний проблемной среды.

3.2. Базовые механизмы проблемного анализа.

3.2.1. Метод построения преобразования ^з.

3.2.1.1. Построение транзитивных замыканий.

3.2.1.2. Описание системы продукций.

3.2.1.3. Преобразование графа зависимостей терминов логической модели в граф зависимостей терминов физической модели - преобразование

3.3. Формирование SQL-запроса или построение преобразования Ч>4.

3.3.1. Продукции по формированию SQL-запроса.

3.3.2. Алгоритм доказательства гипотез.

3.3.3. Формирование оператора SQL.

3.4. Выводы по третьей главе.

Актуальность темы диссертационного исследования. Задача , интеллектуальной обработки текстов на естественном языке впервые появилась на рубеже 60-х—70-х гг.ХХ в. Работы последних лет связаны с решением проблемы анализа смысла языка в приложении к созданию систем диалога с программным обеспечением. Подходов к решению задачи понимания естественно-языковых запросов несколько. Наиболее распространенными являются подходы, основанные на синтаксическом, семантическом анализах и шаблонах. Первый подход основан на использовании синтаксических конструкций. Синтаксическое представление запроса строится на основе подлежащего, сказуемого, прямого дополнения и т.п., которые определяются с помощью морфологических характеристик (часть речи, род, падеж, лицо и т.д.). Это представление ничего не говорит о смысле запроса.

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

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

К настоящему времени существующие естественно-языковые системы используют в основном два последних подхода. Второй подход реализован в достаточно распространенной системе ЗАПСИБ, разработанной в середине 80-х годов [78]. Система позволяет вести общение на ограниченном подмножестве естественного языка. Развитием проекта является система InterBase, вышедшая в 1990 году [128]. Система основана на семантически-ориентированном анализе и продолжает ряд естественно-языковых технологий лаборатории искусственного интеллекта ВЦ АН Новосибирска, затем фирмы «Интеллектуальные технологии», а теперь РосНИИ искусственного интеллекта. В 2001 году эта система была переработана и получила название InBASE в виде коммерческого продукта. В настоящее время система представляет собой библиотеку СОМ-компонентов и- среду настройки естественно-языковых интерфейсов. Существенным отличием от старой версии является появление промежуточного уровня запросов — Q-языка, являющегося подмножеством языка объектных запросов OQL, и уровня описания предметной области в виде диаграммы классов UML. В полном соответствии с особенностями семантически-ориентированной парадигмы InBASE позволяет строить естественно-языковые интерфейсы ко многим языкам —для русского и для английского используется один и тот же JI-процессор. Интересной особенностью InBASE является возможность моделирования предметной' области на естественном языке: с помощью класса словарных статей «Толкование» смысл слова можно описать простой фразой. Это позволяет настраивать естественно-языковые интерфейсы людям, не обладающим навыками инженеров знаний. Основным недостатком данной системы является то, что кортежи базы данных продублированы в словарях — отдельных файлах. В базах данных больших объемов этот недостаток может стать проблемой [34, 97, 115, 123, 126-127].

Ярким представителем третьего подходаявляется система English Query. Система English Query от Microsoft основана на синтаксически-ориентированных шаблонах, связываемых с моделью предметной области, и через нее - со схемой базы данных [107]. При настройке необходимо задать модель базы данных и предметной области, а затем для каждого отношения в базе данных (а отношением считается и связь между классом и его атрибутом, например, между товаром и его ценой) задать синтаксический шаблон английской грамматики, выбираемый из списка. Этот продукт позволяет строить естественно-языковые интерфейсы только для английского языка и работает только с Microsoft SQL Server, в этом; смысле это лишь утилита, поставляемая с SQL-сервером, именно так она и позиционируется. В целом же этот продукт очень интересен. Например, в нем есть встроенная обучаемая. база знаний, с которой можно пообщаться на английском : языке, — она запоминает факты, правила и отвечает на вопросы по этой базе. К сожалению, эта замечательная способность не совмещена с пониманием запросов к базе данных.

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

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

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

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

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

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

2) разработка лингвистической модели транслятора;

3) разработка интерпретационной модели задачи;

4) разработка подхода к семантическому и проблемному анализам естественноI языкового запроса;

5) разработка методов трансляции естественно-языковых запросов к базе данных, представленных в виде простых предложений русского языка, в SQL-запросы.

Объектом исследования является естественно-языковой запрос к базе данных в виде простого предложения.

Предмет исследования - преобразование запроса на естественном языке в SQL-запрос.

Методологической и теоретической основой исследования послужил математический аппарат теории искусственного интеллекта, множеств, графов, математической логики и лингвистики. Достоверность научных выводов и практических рекомендаций основывается на теоретических и методологических положениях, сформулированных в исследованиях зарубежных и российских ученых: Д.А. Поспелова, Э.В. Попова, Г.Г. Белоногова, Е.С. Кузина, Р.Г. Пиотровского, A.C. Нариньяни, Т. Винограда, М. В. Никитина, О. Н. Селиверстовой, А. И. Смирницкого, Ю.А. Загорулько, J1.A. Голубевой, В.Е. Дмитриева, Ф.Г. Диненберга, Е.Ю. Кандрашиной, И.С. Кононенко, Д.Я. Левина, B.C. Маркина, Т.В. Нестеренко, О.Н. Очаковской, В.В. Телермана, С.П. Трапезникова, В.Ф. Хорошевского, И.Е. Швецова, Т.М. Яхно, Р. Ковальского, Д. Лавленда, Д. Кюнера и других [21-29,49,59, 55, 64, 68, 80, 85-86,114,107].

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

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

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

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

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

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

Апробация результатов- исследования. Основные положения диссертационной работы докладывались и обсуждались на международной научно-технической конференции "Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и СИИ" (Вологда, 2001 г.), III Международной выставки-конференции "Информационные технологии и телекоммуникации в образовании" (Москва, 2001 г.), VI и VII Всероссийской конференции по проблемам информатизации региона ПИР (Красноярск, 2000 и 2001 гг.), первой, третьей, четвертой и пятой конференциях «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2000-2004 гг.), внуривузовской научной конференции преподавателей, научных работников и аспирантов ВСГТУ (Улан-Удэ, 2000-2004 гг.), межкафедральном семинаре «Концепции и методологии создания, современных информационных систем» (Сиб1 ТУ, Красноярск, 22 сентября 2004 г.). Ряд положений диссертации был использован при подготовке учебного курса «Естественно-языковые системы» по специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем» и нашел применение в учебном процессе ВСГТУ. По теме диссертации опубликовано 8 печатных работ общим объемом более 24 пл.

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

3.4. Выводы по третьей главе

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

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

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

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

Все частичные функции, представленные в виде вычислительных процедур, составляют библиотеку ассоциированных процедур К третьего элемента системы общения с базами данных 2 = <М, В, К>.

Заключение

В диссертационной работе разработаны методы и алгоритмы, позволяющие осуществлять трансляцию естественно-языкового запроса к структурированному источнику в БС^Ь-запросы. Основные результаты работы заключаются в следующем:

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

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

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

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

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

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

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

1. Андреев A.M., Березкин Д.В., Брик A.B. Лингвистический процессор для ИПС // Компьютерная хроника. -1998.- №11. - С. 79-100.

2. Андреева A.M., Березкин Д.В., Смирнов A.M. Об одном способе построения синтаксического анализатора текстов на естественном языке. // Изв. Вузов // Приборостроение. 1977.- Т. 40.- №5. - С. 34-42.

3. Апресян Ю.Д., Богуславский И.М., Иомдин JI.JL и др. Лингвистический процессор для сложных информационных систем. -М.: Наука, 1992. 256 с.

4. Апресян Ю.Д., Богуславский И.М., Иомдин Л.Л. и др. Лингвистическое обеспечение системы Этап-2. -М.: Наука, 1989.

5. Артемьева И.Л., Гаврилова Т.Л., КлещевА.С. Логические модели второго порядка для предметных областей // НТИ. Сер.2. 1997. № 6.- С. 14 30.

6. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. Синтаксический анализ.- М.: Мир, 1978. 612 с.

7. Бадд Т. Объектно-ориентированное программирование в действии.- СПб.: Питер, 1997.

8. Белоногов F. Г., Котов Р. Г. Автоматические информационно-поисковые системы. -М.: Сов. радио, 1968.- 415 с.

9. Белоногов Г.Г. , Кузнецов Б.А. Языковые средства автоматизированных информационных систем. М.: Наука, 1983.- 380 с.

10. Вениаминов Е.М. Основания категорного подхода к представлению знаний. Категорные средства // Изв. АН СССР. Техн. Кибернетика. N 2.- 1988. - 242 с.

11. И. Вениаминов Е.М., Болдина Д.М. Система представления знаний Ontolingua -принципы и перспективы // НТИ. Сер.2. 1999. № 10.

12. Вениаминов Е.М., Манушина М.Ю. Принципы построения открытого языка шаблонных выражений в системе представления знаний // НТИ. Сер.2. 2000. № 7.

13. Бидер И. Г., Большаков И. А., Еськова Н. А. Формальная модель русской морфологии. Ч. 1-2. М.: Изд-во ИРЯ, Вып. 111-112, 1978.

14. Богданов С. И. Форма слова и морфологическая форма .- СПб.: Изд-во С.-Петерб. ун-та, 1997.-204 с.15. www.gramma.ru сайт по русской грамматике.

15. Богуславский И.М., Цинман Л.Л. Семантический компонент лингвистическогопроцессора // Семиотика и информатика 32: 1990 5-30 с.

16. Большая советская энциклопедия, http://encycl.yandex.ru/cgi-bin/

17. Бондаренко М.Ф., Осыка А.Ф. Автоматическая обработка информации на естественном языке. Киев: УМК ВО, 1991. - 140 с.

18. Брябин В.М., Любарский Ю.Я., Микулич Л.И. и др. Диалоговые системы в АСУ // Под ред. Д.А. Поспелова. М.: Энергоатомиздат, 1983. - С. 85-120.

19. В. Липский. Комбинаторика для программистов. Москва — Мир, 1988.

20. Виноград Т. К процессуальному пониманию семантики // Новое в зарубежной лингвистике.-М., 1983. Вып. XII.

21. Виноград Т. Программа, понимающая естественный язык.- М., 1976.

22. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем,- СПб.: Питер, 2000. 573 с.

23. Гаврилова Т.А., Червинская K.P. Извлечение и структурирование знаний для экспертных систем.- М.: Радио и связь, 1992.- С. 62.

24. Гладкий A.B. Формальные грамматики и языки. М., 1973. - 368 с.

25. Голдблатт Р. Топосы. Категорный анализ логики. М.: Мир 1983. 361с.

26. Голубева Л. А., Алсынбаева Л. Г., Москвина Л. А. Введение в компьютерное моделирование //Программные системы.- Новосибирск, 1996.- С. 53-63.

27. Грамматика русского языка. М., 1954,1960. - Т. 2, ч. 1 - 2.

28. Диненберг Ф.Г., Загорулько Ю.А., Жигалов М.А., Левин Д.Я., Попов И.Г. Разработка системы речевого взаимодействия с интеллектуальным роботом // Тр. междунар. семинара Диалог'98 по компьютерной лингвистике и ее приложениям. -Казань, 1998. С.781-794.

29. Диненберг Ф.Г., Кучин С.И., Трапезников С.П. INTERBASE система конструирования ЕЯ-интерфейса к dBASE III PLUS// Искусственный интеллеюг-90: Тр.12-й Всесоюзной конференции: секционные и стендовые доклады. - Минск, 1990. - Т.2. - С. 161-163.

30. Дударь З.В;, Шуклин Д.Е. Семантическая нейронная сеть как формальный язык описания и обработки смысла текстов на естественном языке // Радиоэлектроника и информатика. Харьков: Изд-во ХТУРЭ, 2000.- №3.- С. 72-76.

31. Евдокимова И.С. Модель представления знаний синтаксического анализатора: Материалы Всерос. конф. // Теоретические и прикладные вопросы современных информационных технологий,- Улан-Удэ, 2001.- С. 206-211.

32. Жигалов В.А. Естественное общение с приложением // Открытые системы. 2001. №12.

33. Жигалов В.А., Соколова Е.Г. InBASE: технология построения ЕЯ интерфейсов к базам данных // Тр. междунар. семинара Диалог'2001 по компьютерной лингвистике. Т. 2.-Аксаково, 2000,- С. 123-135.

34. Жигирев H.H., Корж В.В., Оныкий Б.Н. Самонастраивающийся словарь ключевых слов и нейронная сеть Хопфилда для классификации текстов // Тр. 2-й Всерос. науч.-тех. конф. "Нейроинформатика-2000". Ч. 2. -М., 2000. С.58-61.

35. Загорулько Ю.А., Попов И.Г. Подход к разработке языка представления знаний, использующего динамическое множество ограничений // Распределенная обработка информации: Тр. VII междунар. семинара. Новосибирск, 1998. — С.323-327.

36. Замулин М.А. Системы программирования баз данных и знаний. Новосибирск: Наука, 1990.-352 с.

37. Золотов Е.В., Кузнецов И.П. Расширенные системы активного диалога. М.: Наука, 1982.

38. Искусственный интеллект: В 3 кн. Кн.1. Системы общения и экспертные системы: Справочник / Под ред. Э.В. Попова. — М.: Радио и связь, 1990. 464 с.

39. Искусственный интеллект: В 3 кн. Кн.2. Модели и методы: Справочник /Под ред. Д.А.Поспелова. М.: Наука, 1990. - 472 с.

40. Искусственный интеллект: Применение в интегрированных производственных системах / Под ред. А.И. Дашенко, Е.В. Левнера. М.: Машиностроение, 1991. — 539 с.

41. Исследования по семантике: Межвуз. научный сборник / Отв. ред. JI.M. Васильев / Башкирск. гос. ун-т. Уфа, 1975. - Вып. 1. - 179 с.

42. Исследования по семантике: Межвуз. научный сборник / Отв. ред. JI.M. Васильев / Башкирск. гос. ун-т. Уфа, 1976. - Вып. 2. - 145 с.

43. Исследования по семантике: Общие вопросы семантики / Отв. ред. JI.M. Васильев / Башкирск. гос. ун-т. Уфа, 1983. - Вып. 9. - 144 с.

44. Исследования по семантике: Семантика языковых единиц разных уровней / Отв. ред. P.M. Гайсина / Башкирск. гос. ун-т. Уфа, 1988. - Вып. 13. - 147 с.

45. Исследования по семантике: Семантические классы языковых единиц /Отв. ред. JI.M. Васильев / Башкирск. гос. ун-т. Уфа, 1980. - Вып. 5. - 111 с.47