Экзаменационные билеты 
по курсу "Базы данных. Введение в теорию и методологию"
(для 1-го потока 3-го курса вечернего с./отд. ф-та ВМК МГУ) 





Лектор: 
доктор физ.-мат. наук А.С.Марков 

Билет 1
1) Понятие о базах данных и о системах управления базами данных. Базовые уровни представления БД (логический, концептуальный, физический).
2) Порядок в домене. Частичный порядок. Полный порядок.

Билет 2
1) Понятие о модели данных. Множественность моделей. Типы моделей.
2) Нормальные формы (НФ) реляционных баз данных: НФ1, НФ2.

Билет 3
1) Индексирование таблиц. Время поиска как функция от размера таблиц.
2) Нормальные формы (НФ) реляционных баз данных: НФ3, НФ3БК.

Билет 4
1) Применение функций расстановки ("хэширование").
2) Нормальные формы (НФ) реляционных баз данных: НФ4.

Билет 5
1) Понятие о транзакции, о программо-независимости, целостности и защищенности данных. Оператор GRANT в SQL.
2) Нормальные формы (НФ) реляционных баз данных: НФ5.

Билет 6
1) Сопоставление понятий файл, набор данных, запись, отношение, таблица, домен, столбец, строка, атрибут, поле, ключ в соответственных контекстах.
2) Принцип дедукции.

Билет 7
1) Алгоритмы поиска и время поиска как функция от размера таблиц.
2) Хорновские дизъюнкты.

Билет 8
1) Аксиомы Армстронга.
2) Реляционные таблицы. Операция Set relation над таблицами.

Билет 9
1) Рекурсивно-перечислимые отношения, частично рекурсивные функции (в терминах канонических систем Поста).
2) Принцип резолюции.

Билет 10
1) Отношение в терминах теории множеств. Понятие о решетке. Понятие о полных решетках.
2) Принципы реляционности СУБД Кодда.

Билет 11
1) Вложенные SELECT в SQL.
2) Реляционная алгебра: объединение, разность, пересечение отношений.

Билет 12
1) Расширенное декартово произведение отношений.
2) Выразить на SQL запрос: "имена поставщиков красных деталей".

Билет 13
1) Реляционная алгебра: проекция и селекция отношения.
2) Выразить на SQL запрос: "имена поставщиков всех деталей".

Билет 14
1) Представление о теореме Кодда о редукции.
2) Теорема о существовании неразрешимых рекурсивно перечислимых отношений.

Билет 15
1) Рекурсивно-перечислимые отношения (в терминах канонических систем Поста) в сопоставлении с понятием об отношении в теоретико-множественных терминах.
2) Понятие о схеме базы данных.

Билет 16
1) Понятие об универсальном отношении, связь с машинами Тьюринга.
2) Выразить в реляционной алгебре запрос: "имена поставщиков красных деталей".

Билет 17
1) Представление об отношении геделизации.
2) Реляционная алгебра: соединение (Join) отношений. Связь с 5НФ.

Билет 18
1) Понятие о реляционной полноте языков РБД.
2) Выразить в реляционной алгебре запрос: "имена поставщиков всех деталей".

Билет 19
1) Понятие о логическом выводе из гипотез, логические следствия.
2) Понятие о реляционной полноте реляционной алгебры.

Билет 20
1) Рекурсивно-перечислимые отношения, связь с формальными грамматиками.
2) Порядок в домене. Совершенный порядок.

Билет 21
1) Метод Якоби решения систем реляционных уравнений.
2) Порядок в домене. Полный порядок.

Билет 22
1) Основные черты языка реляционных данных QBE.
2) Реляционная алгебра: операция деления отношений.

Билет 23
1) Понятия о полноте в исчислениях, алгебрах, порядках, решетках.
2) Взгляды как виртуальные таблицы.

Билет 24
1) Монотонные преобразования на полных решетках.
2) Выразить на SQL запрос: "имена поставщиков красных и только красных деталей".

Билет 25
1) Теорема о неподвижной точке на полных решетках.
2) Выразить на SQL запрос: "имена поставщиков всех красных деталей".

Билет 26
1) Условия сходимости итерационных методов решения систем реляционных уравнений.
2) Понятие о модели данных.

Билет 27
1) Полные декомпозиции отношений. Связь с понятием о 5НФ.
2) Булевы алгебры и алгебра логики как частные случаи решеток.

Билет 28
1) Алгоритм резолюций.
2) Выразить в реляционной алгебре запрос: "имена поставщиков красных деталей".

Билет 29
1) Понятие об исчислении предикатов первой ступени как о математической модели реляционных баз данных.
2) Наименьшая неподвижная точка в полной решетке.

Билет 30
1) Сопоставление семантики Пролога с семантикой Дейталога.
2) Дистрибутивность операций реляционной алгебры.