Кук Д., Бейз Г. - Компьютерная математика, страница 10
Описание файла
DJVU-файл из архива "Кук Д., Бейз Г. - Компьютерная математика", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 7 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 10 - страница
Если запись локализована с помощью некоторого ключа, то поле, выделяемое из этой записи, называется проекцией. В данном контексте проекцией является еизз. Будем также говорить, что эти атрибуты зависят от ключа. 1 56 На рис. 2.7 представлен графический пример зависимостей в Я11Р1. Пример 6.3. Модифицируем файл ЯСАР( с целью включения туда информации об имеющихся на складе запасных частях и об их количествах, которые отдельный Рае. 2.7 поставщик желает продать в отдельной сделке.
Включим в файл также код поставки, из которого мы можем выяснить скорость и частоту поставок. Во избежание излишней детализации введены номер компании и номер запасной части (табл. 2.3). г" Таблица 23 место КАс- ПОЛОЖЕНИЯ количвст- ВО ЗАП, чАсть КОМПАНИЯ постлвшик Из табл. 2.3 выясним, какие преобразования мы можем делать с Я()Р2, а какие нет: а) вставка, Например, мы не можем добавить в файл запись, указывающую, что компании 4 (РВ1г(ТАСО) находится в Манчестере, без указания деталей, которые она может поставлять; б) удаление.
Если компании 8 (ВТХ) прекратила поставки запчастей 1, тогда мы обязаны удалить все записи, относящиеся к атой компании и имеющие в поле ЗАП, ЧАСТЬ код 1; ба РОМРОМ РОМРОМ РОМВОМ РОМРОМ РОМРОМ В'НАМ В'НАМ В'НАМ В'НАМ В'НАМ РОМРОМ 10 1 10 2 5 2 10 А 10 10 10 в) модификация. Если код поставщика для Лондона изменился, например, из-за транспорта, то соответствующее поле должно быть изменено з каждой записи, где есть код ЬОМПОХ в поле МЕСТО РАСПОЛОН(ЕНИЯ. Что можно сделать для того, чтобы уменьшить или отодвинуть эти проблемы? С практической точки зрения мы должны выделить информацию в БПР2 так, чтобы по возможности избежать повторений. Таким образом, Табззца 24 ЗПРЗ Таб лица 25 ком- пА ния по- СТАВ. щяк МКСТО РАСПО- ложкния постлв- щнк МЕСТО РАС- положв- ния ЗАП.
ЧАСТЬ ЗАП. ЧАСТЪ волн- ч яство КОМПА- нин ЗАП. ЧАСТЬ мы получаем возможность вставки/удаления части записи в БУР2. Возможное и, на наш взгляд, разумное разделение дается в БОРЗ (табл. 2.4). Тогда остаток информации в БУР2 может содержаться в поле ЗАП.ЧАСТЬ. Используя эту конфигурацию, можно, например: а) включить в БПР3 запись, означающую, что компания 4 находится в Манчестере (код поставщика 3); 5В ЬОМПОМ ЬОМООМ В'НА51 В'НАМ ЬОМВОМ 10 1 10 2 5 2 10 4 10 10 10 ЬОМВОМ ЬОМВОМ В'НАМ М'СНЕЗТЕВ В'НАМ ЬОМВОМ 10 1 10 2 5 2 10 1О 10 б) удалить ссылку на компанию 6 как на поставщика запчасти 1, но оставить соответствующий код в ЗПРЗ; в) изменить код поставщика для ЬОХВОХ на 7 путем замены только трех входов„соответствующих компаниям с кодом 1, а не всех шести.
Результаты этих изменений приведены в табл. 2.5. Зто уже значительно лучше, однако все же может быть ззгз здп. чытз Рис. 88 еще усовершенствовано. Чтобы увидеть, в каком направлении продолнсать исследования, отделим ключи я подчиненные части (рис. 2.8). Заметим, что ЗАП. ЧАСТЬ требует объединенного ключа. Все не-ключи непосредственно связаны с ключом. Зто дает нам следующее свойство нормальной формы. в' О п р е д е л е п и е. Файл имеет вторую нормальную (борму (2г)Р), если он имеет форму (АР и неключевые атрибуты полностью независимы от ключа. в" Пример 6.3 (продоливение).
Файл 81)РЗ все еще является достаточно сложным в том смысле, что для данной записи ПОСТАВЩИК может бытьустановлен при помощи исследования поля КОМПАНИЯ или яве поля МЕСТО РАСПОЛО)КЕНИЯ. Это является причиной того, что в требовании а) код поставщика для Манчестера должен быть вставлен перед записью кода 4 компании, а требование б), возможно, потребует изменить более одной записи для модификации единственного ноля данных, относящегося к коду поставщика. На практике мы можем убрать эту проблему проектированием 81)РЗ в Б()Р4 и ВЕЬ (табл.
2.6). (Заметим, что коды поставщика, изменяемые таким образом, препятствуют той возможности, что любые другие записи в файле вызывают противоречивую информацию. В 8()РЗ можно иметь запись вида «ПОСТАВЩИК КОМПАНИИ 6-2з и вПО- 89 СТАВП«ИК КОМПАНИИ (-7ь на некотором этапе модификации Я)Р2, несмотря на тот фант, что обе компакии Находятся в Лондоне.) Зависимость отношений в З()Р4 и ЭЕЬ изображена ка рис. 2.9. Р Нетракэитивкость отношения зависимости является вкутренвим свойством, иэ которого возникает понятие третьей нормальной формы. Таблаца 26 МЕСТО РАСПО- ложенпя МЕСТО РАСПО- ложеняя ПОСТАЗЩКК КОМПАНИЯ ! Об ВОН В'НАМ М'СНЕЕТЕВ ЬОНВОН ЬОХВОН В'НАМ М'СНЕВТЕВ В'НАМ ЬОХВОХ ЗОРЕ згь Рас. 2.9 своей целью в дальнейшем.
Достаточно лишь иметь в виду, что информация в файлах является одной иа реалиааций математического понятия отпошепия. Практическое использование отношений ЯУР4 и ПЕЬ требует явной связи атрибута МЕСТО РАСПОЛО)КЕНИЯ файла ЗНР4 с атрибутом МЕСТО РАСПОЛОЖЕНИЯ файла ВЕЬ, Зто — отношение эквивалентности ео Определение. Файл находится в третьей нормальной Форме (ЗХГ), если оп является файлом 2ХР, и каждый атрибут, яе являющийся ключом, яетракзитивкым образом зависит от ключа.
г" Возможен и другой путь — каждый атрибут, ке являющийся ключом, зависит только от ключа и пи от чего другого. Как было отмечено ранее, существует мпого других «иормалькыхь форм, ко мы пе ставим иаучекие файлов (между компонентами различных файлов, имеющих одно и то же имя). Подобные отношения эквивалентности могут быть использованы для определения внутренних связеи и других структурных данных. В качестве иллюстрации рассмотрим рис. 2.10. Диаграмма на рис.
2.10, а а Рвс. 230 изображает дерево, диаграмма на рис. 2.10, Ь подобна диаграмме структурных данных, а диаграммы на рис. 2.10, с и Ы описывают нх воэможные применения. Отметим, что отношения эквивалентности раэличны, но результирующие структурные свявн сохраняются. С ма- тематической точки эрения это является раэбиением на классы эквивалентности. Следовательно, мы можем опре- делить проиэвольное представление этого дерева как эле- мент множества Т Р~Е, где Р (а (х,а,р),Ь=(у, Ь,в),е (и,с,и), И (о, Н, г), е (е, е, Ф)), Е ((х, Ь), (у, И), (р, с), (в, е)).
Эти вопросы будут обсуждаться в $4 гл. 3, в 7. Составные отношения Подобно тому как мы устанавливали внутренние свяэи в файлах, для выделения некоторых данных из информации (например, ПОСТАВЩИК к МЕСТО РАСПОЛОЖЕНИЯ 3 посредством файлов ПЕЬ и ЗБР4 в примере 6.3) часто приходится свяэывать бинарные отношения друг с другом. Руководствуясь предыдущими рассуждениями, можно определить это понятие следующим обраэом. Определение. Пусть заданы множества А, В и С и отношения о между А и В и р меэкду В и С.
Определим отношение между А и С следующим образом: опо действует иэ А в В посредством о, а эатем из В в С посредством р. Такое отношение называют состаеным и обовначают р ° а, т. е. (р ° о) (а) = р(о(а) ). г' Следовательно, (х, р) ж (р ° а), если существует х ж В такое, что (х, г)же и (з, р)жр. Отсюда следует, что м);, о Ю,. Чтобы проиллюстрировать ситуацию, рассмотрим рис. 2АЬ Области определения и эначении о и Рис.
23$ р заштрихованы в равных направлениях. Следовательно, сегменты с двойной штриховкой ва А, В и С представляют собой <В,.„!В, П Я, и йт... соответственно. Замечание. Иа записи отношений о и р следует, что они применяются справа налево. Следовательно, (р ' о)(а) оэначает, что вначале берется а и преобраэуетсн посредством с, а ватам преобразуется посредством р.
В алгебре это иногда эаписывают в виде сор. Следует обращать внимание при чтении других математических книг на то, какой порядок выполнения отношений принят в той книге. 62 Првмер 7.1. Пусть о и р — отношения иа Х такие, что о ((х, х+1): хжХ), р ((х', х): хыХ). Тогда !й,=(х~: х~иХ), ЯР, (х: х, х+1жХ) =Х, йр;, аю, (х: х ж Х и х+ 1 рт, где р ж Х) (3, 8, 15, 24, .) (рис. 2.12). Х В случае, когда мы рассматриваем отношение на мвожестве, оно может быть скомбинироваво само с о 6 Рвс.
2.12 собой. Например, используя отношения из примера 7.1, имеем о~с=((х, х+2): хжХ) и р ° р=((х', х): хж Х). Эти отношения можно также обозначать соответственно оз и р'. В общем-то эти обозначения пе совсем заковвы для множеств, однако их легко можно обосповать, поскольку если (х, у)ыо о, то ((х, х), (з, р))ыОХс при некотором з; ввкакого недоразумевия при этом lе воаникает, поскольку известна структура получаемого результата. Используя это обозначение, мы можем определить о" для любого пжХ, л= 1, следующим образом: о" ((х, р); хог и зо" 'р для некоторого з).
Если мы вновь возьмем отношения а и р из примера 7.1, то получим о" = ((х, х + и), х ы Х) и р" ((х', х): х ы Х). Хотелось бы рассмотреть вопрос о том, насколько в этих 63 случаях применима аналогия с умножением. Пусть А— множество, а  — отношение на А. Тогда отношения 1„В, В и В 1«еквивалентны; поэтому 1«является тождественным отношением на А, которое ведет себя подобно числу ( по отношению к умножению чисел. Чтобы дополнить аналогию, желательно было бы иметь воэможность писать В 'еВ 1«В ° В-'. Однако в общем случае этого делать нельвя.