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

ВВЕДЕНИЕ.

1. ИССЛЕДОВАНИЕ УСЛОВИЙ РЕАЛИЗАЦИИ СЕМАНТИЧЕСКОЙ МОДЕЛИ ДАННЫХ В АСУЖТ.

1Л. Проблемы и перспективы развития АСУЖТ.

1.2. Анализ требований к единой модели данных для АСУЖТ.

1.3. Анализ соответствия существующих моделей данных требованиям к единой модели для АСУЖТ.

1.4. Выводы.

2. СРЕДСТВА ОПИСАНИЯ ДАННЫХ В СЕМАНТИЧЕСКОЙ МОДЕЛИ.

2.1. Объекты и отношения на множестве объектов.

2.2. Описание фактов.

2.3. Описание правил.

2.4. Выводы.

3. ОБРАБОТКА ИНФОРМАЦИИ

В СЕМАНТИЧЕСКОЙ МОДЕЛИ ДАННЫХ.

3.1. Автоматическая классификация с целью сокращения связей между объектами.

3.2. Индуктивный вывод.

3.3. Поиск и разрешение противоречий.

3.4. Поиск информации.

3.5. Выводы.

4. АЛГОРИТМ АДАПТИВНОЙ СТРУКТУРИЗАЦИИ СЕМАНТИЧЕСКОЙ БАЗЫ ДАННЫХ.

4.1. Разработка алгоритма.

4.2. Оценка эффективности алгоритма.

4.3. Практическая реализация алгоритма.

АРМ АСОУП

АСУГС

АСУЖТ

АСУКП

АСУСС

СПИСОК СОКРАЩЕНИЙ.

Автоматическая классификация с целью сокращения числа связей.

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

Автоматизированная система железнодорожным транспортом. Автоматизированная система контейнерными перевозками. Автоматизированная система сортировочными станциями. База данных. База знаний. База фактов.

Главный вычислительный центр Министерства Министерство путей сообщения России. Естественный язык.

Информационно-вычислительный центр.

Система интегрированной обработки дорожной ведомости.

Система интегрированной обработки маршрута машиниста. управления управления управления

КИТ - Комплекс информационных технологий. ЛПР - Лицо принимающее решения. МПС - Министерство путей сообщения России. НП - Неполный поиск данных. ОС - Операционная система. ПК - Персональный компьютер. ПО - Программное обеспечение. ПП - Полный поиск данных.

РГУПС - Ростовский государственный университет путей сообщения. РП - Расширенный поиск данных. СКЖД - Северо-Кавказская железная дорога. СУБД - Система управления базами данных. УМО - Учебно-методический отдел. УН - Учебная нагрузка. УП - Учебный план.

ЭВМ - Электронно-вычислительная машина. ЯМД - Язык манипулирования данными. ЯОД - Язык описания данных.

API - Application Programming Interface (набор типов данных и подпрограмм, предназначенных для использования системных функций Windows в прикладных программах). QBE - Query Ву Examie (язык запросов по образцу). SQL - Structure Query Language (язык структурированных запросов).

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

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

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

Отсутствие единой модели данных в АСУЖТ в настоящее время объясняется тем, что ни одна из классических моделей данных не обладает выразительной мощностью, достаточной для полного охвата предметной области. В этом аспекте семантическая модель данных, наиболее полно учитывающая специфику железнодорожного транспорта, может в перспективе претендовать на роль единой модели.

В существующих семантических БД отсутствуют специальные средства формирования динамической модели предметной области, что не позволяет эффективно использовать их в наиболее важных подсистемах АСУЖТ, например, в системах управления перевозочным процессом.

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

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

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

- определить и исследовать средства описания данных семантической модели (средства выразительной мощности);

- исследовать алгоритмы поиска данных в семантической БД;

- определить структурообразующие свойства семантической БД, позволяющие повысить производительность поиска данных;

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

- разработать методику разрешения противоречий с учетом оценок достоверности источников информации.

Методы исследования. Для решения поставленных задач использовались теория множеств, теория решеток, теория баз данных, теория графов, теория семантических сетей, исчисление высказываний, методы объектно-ориентированного и процедурного программирования. Основополагающее влияние на исследования автора оказали работы Поспелова Д.А., Нариньяни A.C., Цаленко М.Ш., Замулина A.B., Вагина В.Н., Фурсина Г.И., Головко A.B., Осипова Г.С., Горбатова В.А., Шенка Р., Цикритзиса Д., Шуберта JL, Сандевалля Э., Рубашкина В. Ш., Лахути Л.Г., Новикова А.И., Микони C.B., Финна В.К., Тулупова Л.П., Ратина Г.С.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Основное содержание диссертации изложено на 192 страницах (основного текста - 177 страниц), содержит 7 рисунков и 8 таблиц. Список литературы содержит 106 наименования библиографических источников.

Основные результаты работы заключаются в следующем:

1. Исследованы средства выразительной мощности и алгоритмы обработки данных в семантической модели.

2. Разработана семантическая модель данных, характеризующаяся наличием средств формирования динамической модели предметной области и высокой эффективностью поисковых операций, что позволяет использовать ее в большинстве подсистем АСУЖТ.

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

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

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

6. Разработан и реализован алгоритм адаптивной структуризации БД, позволяющий повысить эффективность поиска в среднем в 1,7 раза.

7. Разработан и внедрен АРМ Контрольно-ревизионной службы СКЖД.

ЗАКЛЮЧЕНИЕ

1.Н. Спецификация программ: понятийные средства и их организация. - 2-е изд. - Новосибирск: Наука, 1990. - 280 с.

2. Александров В.В. Инфраструктура, информационные системы, базы данных и знаний // Системы баз данных и знаний. Докл. IV Всесоюзн. конф. Калинин: НПО "Центрпрограммсистем", 1990.

3. Анализ программного обеспечения банков данных: Методические рекомендации. Калинин: НПО "Центрпрограммсистем", 1985. - 98 с.

4. Атре Ш. Структурный подход к организации баз данных. М.: Финансы и статистика, 1983.

5. Бакаев A.A. Методы организации и обработки баз знаний. Киев: Институт кибернетики им. Глушкова, 1993.

6. Басараб И.А., Редько В.Н. Базы данных с логико-функциональной точки зрения // Программирование, 1984. №2.

7. Биргкоф Г. Теория решеток. М.: Наука, 1984.

8. Брудно В.А., Скворцов Д.П., Финн В.К., Цаленко М.Ш. Базы данных с неполной информацией // Семиотика и информатика. М.: ВИНИТИ, 1985. - Вып. 25.

9. Бургин М.С., Кузнецов В.И. Системная организация баз данных и баз знаний. Киев: Наукова думка, 1991.

10. Вагин В. Н. Дедукция и обобщение в системах принятия решений. -М.: Наука, 1988.

11. Вагин В.Н., Викторова Н.П. Задачи обобщения в системах принятия решений: формирование классов объектов и отношений выбора на семантических сетях // Известия АН СССР, Техническая кибернетика. М.: Наука, 1985. №5.

12. Вагин В.Н., Головко A.B. Дедуктивные базы данных в системах управления // Известия АН СССР, Техническая кибернетика. М.:1. Наука, 1987. №2.

13. Вагин В.Н., Кикнадзе В.Г. Дедуктивный вывод на семантических сетях в системах принятия решений // Известия АН СССР, Техническая кибернетика. М.: Наука, 1984. №5.

14. Ващенко Н.Д. Формирование понятий в семантической сети // Кибернетика. №2, 1983.

15. Виноградов М.М. Модели данных и отображения моделей данных: алгебраический подход // Теория и приложения систем баз данных. -М.: ЦЭМИ, 1984.

16. Вудс У.А. Основные проблемы представления знаний // ТИИЭР, Т. 74, №10, 1986.

17. Головко A.B. Рекурсивные аксиомы в дедуктивных базах данных // Известия АН СССР, Техническая кибернетика. М.: Наука, 1985. №5.

18. Голышев JI.K. Проблема идентификации и формализации представления автоматизируемых функций управления в сложных системах социально-экономического типа // УСиМ. №3. - Киев, 1994.

19. Горбатов В.А. Основы дискретной математики. Москва. Высшая школа, 1986. - 311 с.

20. Гордиенко Е.К., Захаров В.Н. Управление процессами в базах знаний // Известия АН СССР, Техническая кибернетика. М.: Наука, 1985. №5.

21. Гордиенко Е.К., Захаров В.Н., Кириллов В.Ю., Миронов А.Ю. Полнота и эффективность навигационных операций в децентрализованных интеллектуальных системах // Известия АН СССР, Техническая кибернетика. М.: Наука, 1990. №5.

22. Гуда А.Н. Математическое моделирование сложных технологических процессов железнодорожного транспорта. Ростов-на-Дону: РГУ, 1995.

23. Гуда А.Н. Методы анализа данных и принятия решений в затрудненных условиях. Ростов-на-Дону: СКНЦВШ, 1997.

24. Дейт К. Введение в системы баз данных. Москва: Наука, 1980. - 468 с.

25. Дрибас A.B., Столяров Г.К. Факторы оценки и выбора СУБД. Минск, 1978.

26. Дрибас В.П. Реляционные модели баз данных. Минск.: БГУ, 1982.

27. Евдокимов С.А., Рыбаков A.B. Программно-компьютерная среда для автоформализации знаний // Вестник машиностроения. №7, 1990.

28. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985. - 351 с.

29. Ерема-Еременко A.A., Михновский С.Д., Информационная модель для формирования описания предметной области проектируемой базы данных // УСиМ. -1982.-№5.

30. Ефимова С.М. Представление схемы сетевой базы данных в виде системы специальных линейных уравнений // Известия АН СССР, Техническая кибернетика. М.: Наука, 1986. №5.

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

32. Ивахненко А.Г., Ивахненко JI.H. Индуктивные (переборные) системы искусственного интеллекта // Всес. Конференция по искусственному интеллекту. Том 2. Переславль-Залесский, 1988.

33. Инфанов А.П., Осипов Г.С. Язык байсл для представления знаний // Известия АН СССР, Техническая кибернетика. М.: Наука, 1986. №5.

34. Информационная система для управления перевозочным процессом / Под ред. Г.С. Ратина. М.: Транспорт, 1989.

35. Искусственный интеллект: Справочник. М.: Радио и связь, 1990.

36. Калиниченко Л.А., Рыбкин В.М. Машины баз данных и знаний. М.: Наука, 1990

37. Кандрашина Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах / Под ред. Д.А. Поспелова. Москва: Наука. Гл. ред. физ-мат. лит., 1989. -328 с.

38. Кобзарева Т.Ю., Лахути Л.Г. О стуктуре денотативного значения предлогов // Семантическая структура слова. М. : Наука, 1971.

39. Когаловский М.Р. Проблемы терминологии в теории систем баз данных // Управляющие системы и машины. Киев: Наукова думка, 1986. №6.

40. Космынин А.Н. Система хранения иерархических и сетевых структур данных для ПЭВМ // Практика применения баз данных. Пенза: ПДНТП, 1989.

41. Крамаренко Р.П., Долинный О.Б. Расширение возможностей СУБД по обеспечению семантической целостности баз данных // УСиМ. 1987. -№1.

42. Лакофф Дж. Мышление в зеркале классификаторов // Новое в зарубежной лингвистике.- Вып. 23. М.: Прогресс, 1988.

43. Лахути Д.Г., Рубашкин В.Ш. Средства и процедуры концептуальной интерпретации входных сообщений на естественном языке // Известия АН СССР, Техническая кибернетика. М.: Наука, 1987. №2.

44. Лисицын A.A. Многоуровневая обработка данных в интеллектуальных системах // Сб. тез. к докл. СПб. 1995.

45. Логический подход к искусственному интеллекту: от классической логики к логическому программированию: Пер.с франц./ Тейз А., Грибомон П., Луи Ж. И др. Москва: Мир, 1990 - 432 с.

46. Лябах H.H. Математические основы разработки и использования машинного интеллекта. Ростов-на-Дону, 1990.

47. Мартин Дж. Организация баз данных в вычислительных системах. -М.: Мир, 1980. 662 с.

48. Маслов С.Ю. Теория дедуктивных систем и ее применения. М.: Радио и связь, 1986. - 133 с.

49. Микони C.B. Генерация понятий предметной области // Сб. науч. Тр., "Проблемы обработки знаний" Ленинград: Наука, 1989.

50. Микони C.B. Общие диагностические базы знаний вычислительных систем. СПб.: СПИИРАН, 1992. 234 с.

51. Моделирование языковой деятельности в интеллектуальных системах / Под ред. А.Е. Кибрика, A.C. Нариньяни. М.: Наука, 1987.- 280 с.

52. Нариньяни A.C. Недоопределенность в системе представления и обработки знаний // Известия АН СССР, Техническая кибернетика. М.: Наука, 1986. №5.

53. Новиков А.И. Семантика текста и ее формализация. М.: Наука, 1983. -215 с.

54. Овчаров Л.А., Селетков С.Н., Автоматизированые банки данных. М.: Финансы и статистика, 1981.

55. Олле Т.В. Предложения КОДАСИЛ по управлению базами данных. -М.: Финансы и статистика, 1984.

56. Ольховик О.В. К вопросу о разрешении противоречий в семантических сетях. Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении: Материалы отраслевой научно-технической конференции. Ростов-на-Дону. РГУПС, 1998.

57. Ольховик О.В. К вопросу об отношениях между объектами в семантических сетях. Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении: Материалы отраслевой научно-технической конференции. Ростов-на-Дону. РГУПС, 1998.

58. Ольховик О.В. К вопросу о реализации сверхбыстродействующих баз данных и знаний. Материалы ежегодной научно-практической конференции. Ростов-на-Дону. РГУПС, 1998.

59. Ольховик О.В. Анализ высказываний на основе параллельности классов. Материалы 58-й научной конференции профессорско-преподавательского состава РГУПС. РГУПС, Ростов-на-Дону, 1999.

60. Ольховик О.В. Исследование семантики отношения IS-A. Материалы58.й научной конференции профессорско-преподавательского состава РГУПС. РГУПС, Ростов-на-Дону, 1999.

61. Осипов Г.С. Метод формирования и структурирования модели знаний для одного типа предметных областей // Известия АН СССР, Техническая кибернетика. М.: Наука, 1988. №2.

62. Осипов Г.С. Построение моделей предметных областей. Ч. 1. Неоднородные семантические сети // Известия АН СССР, Техническая кибернетика. М.: Наука, 1990. №5.

63. Осуга С. Обработка знаний: Пер. с япон. Москва: Мир, 1989. - 293 с.

64. Падучева Е.В. высказывание и его соотнесенность с действительностью. М.: Наука, 1985. - 271 с.

65. Плесневич Г.С. Концептуальные языки и модели данных // Известия АН СССР, Техническая кибернетика. М.: Наука, 1984. №5.

66. Поддавашкин Э.С., Кутыркин A.B., Шевцов В.Б. Концепция информатизации железнодорожного транспорта // Железнодорожный транспорт. №6, 1996.

67. Попов Э.В. Экспертные системы. Решение неформальных задач в диалоге с ЭВМ. М.: Наука, 1987.

68. Поспелов Д.А. Логико-лингвистические модели в системах управления. Москва: Энергоиздат, 1981. - 231с.

69. Поспелов Д.А. Ситуационное управление. Теория и практика. М.: Наука, 1986.

70. Представление и использование знаний: Пер. с япон. / Под ред. X. Уэно, М. Исидзука. Москва: Мир, 1989. - 220 с.

71. Приобретение знаний: Пер. с япон. / Под ред. С. Осуги, Ю. Саэки. -Москва: Мир, 1990. 304 с.

72. Проблемы сокращения перебора / Под ред. Поспелова Д.А. М.: Наука, 1987.

73. Раскина A.A., Сидоров И.С., Шрейдер Ю.А. Семантические основанияобъектно-признаковых языков // НТИ. Сер. 2, 1976. №5.

74. Рубашкин В. Ш. Представление и анализ смысла в интеллектуальных информационных системах. Москва: Наука. Гл. ред. физ-мат. лит., 1989. - 192 с.

75. Самедова М.А. Информационный поиск как задача лингвистического распознавания образов // Программирование. М.: Наука, 1981. №5.

76. Сандевалль Э. Правила немонотонного вывода для случая множественного наследования информации с наличием исключений // Представление знаний. Тематический выпуск. М.: Мир, 1987.

77. Санников В.З. Семантика и прогматика союза ИЛИ // Семиотика и информатика,- Вып. 24. М.: ВИНИТИ, 1985.

78. Системы управления базами данных и знаний: Справ, изд./ А.Н.Наумов, A.M. Вендров, В.К. Иванов и др.; Под ред. А.Н. Наумова.- Москва: Финансы и статистика, 1991. 352 с.

79. Скороходько Э.В. Семантические сети и автоматическая обработка текста. Киев: Наукова думка, 1983.

80. Смит Дж., Смит Д. Принципы концептуального проектирования баз данных // Требования к спецификации и разработке программ: Сб. статей. М.: Мир. 1984.

81. Сотников Е.А., Ратин Г.С. Опыт развития автоматизированных систем управления на дорогах сети. М.: Транспорт, 1987.

82. Триори Т., Фрай Дж. Проектирование структур баз данных. М.: Мир, 1985.

83. Тулупов Л.П., Жуковский Е.М., Гусятинер A.M. Автоматизированные системы управления перевозочными процессами на железных дорогах.- М.: Транспорт, 1991.

84. Тулупов Л.П., Шапкин А.Н. АСУ железнодорожного транспорта. М.: Знание, 1988.

85. Ульяницкий Е.М., Ольховик О.В. Проблемы автоматизации системного анализа. Экономико-организационные проблемы анализа,проектирования и применения информационных систем: Материалы межгосударственной научной конференции. Ростов-на-Дону. РГЭА, 1997.

86. Ульяницкий Е.М., Ольховик О.В. Об одном способе преставления высказываний в семантической сети. Вестник РГУПС. №1. РГУПС, Ростов-на-Дону, 2000.

87. Филиппов В.И. Реляционно-сетевая модель данных // Прикладная информатика. М.: Финансы и статистика, 1983. - Вып. 1.

88. Филиппов В.И. Теоретико-множественное обоснование модели данных // Тр. 3-й Всесоюзн. конф. по банкам данных. Таллинн, 1985.

89. Финн В.К. Логические проблемы информационного поиска. М.: ВИНИТИ, 1976.

90. Финн В.К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф. Бэкона Д. С. Милля // Семиотика и информатика. М.: ВИНИТИ, 1985. - Вып. 25.

91. Фурсин Г.И. На пути к созданию семантических моделей данных нового поколения // Развитие теории и методов создания систем управления базами данных: II междунар. науч.- техн. конф. "Программное обеспечение ЭВМ". Калинин, 1987.

92. Фурсин Г.И., Кабаков Ю.Б., Модель данных КОМОД // Управляющие системы и машины. Киев: Наукова думка, 1986. №4.

93. Хайтер П.А. Интеллектуальные информационные системы. Ростов-на-Дону: РГЭА, 1996.

94. Цаленко М.Ш. Моделирование семантики в базах данных. Москва: Наука. Гл. ред. физ-мат. лит., 1989. - 288 с.

95. Цаленко М.Ш. Семантические и математические модели баз данных // Итоги науки и техники. Информатика. Москва: ВИНИТИ, 1985. - Т.9.

96. Цаленко М.Ш., Янко Т.Е. Общение с банком данных на естественном языке // Вопросы информационной технологии: Сборник трудов. М.: ВНИИСИ, 1986. -Вып.2.192

97. Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика. - 1985. - 344 с.

98. Чесноков C.B. Силлогизмы в детерминационном исчеслении // Известия АН СССР, Техническая кибернетика. М.: Наука, 1984. №5.

99. Четвериков В.Н., Ревунков Г.И., Самохвалов Э.Н. Базы и банки данных. М.: Высшая школа, 1987.

100. Шамир А., Уэйдж У. Типы данных как объекты // Данные в языках программирования. М.: Мир, 1982.

101. Шенк Р. Обработка концептуальной информации. М.: Энергия, 1980. - 360 с.

102. Шрейбер Б.Т. Организация поиска и обработки данных на основе системы УНИСОН. М.: Энергоатомиздат, 1986. - 224 с.

103. Шуберт Л. Усиление выразительной мощности семантических сетей // Кибернетический сборник. Новая серия. Вып. 16. - М.: Мир, 1979.

104. Язык описания данных КОДАСИЛ: М.: Статистика, 1981.

105. Gregoire Е. Raisonnement plausible: inference non monotone et logiques autoepistemiques, Proc. Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Paris, pp. 376379, julliet 1986.

106. Roussopoulos N.D. A Semantic Network Model of Data Bases. Toronto, 1977.

107. Министерство путей сообщения ' Утверждаю

108. Российской Федерации . " Начальни'кИвЦ СКЖД

109. Начальник отдела Разработки прикладных программ ИВЦ СКЖД

110. Подпись Ганашека Л.А. уд Начальник отдела кадров1. Ганашек Л.А.1. Ганжа Л.Б.