![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Минимизация конъюнктивных запросов.
Последняя теорема может быть использована для определения конъюнктивного запроса с минимальным числом термов, эквивалентных данному запросу Свёртка как отображение термов. Термы запроса
g
Композиция двух свёрток также является свёрткой. Теорема: Для каждого конъюнктивного запроса Любой другой запрос Следствие: Для любого заданного конъюнктивного запроса Пример: Проверка того, что этот запрос минимален, трудная (NP-полная) задача, т.к. любое выражение РА, включающее Эта задача может быть решена при небольшом числе атомов. Параллельные операции с БД имеют место при обработке БД коллективного пользования. БД коллективного пользования делятся на два больших класса: - БД с распределенной обработкой. Файлы БД находятся на сервере, а программы обработки на рабочих станциях. - Распределенные БД, если файлы БД произвольно распределены на компьютерном NBC.
Задача оптимизации запросов является NP-полной, она разрешима для подкласса табло запросов, состоящих из простых табло запросов. Табло запросов не обладает такой выразительной силой как РА, но оно может представлять любое алгебраическое выражение, включающее только селекцию по равенству, проекцию и соединение.
Введем класс алгебраических выражений, которые можно выразить с помощью табло запросов. Назовём ограниченным алгебраическим выражением - селекции - проекции - естественного соединения. Табло похоже на отношения, но вместо значений атрибутов содержит переменные из некоторого множества Табло записывается в виде таблицы:
Множество атрибутов, именующих столбцы табло, образуют схему табло. Кортежами отношения являются строки табло. Ограничения: 1. каждая переменная в табло принадлежит только одному столбцу; 2. каждый столбец содержит не более одной выделенной переменной. Если имеем Табло со схемой Пусть
В табло запросов, так же как и в табло переменные делятся на выделенные и невыделенные, кроме них в ТЗ встречаются константы и пробелы. Выделенные переменные, невыделенные, константы будем называть собирательно символом. Табло запросов содержит также резюме – выделенную строку. Резюме запроса записывается над строками ТЗ и будет выделяться линиями сверху и снизу.
Правила построения табло запросов: 1) Столбцы снабжены метками 2) Каждая выделенная переменная может встретиться лишь в одном столбце. 3) Если в столбце стоит выделенная переменная, то она должна встречаться и в резюме этого запроса. 4) В строках должны стоять только символы (а не пробелы). 5) В резюме должны стоять только выделенные переменные, константы и пробелы. 6) Если в столбце с меткой Резюме будем обозначать
Пример:
Пусть 1. 2. 3.
ТЗ называется простым, если в любом столбце, где есть парная невыделенная переменная, никакой другой символ не повторяется. ТЗ из примера – простое. Припишем строку:
– уже не является простым. Простые ТЗ эффективно минимизируются и эквивалентность минимальных ТЗ легко проверить. Теорема: Для простого ТЗ
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-01-25; просмотров: 270; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.44.199 (0.021 с.) |