29 декабря (суббота) в 11-00 в ауд. 779.
Экзаменационные
билеты
по курсу "Базы данных. Введение в теорию и методологию"
(для математических потоков 3-го и 4-го курсов ф-та ВМК МГУ)
Лектор:
доктор физ.-мат. наук А.С.Марков
Билет 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) Дистрибутивность операций реляционной алгебры.