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

     

     

     

     

     

         
     
    Ієрархічні довідники з лінійним часом доступу
         

     

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

    Ієрархічні довідники з лінійним часом доступу

    Гліб Земсков

    Вступ

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

    Наскільки гарний алгоритм

    Для ієрархічних довідників ми визначимо кілька найбільш часто зустрічаються завдань, які зачіпають ієрархію.

    отримання всіх нащадків вузла;

    отримання безпосередніх нащадків вузла;

    додавання нащадка;

    видалення вузла з нащадками;

    перенесення вузла.

    Ієрархія Дьюї (Dewey)

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

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

    Наприклад:

    1 Організація «Роги і копита».

    1.1 Департамент «Рогу».

    1.1.1 Відділ продажу рогів.

    1.1.2 Відділ покупки рогів.

    1.1.2.1 Група оцінки якості рогів.

    1.1.3 Відділ прокату рогів.

    1.2. Департамент «Копита»

    1.2.1 Відділ покупки копит.

    1.2.2 Відділ продажу копит.

    Як можна відразу помітити, при роботі з подібним класифікатором зручно використовувати оператора LIKE. Якщо вказується шлях, в якому початкові символи не є маскою, база даних може використовувати індекс з операцією index scan з діапазонним пошуком.

    Створимо тестовий приклад.        

    CREATE TABLE DEPARTMENT   

    (   

    ID INT PRIMARY KEY   IDENTITY (1,1),   

    Path VARCHAR (180) UNIQUE,   

    Position INT NOT NULL,   

    NAME VARCHAR (128)   

    )   

    GO      

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 ', 1,' Організація «Роги і копита »')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .1 ', 1,' Департамент «Роги »')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .1.1 ', 1,' Відділ продажу рогів ')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .1.2 ', 2,' Відділ покупки рогів ')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .1.2.1 ', 1,' Група оцінки якості рогів ')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .1.3 ', 3,' Відділ прокату рогів ')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .2 ', 2,' Департамент «Копита »')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .2.1 ', 1,' Відділ покупки копит ')   

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .2.2 ', 2,' Відділ продажу копит ')   

    GO     

    Розрахунок довжини поля Path

    Перш за все слід уточнити, чому полі Path має довжину 180. Розрахунок простий. Кількість підлеглих відділів кожного вузла в довіднику навряд чи може бути більше, ніж тризначна цифра (від 0 до 999 підрозділів). Таке не під силу навіть таким гігантам, як Газпром. Ділимо кількість зайнятих символів 4 (з огляду на точку) і отримуємо рівень можливих вкладень - 60. Цифра також позамежна. Можна підійти з іншого боку. Рівень вкладень навряд чи буде більше 20. Ділимо 180 на 20, і отримуємо 9 символів. 8 символів (враховуючи точку) в десятковій системі - це десять мільйонів підрозділів. Таким чином, 180 символів в даному випадку достатньо, щоб описати надмірне число організацій та відділів, але недостатньо, щоб розмір сильно впливав на продуктивність бази даних. І це при тому, що ми розраховували найгірші випадки. Насправді, місткість ієрархії значно більше. Якщо кількість даних більше, то розмір Path можна збільшити. Але для цього довідника його розміру достатньо. І цього розміру вистачало для більшості бізнес-додатків, з якими я зустрічався.

    Отримання всіх нащадків вузла.

    Припустимо, ми збираємося отримати всі підрозділи, що входять до відділу «Роги і копита».

    За допомогою Path батька створюємо простий запит.        

    SELECT   * FROM DEPARTMENT WHERE Path LIKE '1 .1 .%'     

    Додавши до умови в операторі LIKE, ми вказали запиту вибрати всі записи, що мають Path довше, ніж у батьків.

    Такий запит також може бути побудований щодо даних батьківського вузла.        

    SELECT result .*   

    FROM DEPARTMENT parent INNER   JOIN DEPARTMENT result   

    ON (result.Path LIKE   parent.Path +'.%')   

    WHERE parent.NAME = 'Департамент «Роги»'     

    Отримання безпосередніх нащадків вузла

    Візьмемо попередній запит і додамо негативне умова для безпосередніх нащадків даного Path.        

    SELECT * FROM DEPARTMENT   

    WHERE Path LIKE '1 .1.% 'AND Path NOT LIKE '1 .1 .%.%'     

    У результаті ми отримаємо всі підлеглі елементи від вузла "Департамент« Роги »". Можна вибрати відразу декілька рівнів:        

    SELECT * FROM DEPARTMENT   

    WHERE Path LIKE '1 .1.% 'AND Path NOT LIKE '1 .1 .%.%.%'     

    Додавання нащадків.

    У даному випадку нам потрібно вставити запис по певному шляху з унікальним ідентифікатором Position. Створимо підлеглий елемент вузла із значенням Path 1.1. Унікальність ідентифікатора важлива тільки для самих нащадків. Тому обчислимо максимальне значення для нащадків даного батька та додамо до нього одиницю. Якщо на клієнті відомі сусідні елементи, і можна отримати ідентифікатор Position відразу, то запит не представляє складності:        

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    VALUES ('1 .1.4 ', 4,' Відділ   прокату копит ')     

    Якщо Position невідомий, то можна отримати його в запиті:        

    INSERT INTO DEPARTMENT (Path, Position, NAME)   

    SELECT '1 .1 '+'. '+ ISNULL (CAST (MAX (Position) 1 AS VARCHAR), '1'),   

    ISNULL (MAX (Position) 1, 1),   'Відділ прокату копит'   

    FROM DEPARTMENT   

    WHERE Path LIKE '1 .1.% 'AND Path NOT LIKE '1 .1 .%.%'             

    ПОПЕРЕДЖЕННЯ   

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

    Видалення вузла з нащадками

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

    DELETE FROM DEPARTMENT   

    WHERE Path LIKE '1 .1% '     

    За допомогою додаткової точки в аргументі оператора LIKE можна видалити всі дочірні елементи без батьківського вузла:        

    DELETE   FROM DEPARTMENT   

    WHERE   Path LIKE '1 .1 .%'     

    Має сенс побудувати тригер, який буде автоматично видаляти дочірні елементи:        

    CREATE TRIGGER DELETE_NODES_TR   

    ON DEPARTMENT AFTER DELETE   

    AS   

    DECLARE @ ParentPath VARCHAR (180)   

    BEGIN   

    SELECT @ ParentPath = Path FROM   deleted   

    DELETE FROM DEPARTMENT WHERE   Path LIKE @ ParentPath +'.%'   

    END     

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

    DELETE   FROM DEPARTMENT WHERE Path = '1 .1 '     

    Перенесення вузла

    Перенесення вузла - більш складна операція, ніж попередня. Для неї потрібно буде виконати дві команди оновлення. Наприклад, перенесемо вузол з Path 1.1, зробивши його дочірнім вузлом по відношенню до вузла 1.2. Першою командою ми перенесемо сам вузол:        

    UPDATE DEPARTMENT   

    SET Path =   

    (SELECT '1 .2. '+   ISNULL (CAST (MAX (D. Position) + 1 AS VARCHAR), '1 ')   

    FROM DEPARTMENT D   

    WHERE D. Path LIKE '1 .2.% '   AND D. Path NOT LIKE '1 .2 .%.%'),   

    Position =   

    (SELECT ISNULL (MAX (D. Position)   + 1, '1 ')   

    FROM DEPARTMENT D   

    WHERE D. Path LIKE '1 .2.% '   AND D. Path NOT LIKE '1 .2 .%.%')   

    WHERE Path = '1 .1 '     

    Другий командою ми відновимо всі ідентифікатори Path для дочірніх елементів:        

    UPDATE   DEPARTMENT SET Path = STUFF (Path, 1, 3, '1 .2.4 ')   

    WHERE   Path LIKE '1 .1 .%'     

    Так само, як і у випадку з видаленням, ми можемо побудувати тригер, який буде гарантовано адаптувати дочірні посилання, а також стежити за правильністю поля Position:        

    CREATE TRIGGER UPDATE_NODES_TR   

    ON DEPARTMENT   

    AFTER UPDATE   

    AS   

    DECLARE   

    @ OldParentPath VARCHAR (180),   

    @ NewParentPath VARCHAR (180),   

    @ ParentPosition INT,   

    @ RealParentPosition INT   

    BEGIN   

    IF UPDATE (Path)   

    BEGIN   

    SELECT @ OldParentPath = Path   FROM deleted   

    SELECT @ NewParentPath = Path,   @ ParentPosition = Position FROM inserted   

    - якщо поле Position некоректно, то оновлюємо його   згідно Path   

    SELECT @ RealParentPosition =   CAST (RIGHT (@ NewParentPath,   

    CHARINDEX ('.',   REVERSE (@ NewParentPath)) - 1) AS INT)      

    IF (@ RealParentPosition   <> @ ParentPosition)   

    UPDATE DEPARTMENT   

    SET Position =   @ RealParentPosition   

    WHERE Path = @ NewParentPath      

    - оновлюємо всі дочірні елементи   

    UPDATE DEPARTMENT   

    SET Path = STUFF (Path, 1,   LEN (@ OldParentPath), @ NewParentPath)   

    WHERE Path LIKE   @ OldParentPath +'.%'   

    END   

    END     

    Деякі додатки

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

    Якщо ви хочете сортувати послідовність безпосередньо підпорядкованих елементів, то можна ввести додаткову цифру, у якої буде лежати кількість цифр у елементі. Наприклад, для Position c номером 2 ідентифікатор у Path буде дорівнює 12, де 1 - кількість символів у ідентифікаторі. А якщо Position дорівнює 12, то ідентифікатор буде дорівнює 212. У цьому випадку сортування строкових даних буде збігатися з послідовністю числових, і ми отримаємо повністю сортованого Path.

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

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

    Список літератури

    Для підготовки даної роботи були використані матеріали з сайту http://www.rsdn.ru/

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

     

     

     

     

     

     

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