Теория моделей и теория баз данных

Тверской государственный университет Утверждаю Декан факультета ПМиК ______________А.В.Язенин "___"_____________ 2003 г.

КАФЕДРА

ИНФОРМАТИКИ

Учебная программа Дисциплина: "Теория моделей и теория баз данных" Направление: Прикладная математика и информатика

Обсуждено на заседании кафедры "_____"_____________ 2003 г.

Заведующий кафедрой

Протокол N____

Автор

М.А. Тайцлин

М.А. Тайцлин

Т в е р ь 2003 г.

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

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

№ п/п

Содержание разделов и Тем

Часов лекций

Часов лабор. работ

Часов практ.

Часов контр.

Часов всего

2 2

2 6 6 12

1. Теория моделей 1.1 1.2 1.3 1.4

1.5 1.6 1.7 1.8

Ординалы и кардиналы Язык логики предикатов Элементарные подсистемы Ультрапроизведения. Теорема Лося. Теорема компактности Мальцева Универсальные, однородные и насыщенные системы Специальные системы. Существование специальных систем Теоремы Рамсея и Эренфойхта- Мостовского Псевдоконечные состояния

2 2 2 6

2 2

2 2 2

4

2

2

4

12

6

2

2

2

12

4 2

2 2

6 4

8

2. Полиномиальные запросы 2.1

Глобальные предикаты и стандартные структуры. Классификация глобальных предикатов. Полиномиальные по времени и по емкости глобальные предикаты.

2

2.2

Неподвижные точки. Логика неподвижных точек. Логика бесконечных выражений с конечным числом переменных.

6

2.3

Язык неявных определений.

2

2

2

2

10

2

4

3. Локально генерические запросы 3.1 3.2 3.3 3.4 3.5

3.6 3.7

Роль упорядочения в запросах Локально генерические запросы Критерий эквивалентности расширенного запроса ограниченному Достаточное условие эквивалентности расширенного запроса ограниченному для локально генерических запросов Трансляционные теоремы. Условия псевдоконечной однородности и изолированности. Примеры их применения. Квази-о-минимальные системы. Системы Семёнова. Элиминация кванторов в системах Семёнова. Трансляционная теорема для систем Семёнова Другие вопросы теории локально генерических запросов

2 2 2

2

4 2 2

2

2

2

2

4

6

2

8

6

18

6

6

2

4. 0-1 Закон 4.1

Определение асимптотической вероятности. Примеры свойств, для которых 0-1 закон не выполняется.

2

4.2

Вычисление асимптотической вероятности аксиом расширения.

2

2

4.3

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

2

2

4.4

Теорема о справедливости 0-1 закона.

2

2

4.5

Случайные системы и их теория. Изоморфность всяких двух счётных случайных систем одной сигнатуры. Полнота теории случайных систем. Разрешимость этой элементарной теории.

4

4.6

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

2

2

4.7

Теорема о неразрешимости логики предикатов на конечных структурах.

6

6

2

4

6

4.8

0-1 закон для фрагментов логики второго порядка.

2

2

4

4.9

Задание линейного порядка с помощью монадической формулы второго порядка. Ложность 0-1 закона для монадической теории второго порядка.

6

2

8

5. Логика бесконечных формул с конечным числом переменных 5.1

Определение. Теорема о вхождении логики неподвижных точек в эту логику. Теорема о формулах конечной кванторной глубины.

4

4

5.2

Игра Эренфойхта для этой логики. Теорема о выигрышной стратегии.

2

2

5.3

Теорема о формулах на упорядоченных структурах.

2

2

5.4

0-1 закон для этой логики.

2

2

5.5

Представление с одной бесконечной дизъюнкцией и одной бесконечной конъюнкцией.

2

2

4

8

6. Неявная определимость 6.1

Интерполяционная теорема Крейга. Явная определимость неявно определимых отношений на всех структурах заданной сигнатуры.

2

2

6.2

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

4

4

6.3

Жёсткие структуры. Естественный линейный порядок на жёстких структурах. Определимость этого линейного порядка.

2

2

6.4

Гиперграфы. Плотные множества вершин и бедные гиперграфы. Нечётные гиперграфы. Существование нечётных бедных гиперграфов с как угодно большим числом вершин.

8

8

6.5

Многоножки. Конечная аксиоматизируемость. Жёсткость.

2

2

6.6

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

4

4

6.7

Неявная определимость на многоножках линейного порядка формулой логики предикатов.

2

2

6.8

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

2

2

4. Литература 1. Тайцлин М.А. Языки запросов для баз данных. Тверь, 1998. 2. Kolaitis Ph.G. Implicit definability on finite structures and unambiguous computations. - In Proc 5th IEEE Symp.on Logic in Computer Science, pages 168-180, 1990. 3. Belegradek O.V., Stolboushkin A.P., Taitslin, M.A. Extended Order-Generic Queries. Annals of Pure and Applied Logic, 97(1): 85-125, 1999. 4. Кейслер Г., Чэн Ч.Ч. Теория моделей. Перевод с английского. Москва, «Мир», 1977. 5. Libkin L. Elements of finite model theory. Springer, 2004. 6. Gurevich Yu., Shelah S. On finite rigid structures.