ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Лекції з теорії проектування баз даних (БД )
         

     

    Інформатика, програмування

    Лекція 1

    Технологія проектування баз даних

    Питання:

    1. Проектування бази даних як елемент інформаційної технології;

    Теоретичні основи проектування БД;

    1. Синтез БД.

    Проектування бази даних як елемент інформаційної технології

    Як видно з матеріалів попередніх лекцій основу більшості інформаційних технологій складають великі масиви накопиченої інформації. Основною формою організації зберігання даних в інформаційних системах є бази даних. У курсі "Автоматизовані системи обробки облікової інформації" ми розглянули основні поняття, пов'язані з моделями даних, теоретичні основи розробки найпростіших баз даних і життєвий цикл баз даних. Тепер, розглядаючи БД як частина інформаційної технології, необхідно по новому поглянути на проблему проектування бази.

    Проблеми проектування пов'язані з функціями БД в програмно - технологічної середовищі, що підтримує інформаційні технології. У загальному випадку місце БД можна відобразити наступною схемою:

    Програми підтримки

    інформаційних технологій

    Інші програми

    Оскільки база даних є сполучною ланкою між одними програмами та апаратними засобами, її проектування можна розділити на два напрямки: проектування структури і призначених для користувача програм та розподіл даних по апаратних засобів (у випадку баз даних на мережах). У цьому розділі ми розглянемо питання проектування структури бази даних. У дисципліні
    АСОЕІ, розглядаючи основи реляційної алгебри та розробки реляційних моделей, ми торкнулися питань проектування реляційних баз даних.
    Однією з поширених технологій розробки БД є наступна:

    1. збір даних про предметну область;
    1. аналіз уявлень користувачів;
    1. інтеграція уявлень користувачів;
    1. розробка мережевої моделі;
    1. перетворення мережевої моделі в першу нормальну форму реляційної моделі;
    1. нормалізація відносин шляхом перетворення їх до третьої нормальної форми.

    У результаті виходить модель реляційної бази даних, яка являє собою сукупність взаємопов'язаних відносин.

    Побудова мережевої моделі пов'язано скоріше з потребою розробника графічно представити взаємозв'язок даних, отриманих в результаті інтеграції представлень користувачів. Перетворення мережевої моделі в реляційну дає першу нормальну форму останньої.

    Нагадаємо, що ставлення R знаходиться в першій нормальній формі, якщо значення в dom (A) є атомарними для кожного атрибута А в R. < p> Друга і третя нормальні форми дозволяють уникнути аномалій при оновленні даних і позбудеться інформаційної надмірності у відносинах. Нагадаємо, що ставлення R нормальній формі, якщо воно знаходиться в першій нормальній формі і кожен атрибут не є ключем повністю залежить від будь-якого ключа в R. І ставлення R знаходиться в третій нормальній формі, якщо воно знаходиться у 2НФ і кожен атрибут, який не є первинним ключем не транзитивній залежить від будь-якого можливого ключа.

    Недоліком такого підходу є те, що в моделях, що мають десятки і сотні атрибутів дуже важко Імперична побудувати модель, всі відносини якої задані в третій нормальній формі і пов'язані між собою таким чином, що складають єдине ціле.

    Приклад.

    Іншим підходом є можливість формального синтезу моделі на підставі апріорно встановлених залежностей між атрибутами.
    Залежності між атрибутами встановлюються на підставі смислового зв'язку.

    Приклад.

    НОМЕР_ЗАЧЕТКІ - ІМЯ_СТУДЕНТА

    НОМЕР_РЕЙСА - ДАТА_ВИЛЕТА

    Безумовно такий підхід до розробки моделі бази даних переважно, оскільки дозволяє автоматизувати процес моделювання. Для реалізації цього підходу необхідно розширення теоретичної бази, отриманої в курсі АСОЕІ.

    Теоретичні основи проектування БД.

    Основні поняття.

    Оскільки розглянутий підхід до розробки реляційної моделі базується на формальної логіки, то в його основі повинні лежати деякі фундаментальні формалізації. В теорії реляційних баз даних до них відносяться поняття атрибуту, відносини, ключа та функціональної залежності.

    Атрибутом будемо називати зазначені властивість об'єкта і позначати
    АI, де. Домен атрибута АI позначимо dom (АI). Тоді ставленням R називається кінцеве безліч атрибутів. Ключ відносини R є підмножиною К = з наступним властивістю. Для будь-яких двох різних кортежів t1 і t2 в R існує таке, що t1 (B) t2 (B). Іншими словами, не існує двох кортежів, що мають одне і те ж значення на всіх атрибутах з К. Таким чином, досить знати К - значення кортежу, щоб ідентифікувати кортеж однозначно.

    Приклад.

    СТУДЕНТ [НОМЕР_ЗАЧЕТКІ, ІМ'Я, КУРС, ГРУПА]

    Ключі, явно зазначені в моделі називаються виділеними. Можуть бути ключі відмінні від виділених і звані неявними ключами. Наприклад Ім `я в попередньому прмере.

    Під функціональною залежністю атрибутів або F-залежністю розуміють такий зв'язок між атрибутами, коли значення кортежу на одному безлічі атрибутів єдиним чином визначають ці значення на іншому множині атрибутів. Так у відношенні:

    ГРАФІК [ПІЛОТ, РЕЙС, ДАТА, ЧАС]

    ПІЛОТ функціонально залежить від (РЕЙС, ДАТА)

    F-залежності прийнято позначати ( РЕЙС, ДАТА) -> ПІЛОТ і кажуть, що
    РЕЙС і ДАТА функціонально визначають ПІЛОТ.

    У термінах теорії множин і реляційної алгебри F-залежність визначається так. Нехай R відношення і X, Y підмножини атрибутів у R.
    Відношення R задовольняє функціональної залежності X -> Y, якщо (Y ((X-x ®) має не більше ніж один кортеж для кожного Х - значення х. У F - залежно X-> Y підмножина X називається лівою частиною, а Y - правою частиною.

    Лекція 2

    Така інтерпретація функціональної залежності є основою алгоритму SATISFIES, що приводиться нижче.

    SATISFIES

    Вхід: Отншеніе R і F-залежність X-> Y.

    Вихід: істина, якщо R задовольняє X-> Y, брехня - в іншому випадку.

    SATISFIES (R, X-> Y)

    1. Відсортувати відношення R з Х-стовпцях так, щоб зібрати кортежі з рівними Х-значеннями вмести.
    1. Якщо кожна сукупність кортежів з рівними Х-значеннями має також рівні Y-значення, то на виході отримуємо істину, а в іншому випадку - брехня.

    Цей алгоритм перевіряє, чи задовольняє відношення R F-залежності < p> X -> Y.

    Приклад.

    В результаті виконання алгоритму SATISFIES з'ясуємо чи задовольняє
    F-залежність РЕЙС -> ВРЕМЯ_ВИЛЕТА наступного відношенню

    ГРАФІК

    | ПІЛОТ | РЕЙС | ДАТА | ВРЕМЯ_ВИЛЕТА |
    | А. .. | 83 | 9 серпня | 10:15 |
    | П. .. | 83 | 11 серпня | 10:15 |
    | А. .. | 116 | 10 серпня | 13:25 |
    | Р. .. | 116 | 12 серпня | 13:25 |
    | П. .. | 281 | 8 серпня | 5:50 |
    | С. .. | 281 | 9 серпня | 5:50 |
    | П. .. | 301 | 12 серпня | 18:35 |
    | С. .. | 412 | 15 серпня | 13:25 |

    Однак F-залежність ВРЕМЯ_ВИЛЕТА -> РЕЙС згідно з цим алгоритмом не виконується для цього відносини

    ГРАФІК

    | ПІЛОТ | РЕЙС | ДАТА | ВРЕМЯ_ВИЛЕТА |
    | П. .. | 281 | 8 серпня | 5:50 |
    | С. .. | 281 | 9 серпня | 5:50 |
    | А. .. | 83 | 9 серпня | 10:15 |
    | П. .. | 83 | 11 серпня | 10:15 |
    | А. .. | 116 | 10 серпня | 13:25 |
    | Р. .. | 116 | 12 серпня | 13:25 |
    | С. .. | 412 | 15 серпня | 13:25 |
    | П. .. | 301 | 12 серпня | 18:35 |

    Для розробки моделі бази даних необхідно знати повне безліч F -залежностей. Щоб знайти їх, необхідні семантичні знання про вихіднийвідношенні R. Тому можна вважати сімейство F-завсімостей заданим.
    Позначимо його F. Однак при такому підході не можна бути впевненим, щознайдені всі F-залежності відносини R. Для того, щоб знайти всі F -залежності, якщо відомі деякі з них, можна скористатисяаксіомами виводу. Можливість отримання нових F-залежностей за допомогоюаксіом виведення базується на наступному правилі. Мнжество F-залежностей Fтягне за собою F-залежність X -> Y (позначення: F = X -> Y), якщокожне відношення задовольняє всім залежностей в F, задовольняє такожзалежно X -> Y. Аксіома виведення - це правило, яке встановлює, що якщоставлення задовольняє певним F-залежностей, то воно повиннезадовольняти і деяким іншим F-залежностей. Існує шість аксіомвисновку:

    рефлексивність: X -> X.
    Поповнення: X -> Y тягне за собою XZ -> y.
    адитивність: X -> Y і X -> Z тягне за собою X -> YZ.
    проективної: X -> YZ тягне за собою X -> Z.
    Транзитивність: X -> Y і Y -> Z тягне за собою X -> Z.

    Псевдотранзітівность: X -> Y і YZ -> W тягне за собою XZ -> W.

    Приклад.

    Нехай дано відношення R, а X, Y і Z підмножини R. Припустимо, що відносно задовольняє XY -> Z і X -> Y. Згідно аксіомі псевдотранзітівності отримаємо XX -> Z або X -> Z.

    Якщо дані аксіоми рефлексивности, поповнення та псевдотранзітівності, то з них можна вивести всі інші. Іноді їх називають аксіомами
    Армстронга.

    Нехай F-безліч F-залежностей для відносини R. Замикання F, що позначається F +, - це найменше що містить F безліч, таке що при застосуванні до нього аксіом Армстронга не можна отримати жодної F - залежності, яка не належить F.

    Приклад.

    Нехай F = (AB -> C, C -> B) - безліч F-залежностей на R (ABC). F +
    = (A -> A, AB -> A, AC -> A, ABC -> A, B -> B, AB -> B, BC -> B, ABC ->
    B, C -> C, AC -> C, BC -> C, ABC -> C, AB -> AB, ABC -> AB, AC -> AC, ABC
    -> AC, BC -> BC, ABC -> BC, ABC -> ABC, AB -> C, AB -> AC, AB -> BC, AB
    -> ABC, C -> B, C -> BC, AC -> B, AC -> AB)

    Таким чином, якщо відомо безліч F-залежностей задовольняютьвідношенню R, можна знайти всі F-залежності, що задовольняють цьомувідношенню. Кажуть, що F = X -> Y, якщо X -> Y F +.

    Лекція 3

    Отримання замикання F + не обов'язково для встановлення F = X ->
    Y.

    Для цього достатньо скористатися алгоритмом MEMBER.

    Алгоритм MEMBER.

    Вхід: Безліч F-залежностей F і F-залежність X -> Y.

    Вихід: істина, якщо F = F = X -> Y, брехня в іншому випадку.

    MEMBER (F, X -> Y)

    begin

    if Y CLOSURE (X, F) then return (істина)

    else return (false) end

    Тут CLOSURE алгоритм, що дозволяє виявити список атрибутів що входять в безліч F, що має вигляд.

    Алгоритм CLOSURE.

    Вхід: Безліч атрибутів Х і безліч F-залежностей F.

    Вихід: Замикання Х над F.

    CLOSURE (X, F)

    begin

    OLDDEP = 0; NEWDEP = X

    while NEWDEP OLDDEP do begin

    OLDDEP = NEWDEP

    for кожна F-залежність W -> Z в F do

    if NEWDEP W then

    NEWDEP = NEWDEP Z

    end

    return (NEWDEP) end

    Приклад роботи алгоритму MEMBER

    Нехай F = (НОМЕР_РЕЙСА ДАТА_ВИЛЕТА -> КОЛІЧЕСТВО_МЕСТ, < p> НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНІЯ, НОМЕР_РЕЙСА ДАТА_ВИЛЕТА -> ПІЛОТ) і необхідно встановити F | = НОМЕР_РЕЙСА -> ПІЛОТ

    Використовуємо для цього алгоритм MEMBER

    Покриття функціональних залежностей < p> Для формування БД, як системи взаємопов'язаних відносин на підставі відомих (з семантичних міркувань) F-залежностей необхідно мати спосіб мінімізації початкового безлічі F-залежностей. Це необхідно для мінімізації дублювання даних, забезпечення їх узгодженості і цілісності. Теоретичною основою для побудови такого способу є теорія покриттів функціональних залежностей.

    Визначення.

    Два безлічі F-залежностей F та G над ставленням R еквівалентні,
    , якщо F + = G +. Якщо, то F є покриття для G.
    Передбачається, що має сенс розглядати в якості покриттів такі множини F, які не перевершують безліч G за числом F-залежностей.

    З цього визначення випливає, що для встановлення факту, що безліч функціональних залежностей F є покриттям G, необхідно визначити еквівалентність F і G. Практично це досягається шляхом використання наступного алгоритму:

    Алгоритм EQUIV
    Вхід: дві безлічі F-залежностей F та G.
    Вихід: істина, якщо; брехня в іншому випадку. < p> EQUIV (F, G)

    begin

    v = DERIVES (F, G) and DERIVES (G, F); return (v) end

    Тут DERIVES алгоритм перевіряє умову F | = G і має вигляд:

    Алгоритм DERIVES
    Вхід: дві безлічі F-залежностей F та G.
    Вихід: істина, якщо F | = G; брехня в іншому випадку.

    DERIVES (F, G)

    begin

    v = істина for кожна F-залежність X -> Y з G do v = v and MEMBER (F, X -> Y)

    end return (v) end

    Безліч F-залежностей F не надмірною, якщо у нього немає такого власного підмножини F ', що F'F. Якщо така безліч F 'існує, то F великій кількості. F є не надлишковим покриттям G, якщо F є покриття G і F не надмірною.

    Приклад. Нехай G = (AB -> C, A -> B, B -> C, A -> C). Безліч F =
    (AB -> C, A -> B, B -> C) еквівалентно G, але надмірно, тому що F '=
    (A -> B, B -> C) також є покриттям G. Безліч F 'представляє собою не надлишкове покриття G.

    Дійсно, відповідно до алгоритму EQUIV, так як DERIVES (F, G) дає істину і DERIVES (G, F) так само істина. Те ж саме можна сказати стосовно F 'і G.

    (Докладніше)

    Безліч F не надмірною, якщо в ньому не існує F-залежності X ->
    Y, такий , що F - (X -> Y) | = X -> Y. Назвемо F-залежність з F надлишкової в F, якщо F - (X -> Y) | = X -> Y.

    Для будь-якого безлічі F-залежностей G існує деякий підмножина F, таке, що F є не надмірною покриттям G. Якщо G не надмірно, то F = G. Для визначення не надлишкового покриття безлічі F-залежностей G існує алгоритм NONREDUN, який має вигляд:

    Вхід: безліч F-залежностей G.
    Вихід: не надлишкове покриття G.

    NONREDUN (G)

    begin

    F = G for кожна залежність X -> Y з G do

    if MEMBER (F-(X-> Y] , X-> Y) then F = F-(X-> Y)

    end

    return (F)

    end

    Приклад: Нехай G = (A -> B, B -> A, B -> C, A -> C).

    Результатом роботи алгоритму є безліч:

    (A -> B, B -> A, A -> C).

    Якби G було представлено в порядку (A -> B, A -> C, B -> A, B ->
    C), то результатом роботи алгоритму було б

    (A -> B, B -> A, B -> C).

    З прикладу видно, що безліч F-залежностей G може мати більше одного неізбиточного покриття. Можуть так само існувати неізбиточние покриття G, що не містяться в G. У наведеному прикладі таким неізбиточним покриттям буде безліч

    F = (A -> B, B -> A, AB -> C).

    Якщо F-неізбиточное безліч F-залежностей, то в нього немає "зайвих" залежностей в тому сенсі, що не можна зменшити F, видаливши деякі з них. Видалення будь-F-залежності з F призведе до безлічі, не еквівалентному F. Однак розмір можна зменшити, видаливши деякі атрибути F-залежностей F.

    Визначення. Нехай F-безліч F-залежностей над R і X -> Y є F-залежність з F. Атрибут А з R називається стороннім в X -> Y щодо F, якщо

    1. і (F - (X -> Y)) (Z -> Y) F або
    1. Y = AW, YW і (F - (X -> Y)) (X -> W) F.

    Іншими словами, А - сторонній атрибут, якщо він може бути вилучений з правої або лівої частини X -> Y без зміни замикання F.

    Приклад. Нехай G = (A -> BC, B -> C, AB -> D). Атрибут С є стороннім у правій частині A -> BC, а атрибут B - у лівій частині AB -> D.

    Визначення. Нехай F - безліч F-залежностей над R і X -> Y належить F. F-залежність X -> Y називається скороченої ліворуч, якщо
    Х не містить стороннього атрибуту А і скороченої праворуч, якщо Y не містить атрибуту А, стороннього для X -> y. Залежність X -> Y називається скороченої, якщо вона редукована ліворуч і праворуч і Y
    . Редукована ліворуч F-залежність називається також повної F-залежністю.

    Визначення. Безліч F-залежностей F називається редукованому
    (ліворуч, праворуч), якщо кожна F-залежність з F редукована
    (відповідно ліворуч, праворуч).

    Приклад. Безліч G = (A -> BC, B -> C, AB -> D) не є редукованому ні праворуч, ні ліворуч. Безліч G1 = (A -> BC, B -> C, A ->
    D) зредуковано ліворуч, але не справа, а G2 = (A -> B, B -> C, AB -> D) зредуковано справа , але не зліва. Безліч G3 = (A -> B, B -> C, A -> D) зредуковано зліва і справа, отже, оскільки праві частини не порожні, зредуковано.

    Для знаходження зредуковані покриттів використовується алгоритм:

    REDUCE

    Вхід: безліч F-залежностей G.
    Вихід: скороченої покриття G.

    REDUCE (G)

    begin

    F = RIGHTRED (LEFTRED (G)) видалити з F всі F-залежності виду X -> return (F) end

    тут RIGHTRED і LEFTRED алгоритми редукування відповідно праворуч і ліворуч, які мають вигляд:

    RIGHTRED

    Вхід: безліч F-залежностей G.
    Вихід: скороченої справа покриття G.

    RIGHTRED (G)

    begin

    F = G for кожна залежність X -> Y з G do

    for кожен атрибут А з Y do

    if MEMBER (F - (X -> Y) (X -> (Y - A)), X -> A) then

    видалити А з Y в X -> Y з F

    end

    end

    return (F) end

    Алгоритм LEFTRED
    Вхід: безліч F-залежностей G.
    Вихід: скороченої ліворуч покриття G.
    Begin

    F = G for кожна залежність X -> Y з G do for кожний атрибут А з Х do if MEMBER (F, (X - A) -> Y) then видалити А з X в X -> Y з F end end return (F) end

    Приклад. Нехай G '= (A -> C, AB -> DE, AB -> CDI, AC -> J). З
    LEFTRED (G') отримуємо G "= (A -> C, AB -> DE, AB -> CDI, A -> J) і з
    RIGHTRED (G ") отримуємо F = (A -> C, AB -> E, AB -> DI, A -> J), вже скороченої.

    Далі буде потрібно знаходити розбиття множини F-залежностей, заданих на ставленні R на підмножини, які являють собою класи F-залежностей з еквівалентною лівою частиною.

    Визначення: дві безлічі атрибутів X і Y називаються еквівалентними на безлічі F-залежностей F, якщо F | = X-> Y і F | = Y -> X.

    Наприклад нехай дадуть F = (A -> BC, B -> A, AD -> E), знайдемо всі F-залежності еквівалентні лівій частині першій, тобто А. Ліва частина друга
    F-залежності (В) еквівалентна А? Перевіримо F | = A -> B і F | = B -> A.
    Це дійсно так. Отже А еквівалентно В і перші два F-залежності можна об'єднати в один клас еквівалентності, який позначається в загальному випадку ЕА (Х). Безліч класів еквівалентності для заданої множини F-залежностей позначається F. Скороченим способом запису F-залежностей з еквівалентними лівими частинами є складова функціональна залежність (CF-залежність), що має вигляд:

    (X1, X2, ..., Xk) -> Y < p> де X1, X2, ..., Xk, безліч еквівалентних лівих частин F-залежностей, а Y об'єднання правих частин F-залежностей.

    Синтез реляційних баз даних

    База даних складається з безлічі атрибутів і ключів. З точки зору теоретико-множинного опису реляційної базою даних d називається така сукупність відносин (R1, R2, ..., Rp), в якій кожне відношення має вигляд Ri = (Si, Ki), де Si-безліч атрибутів, а Ki -- безліч атрибутів утворюють ключ.

    Припустимо на вході задано безліч F-залежностей F над R. З їх допомогою потрібно створити базу даних R = (R1, R2, ..., Rp). Ця БД повинна задовольняти наступним вимогам:

    1. безліч F повністю характеризується за допомогою R, тобто

    де К - виділений ключ Ri)

    2. Кожне ставлення Ri знаходиться в третій нормальній формі.

    3. Не існує бази даних з меншим числом відносин, що задовольняє пунктами 1 і 2.

    4. З'єднання всіх отриманих відносин Ri дає початкове відношення R.

    Алгоритм породжує базу даних із заданих F-залежностей називаєтьсяалгоритмом синтезу.

    Визначення. Якщо R - база даних і на ній задано безліч F-залежностей
    G, то в ній існує принаймні | EG | відносин. Це означає, що в
    R стільки ж відносин, скільки і класів еквівалентності. З цього випливаєнаступне.

    Нехай F - безліч F - залежностей. Будь-яка база даних повинна мати
    | EF '| відносин, де F' неізбиточное покриття для F.

    Виходячи з цього будується спосіб побудови структури бази даних.

    Спочатку знаходиться неізбиточное покритіеF 'для F і в EF' обчислюємо класиеквівалентності. Для кожного EF '(X) будуємо відношення, що складається з усіхатрибутів, що з'являються в EF '(X). При цьому атрибути лівій частині кожногокласу еквівалентності утворюють виділений ключ.

    Реалізація цього способу дозволяє отримати алгоритм SYNTHESIZE

    Вхід: безліч F - залежностей F над R.

    Вихід: повна схема баз даних для F.

    1. Наити для F скороченої мінімальне покриття G.

    2. Для кожної CF - залежності (X1, X2, ..., Xk) Y з G побудувати відношення Rj = X1X2 ... XkY з виділеними ключами K = (X1, X2, ... Xk).

    3. Назад до п. 2.

    Приклад.

    A B1B2C1C2DEI1I2I3J

    B1B2C1 AC2DEI1I2I3J

    B1B2C2 AC1DEI1I2I3J

    E I1I2I3

    C1D J C2D J

    I1I2 I3 I2I2 I1 I1I3 I2

    І хай R = AB1B2C1C2DEI1I2I3J

    Безліч мінімально, але не зредуковано . Редуціруя F, отримаємо

    F '= (A B1B2C1C2DE E I1I2

    B1B2C1 A B1B2C2 A

    C1D J C2D J

    I1I2 I3 I2I2 I1 I1I3 I2)

    Образуя класи еквівалентності маємо

    G = ((AB1B2C1, B1B2C2) DE

    (E) I1I2

    (C1D) J (C2D) J

    (I1I2, I2I2, I1I3))

    Перетворюючи кожну CF - у відносини з виділеними ключами, отримаємо

    R1 = AB1B2C1C2DE K1 = (AB1B2C1, B1B2C2)

    R2 = EI1I2 K2 = (E)

    R3 = C1DJ K3 = (C1D)

    R4 = C2DJ K4 = (C2D)

    R5 = I1I2I3 K5 = (I1I2, I2I2, I1I3)

    Остаточна схема БД буде R = (R1, R2, R3, R4, R5)

    Розподілена обробка даних

    Під розподіленою обробкою даних розуміють такий спосіб зберігання і обробки даних, коли окремий додаток може обробляти дані,,розподілені на безлічі різних баз даних, управління якимиздійснюють різними СУБД, що працюють на різних машинах з різнимиопераційними системами, з'єднаних комунікаційними системами.
    Розподілена база даних (РБД) є віртуальним об'єктом, частиниякого розташовані на віддалених базах даних, пов'язаних каналами зв'язку.

    Фізично РБД складається з набору вузлів, пов'язаних комунікаційноїмережею, в якій:

    . Кожен вузол має своїми власними системами баз даних;

    . Вузли працюють злагоджено, тому користувач може отримати доступ до даних на будь-якому вузлі мережі, як ніби всі дані знаходяться на власному сайті.

    Кожен вузол має своїми власними базами даних, власнимилокальними користувачами, власної СУБД і програмним забезпеченням дляуправління транзакціями, а так само власним диспетчером передачі даних.
    Розподілена СУБД може розглядатися як певний спосіб спільноїроботи окремих локальних СУБД, розташованих на різних локальних вузлах.
    Причому новий компонент програмного забезпечення на кожному вузлі підтримуєвсі необхідні функції спільної роботи. Комбінація цього компонента ііснуючої СУБД називається розподіленої системи управління Базами
    Даних (РСУБД).

    В основі розподілених баз даних лежать наступні вимоги:

    1. Локальна автономія;

    2. Незалежність від центрального вузла;

    3. Безперервне функціонування;

    4. Незалежність від розташування;

    5. Незалежність від фрагментації;

    6. Незалежність від реплікації;

    7. Обробка розподілених запитів;

    8. Управління розподіленими транзакціями;

    9. Незалежність від апаратного забезпечення;

    10. Незалежність від операційної системи;

    11. Незалежність від мережі;

    12. Незалежність від СУБД.

    Локальна автономія

    У розподіленої системі вузли слід робити автономними.

    Локальна автономія означає, що функціонування будь-якого вузла Х не залежить від успішного виконання операцій на деякому вузлі У. В іншому випадку вихід з ладу вузла У може призвести до неможливості виконання операцій на вузлі Х. З принципу локальної автономії випливає, що володіння і управління даними здійснюється локально разом з локальним веденням обліку. Насправді мета локальної автономії досягається не повністю, оскільки часто вузол Х повинен представляти деяку частину управління вузла У, тому говорять не про повну, а про максимально можливої автономії.

    Незалежність від центрального вузла. < p> Під локальної автономією мається на увазі, що всі вузли повинні розглядатися як рівні. Отже, не повинно існувати ніякої залежності і від центрального «основного» вузла з деяким централізованим обслуговуванням, наприклад централізованої обробки запитів, централізованим управлінням транзакціями або централізованим присвоєнням імен. Залежність від центрального вузла небажана з двох причин. По-перше, центральний вузол може бути

    «вузьким» місцем всієї системи, а по-друге, більш важливим є те, що система в цілому стає вразливою, тобто при пошкодженні центрального вузла може вийти з ладу вся система.

    Безперервне функціонування

    Однією з переваг розподілених систем є те, що вони забезпечують більш високу надійність і доступність.
    . Надійність (імовірність того, що система виконує властиві їй функції в заданий момент часу) підвищується завдяки роботі розподілених систем не за принципом «все або нічого», а в постійному режимі; тобто робота системи триває, хоча і на більш низькому рівні, навіть у разі несправності деякого окремого компонента, наприклад вузла.
    . Доступність (імовірність того, що система справна і працює протягом певного проміжку часу) підвищується частково з тієї ж причини, а частково завдяки можливості реплікації даних.

    Незалежність від розташування

    Ця мета передбачає забезпечення такого режиму роботи з даними, при якому користувачеві не потрібно знати, на якому вузлі знаходяться необхідні дані. При цьому значно спрощуються для користувача програми, а також не потрібно їх зміни при переміщенні даних в системі.

    Незалежність від фрагментації

    У системі підтримується фрагментація даних, якщо певне відношення з міркувань фізичного зберігання необхідно розділити на частини або фрагменти. Фрагментація бажана для підвищення продуктивності системи, оскільки дані краще зберігати в тому місці, де вони найбільш часто використовуються. При такій організації багато операцій стають локальними, а обсяг переданих у мережі даних знизиться.

    Існує два типи фрагментації - горизонтальна і вертикальна, які пов'язані з операціями селекції і проекції відповідно, тобто горизонтальний фрагмент може бути отриманий за допомогою операції селекції, а вертикальний - проекцією. Реконструкцію вихідного відносини на основі його фрагментів можна здійснити за допомогою операцій з'єднання (для вертикальних фрагментів) і об'єднання (для горизонтальних фрагментів).

    У фрагментованою системі необхідно забезпечити підтримку незалежності від фрагментації, тобто користувач не має «відчувати» фрагментації даних.

    Незалежність від реплікації

    У системі підтримується незалежність від реплікації, якщо задане відношення або фрагмент можуть бути представлені різними копіями

    (репліками) збереженими на різних вузлах. Реплікація корисна з двох причин. По-перше, завдяки їй досягається велика продуктивність, тому що додатки можуть працювати з локальними копіями

    , не обмінюючись даними з віддаленими вузлами. По-друге, реплікація дозволяє забезпечити більшу доступність, тому що реплікованих об'єкт залишається доступним для обробки до тих пір, поки залишається хоча б один його репліка. Головний недолік реплікації полягає в тому, що при оновленні репліціруемого об'єкта, всі його копії повинні синхронізуватися.

    У системі, яка підтримує реплікацію даних, повинна також підтримуватися незалежність від реплікації, тобто користувач не повинен торкатися проблем пов'язаних зі створенням та синхронізацією копій.

    Обробка розподілених запитів

    При обробці в розподіленої системі запиту необхідно виробити ефективну стратегію його реалізації. Наприклад, запит на об'єднання відносин Rx, розташованого на вузлі X, і відносини Ry, що зберігається на вузлі Y, може бути виконаний за допомогою переміщення відносини Rx на вузол Y, переміщення відносини Ry на вузол X або переміщення цих двох відносин на третій вузол Z? т.д. Це означає, що при виконанні запиту на розподіленої БД необхідний його попередній аналіз з подальшим вибором оптимальної стратегії його реалізації.

    Управління розподіленими транзакціями

    У розподіленої системі виконання транзакції пов'язано з виконанням програмних кодів на декількох вузлах. Транзакція це логічна одиниця роботи, яка включає всю сукупність дій, необхідних для реалізації запиту. Транзакція вважається неподільним процесом, тобто якщо будь-яке зі складових дій виявиться не виконаним, то вся транзакція вважається не виконаною. Кожен програмний код, що виконується на якому або вузлі при виконанні транзакції, називається агентом. Таким чином, транзакція складається з декількох агентів, тобто процесів реалізують транзакцію.

    У процесі управління транзакцією виділяють управління відновленням і керування паралельною обробкою. Перше з них базується на протоколі двофазної фіксації. У грубому наближенні згідно з цим протоколом на початку транзакції встановлюється точка фіксації даних, тобто як би створюється копія даних, які передбачається змінити в результаті транзакції. Якщо транзакція завершена нормально, то точка фіксації зберігається до виконання наступної транзакції. Якщо ж стався збій, то система повертає стан даних в точку фіксації, що дозволяє не допустити незворотного неправильного зміни БД. Управління паралельною обробкою передбачає встановлення блокувань на відносини, групи записів з метою не допустити зміна даних іншим користувачем під час виконання транзакції.

    Незалежність від апаратного забезпечення

    Використовувані в даний час комп'ютери характеризуються великою різноманітністю . У зв'язку з цим існує необхідність інтеграції даних на всіх системах і створення для користувача подання єдиної системи. Повинна мати можливість запуску однієї і тієї ж СУБД на різному апаратному забезпеченні.

    Незалежність від операційної системи

    Ця мета є наслідком попередньої. Необхідно, щоб одна й та сама СУБД могла працювати під управлінням різних ОС.

    Незалежність від мережі

    Якщо система в змозі підтримувати декілька вузлів з різним апаратним забезпеченням і різними операційними системами, то бажано , щоб в ній підтримувалися різні типи мереж.

    Незалежність від СУБД

    Ця мета означає, що бажано, щоб розподілена БД допускала використання різних СУБД різними користувачами. Це можливо тільки якщо ці СУБД підтримують деякий загальний стандарт представлення даних, наприклад, офіційний стандарт мови SQL.

    -----------------------
    Базаданих

    Операційна система

    АпаратнаСереда

    А В С

    GVMN

    DFGH

    BMTX

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status