Функциональные и логические методы обработки слабоструктурированной информации

(см. источник от 2004 г.)

Общие сведения о спецкурсе

Лектор — Д. А. Лизоркин.

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

Изучаются методы функционального программирования на языке Scheme применительно к задачам обработки слабоструктурированных данных. Язык XML рассматривается как синтаксис для текстового представления S-выражений, алгоритмы обработки таких данных могут быть реализованы на языке Scheme просто и наглядно. Изучаются и исследуются реализации промышленных стандартов (XPath, XSLT, DOM, DSSSL), а также академических разработок (DataGuide).

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

Особое внимание уделяется практическому применению исследуeмых технологий в информационных системах Internet/intranet.

Программа спецкурса

• Лямбда-исчисление.
  • Синтаксис и семантика.
  • Свободные и связанные переменные.
  • Редукция и нормальные формы.
  • Рекурсия и неподвижная точка.
• Язык Scheme.
  • Авторекурсия и передача продолжений.
  • Присваивание и побочные эффекты.
  • Отложенные вычисления.
  • Объектные расширения.
• Язык Дейталог.
  • Синтаксис и семантика.
  • Итерация наименьшей неподвижной точки.
• Слабоструктурированные данные.
  • XML и инфраструктура.
  • Схема — описывающая и предписывающая.
  • DTD, XML Schema, Relax NG и DataGuide.
  • XML и S-выражения. XML Information Set.
  • Реализация XML-инфраструктуры на Scheme.
  • XSLT и рекурсивная обработка деревьев.
  • Использование Дейталог-программ для представления частично структурированной информации.
  • Дейталог как язык запросов.

Основная литература

• А. Филд, П. Харрисон. Функциональное программирование. — М., Мир, 1993.
• Г. Гарсиа-Молина, Д. Д. Ульман и Д. Уидом. Системы Баз Данных. Полный курс. — М., Вильямс, 2003.
• С. Чери, Г. Готтлоб, Л. Танка. Логическое программирование и базы данных. — М., Мир, 1993.