СОВЕТЫ

Древовидные структуры в SQL

По материалам статьи Joe Celko на intelligententerprise.com " Trees in SQL"
Перевод: Сергея Снисаренко

Обзор некоторых общих вопросов, касающихся древовидных структур и иерархии в SQL.

Эта тема уже рассматривалась мной ранее, но она заслуживает повторения. В специализированных конференциях я встречал слишком много вопросов о древовидных структурах и иерархии в SQL. В литературе по SQL приводится стандартная модель древовидной структуры, которая называется список смежных вершин графа и выглядит следующим образом:

CREATE TABLE Personnel

(emp CHAR(10) NOT NULL PRIMARY KEY,

boss CHAR(10) DEFAULT NULL REFERENCES Personnel(emp),

salary DECIMAL(6,2) NOT NULL DEFAULT 100.00);

Personnel emp	boss	salary
'Albert'	'NULL'	1,000.00
'Bert'	'Albert'	900.00
'Chuck'	'Albert'	900.00
'Donna'	'Chuck'	800.00
'Eddie'	'Chuck'	700.00
'Fred'	'Chuck'	600.00

Таблица 1. Список смежных вершин графа

Другим способом представления древовидной структуры являются вложенные множества. Поскольку SQL является языком, предназначеным для работы со множествами, то эта модель является более предпочтительной, чем стандартный пример списка смежных вершин графа, который более часто встречается в литературе. Давайте создадим тестовую таблицу Personnel, не обращая пока внимания на поля lft и rgt:

CREATE TABLE Personnel

(emp CHAR(10) NOT NULL PRIMARY KEY,

  lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),

  rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),

  CONSTRAINT order_okay CHECK (lft < rgt) );

Эта проблема часто описывается в учебниках с помощью поля для Сотрудника (Personnel emp) и одного из его Начальников (Boss). Следующая таблица (Таблица 2) - за исключением полей lft и rgt - в теории графов называется список смежных вершин графа или пары вершин графа, смежные друг другу.

Personnel emp	ift	rgt
'Albert'	1	12
'Bert'	2	3
'Chuck'	4	11
'Donna'	5	6
'Eddie'	7	8
'Fred'	9	10

Таблица 2. Вложенные множества

Структура организации может быть представлена в виде направленного графа, как показано на рис.1

           Albert (1, 12)
                ¦
   -------------+---------------
   ¦                           ¦
   ¦                           ¦
Bert (2, 3)                Chuck (4, 11)
                               ¦
   ---------------------------------------------------------
   ¦                           ¦                           ¦
   ¦                           ¦                           ¦
Donna (5, 6)               Eddie (7, 8)                 Fred (9, 10)

Таблица 1 является денормализованной по нескольким направлениям. Мы моделируем структуру персонала и организации в одной таблице. Ради экономии дискового пространства представим себе, что имя сотрудника является также названием его должности и что мы имеем еще одну таблицу, которая содержит информацию о сотрудниках и занимаемых ими должностях.

Еще одной проблемой, связанной с моделью "Список смежных вершин графа" является то, что поля Начальник (Boss) и Сотрудник (Personnel emp) содержат данные одинакового вида (имя сотрудника) и поэтому эти данные должны располагаться в одном и том же поле нормализованной таблицы. Для подтверждения того, что эти данные не нормализованы, предположим, что "Chuck" изменил свое имя на "Charles"; вы должны изменить его имя в обеих полях и в нескольких местах. По определению, в нормализованной таблице одна сущность должна встречаться лишь однажды и только в одном месте.

Последней проблемой является то, что "Список смежных вершин графа" не является подчиненной (субординационной) моделью. Полномочия передаются сверху вниз в иерархическом порядке, но если я уберу сотрудника по имени "Chuck", я разорву всю его подчиненность от сотрудника по имени "Albert". В некоторых случаях (например, для трубопроводов) это справедливо, но в нашем случае мы не предполагаем такой ситуации.

Чтобы изобразить древовидную структуру в виде вложенных множеств, заменим вершины графа овалами, где подчиненные овалы вложены один в другой. Основание дерева будет представлено самым большим овалом, который содержит все остальные овалы. Концевые вершины будут представлены самыми внутренними овалами, не содержащими внутри никаких других овалов, а вложенность будет показана иерархическими взаимоотношениями. Поля rgt и lft (я не использую зарезервированные слова RIGHT и LEFT) - это именно то, что показывает вложенность.

Если эта образная модель не работает, то представьте себе маленького червя, ползущего вдоль дерева против часовой стрелки. Каждый раз, когда он достигает правую или левую сторону вершины, он нумерует ее. Червь останавливается после того, когда он обойдет вокруг всего дерева и вернется назад к основанию.

Эта модель натуральным образом показывает как увеличивается количество частей, потому что последняя сборка состоит из вложенных сборок, которые, в конечном итоге, состоят из отдельных частей.

Теперь мы видим, что поле Начальник (Boss) является избыточным и денормализованным, следовательно оно может быть удалено. Обратите также внимание на то, что древовидная структура может быть размещена в одной таблице, а вся информация о вершинах графа может быть помещена в другую таблицу. Вы можете связать обе таблицы между собой по номеру сотрудника.

Для преобразования графа в модель вложенных множеств вспомните о маленьком червячке, ползущем вдоль дерева. Червь начинает двигаться сверху - от основания - и обползает вокруг всего дерева. Когда он приходит к вершине, он присваивает значение стороне, которую он посещает и увеличивает значение счетчика на единицу. Каждая вершина получает два значения - одно для правой стороны и одно для левой. (Специалисты называют это модифицированным алгоритмом обхода вершин графа в прямом порядке.) И в заключение, удалим за ненадобностью поле "Personnel.Boss", которое представляло ребро графа.

Это дает нам некоторые предсказуемые результаты, которые мы можем использовать при построении запросов. Основание всегда можно представить в виде:
(left = 1, right = 2 * (SELECT COUNT(*) FROM TreeTable));
для вершин всегда справедливо (left + 1 = right); условие BETWEEN определяет поддерево и т.д. Ниже представлены некоторые базовые запросы, которые могут быть вам полезны:

1. Найти сотрудника и всех его начальников, независимо от глубины вложения.

 SELECT P2.*
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = :myemployee;

2. Найти сотрудника и всех его подчиненных. (Этот запрос симметричен первому.)

 SELECT P1.* -- (В оригинале опечатка: SELECT P2.*)
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P2.emp = :myemployee;
 

3. Добавьте GROUP BY и обобщенные функции к этим базовым запросам и вы получите иерархические отчеты. Например, суммарный лимит заработной платы, которой распоряжается каждый сотрудник:

SELECT P2.emp, SUM(S1.salary)
   FROM Personnel AS P1, Personnel AS P2,
        Salaries AS S1
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
    AND P1.emp = S1.emp
  GROUP BY P2.emp;
 

4. Найти уровень (глубину вложения) каждой вершины, что дает возможность распечатать древовидную структуру как листинг с отступами.

SELECT COUNT(P2.emp) AS indentation, P1.emp
   FROM Personnel AS P1, Personnel AS P2
  WHERE P1.lft BETWEEN P2.lft AND P2.rgt
  GROUP BY P1.emp
  ORDER BY P1.emp;  -- (В оригинале опечатка: ORDER BY P1.lft)
 

BEGIN
DECLARE right_most_sibling INTEGER;

SET right_most_sibling
    = (SELECT rgt
         FROM Personnel
        WHERE emp = :your_boss);

UPDATE Personnel
   SET lft = CASE WHEN lft > right_most_sibling
                  THEN lft + 2
                  ELSE lft END,
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + 2
                  ELSE rgt END
 WHERE rgt >= right_most_sibling;

INSERT INTO Personnel (emp, lft, rgt)
VALUES ('New Guy', right_most_sibling,
                  (right_most_sibling + 1))
END;
 

6. Для преобразования модели "Список смежных вершин графа" в модель вложенных множеств можно использовать a push down stack алгоритм. Предположим, что мы имеем следующую таблицу:

-- Древовидная структура содержащая модель "Список смежных вершин графа"

CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
 boss CHAR(10));

INSERT INTO Tree
SELECT emp, boss FROM Personnel;

-- Stack starts empty, will holds the nested set model
-- Изначально стек пустой, он будет содержать модель вложенных множеств
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
 emp CHAR(10) NOT NULL,
 lft INTEGER,
 rgt INTEGER);

BEGIN ATOMIC
DECLARE counter INTEGER;
DECLARE max_counter INTEGER;
DECLARE current_top INTEGER;

SET counter = 2;
SET max_counter = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;

INSERT INTO Stack
SELECT 1, emp, 1, NULL
  FROM Tree
 WHERE boss IS NULL;

DELETE FROM Tree
 WHERE boss IS NULL;

WHILE counter <= (max_counter - 2)
LOOP IF EXISTS (SELECT *
                   FROM Stack AS S1, Tree AS T1
                  WHERE S1.emp = T1.boss
                    AND S1.stack_top = current_top)
     THEN
     BEGIN -- push when top has subordinates, set lft value
           -- вершина имеет подчиненные вершины,
           -- заносим новое значение lft в стек
       INSERT INTO Stack
       SELECT (current_top + 1), MIN(T1.emp), counter, NULL
         FROM Stack AS S1, Tree AS T1
        WHERE S1.emp = T1.boss
          AND S1.stack_top = current_top;

        DELETE FROM Tree
         WHERE emp = (SELECT emp
                        FROM Stack
                       WHERE stack_top = current_top + 1);

        SET counter = counter + 1;
        SET current_top = current_top + 1;
     END
     ELSE
     BEGIN  -- pop the stack and set rgt value
            -- выталкиваем значение из стека и определяем значение rgt
       UPDATE Stack
          SET rgt = counter,
              stack_top = -stack_top -- pops the stack
        WHERE stack_top = current_top
       SET counter = counter + 1;
       SET current_top = current_top - 1;
     END IF;
 END LOOP;
END;
 

Несмотря на то, что эта процедура работает, вы можете переписать ее на языке, позволяющем работать с массивами, вместо того, чтобы придерживаться чистого SQL.

Копирование базы данных MS SQL Server

По материалам статьи Rahul Sharma на sqlservercentral.com: " Copying a Database from Server to Server"
Перевод: Александра Гладченко

В этой статье автор рассматривает несколько возможных вариантов копирования баз данных MS SQL Server с одного сервера на другой.

Метод 1: самый быстрый способ копирования - отсоединение базы данных от исходного сервера и затем прикрепление вместе с журналом на нужный сервер.

Отсоедините базу данных на исходном сервере (Измените, соответственно, имя базы данных):

Use Master
GO
Exec sp_detach_db 'database_name', 'true'
GO

sp_detach_db отсоединяет базу данных от исходного сервера (у неё два параметра: @dbname, который является именем базы данных и @skipchecks, который является указанием для обновления статистики) и указав значение 'true' для второго параметра (@skipchecks) этой хранимой процедуры, что бы удостоверится в том, что если модификация статистики не была выполнена перед отсоединением базы данных от сервера, она обновится после присоединения, что потребует некоторого времени. Скопируйте данные и журналы из каталога Data исходного сервера в каталог данных на новом сервере. Удостоверитесь, что Вы не имеете точно таких же баз данных на сервере адресата.... Если это так, отключите их.
Прикрепите данные и журналы на новый сервер. Выполните на этом сервере:

Use Master
GO
PRINT 'Attaching Database'
EXEC sp_attach_db @dbname = 'database_name',
@filename1 = 'c:\mssql7\data\database_name.mdf', -- Это путь к файлу данных
@filename2 = 'd:\mssql7\data\database_name_log.ldf' -- Это путь к журналу

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

declare @login sysname , @password sysname
declare sourcelogins cursor for
select name , password
from sourceserver.master.dbo.syslogins
where isntname = 0 and charindex( 'repl_' , name ) = 0 and
charindex( 'distributor' , name ) = 0 and name != 'sa'
open sourcelogins
while ( @@fetch_status = 0)
begin
fetch sourcelogins into @login , @password
exec sp_addlogin @login , @password , @encryptopt = 'skip_encryption'
end
close sourcelogins
deallocate sourcelogins
go

При откреплении и прикреплении баз данных, я столкнулся с ещё одной проблемой, кроме потери связи пользователей и их логинов, описанной выше. Я обнаружил, что статистика останется не эффективной, если Вы выполните sp_updatestats на прикрепляемой базе данных. Так, я рекомендовал бы обновить статистику после того, как Вы уже прикрепили эту базу. Или воспользуйтесь альтернативным вариантом: когда Вы открепляете базу данных, удостоверьтесь, что второй параметр установлен в Ложь, что заставит статистику обновиться, и Вам не придётся обновлять её позже на новом сервере. Любой из этих путей прекрасно работает.
Этот метод также великолепно работает, если необходимо переместить базы данных на диск и затем прикрепить их на другой сервер, который не находится в сети. Также, это - очень быстрый путь копирования баз данных с сервера на сервер. Не забудьте прикрепить копируемую базу назад на исходный сервер, как только Вы скопировали данные и журналы с исходного сервера на сервер адресат.

Метод 2: Использование DTS.

DTS очень часто используется для перемещения баз данных с сервера на сервер. Вы можете использовать мастер экспорта/импорта DTS (SQL 7.0 и 2000). Мастер может использоваться для копирования схем, объектов (хранимые процедуры, представления и триггеры и т.д.), данных и также логинов. Или Вы можете использовать DTS Designer и создать задачу перемещения базы данных и задачу перемещения логинов (доступно только для SQL 2К). Также, Вы можете использовать мастер копирования баз данных (Copy Database Wizard), чтобы решить задачу перемещения базы (доступно только для SQL 2К). DTS - довольно мощный инструмент и если Вы его пока не использовали, Вы лишаете себя многих функциональных возможностей и лёгкости, с которой Вы могли бы решать сложные задачи.
В случае если Вы ищете хорошую ссылку на DTS, я предложил бы Вам почитать:
http://msdn.microsoft.com/library/default.asp?URL=/library/techart/dts_overview.htm

Метод 3: Создайте схему и механизм переноса данных, использующий bcp/bulk insert.

Создайте схему на сервере приёмнике данных, если Вы уже имеете скрипт для создания схемы и затем используете bcp или bulk insert, чтобы скачать данные. Оба операции - нерегистрируемые, так что они отработают очень быстро. Главное различие между bcp и bulk insert - это то, что bulk insert не может экспортировать данные, а bcp может.
Вы можете использовать bcp, чтобы экспортировать данные в плоский файл и затем импортировать данные в новую базу из плоского файла, используя bcp или bulk insert. Даже при том, что bulk insert является быстрым способом закачки данных, он имеет большое количество ограничений.

Метод 4: Традиционный путь: Backup и Restore.

Сделайте полную копию базы данных, и затем восстановите её на новом сервере.

Метод 5: Использование распределённых запросов.

Вы сначала должны создать схему на сервере приёмнике данных, используя ваши скрипты создания схем. После этого Вы можете организовать связанный сервер и написать инструкции вставки, которые будут вставлять данные из источника на новый сервер, используя функции openrowset и openquery для запросов к связанным серверам. Вы должны удостовериться, что foreign key и check constraints отключены до того, как Вы начнёте закачивать данные и затем подключить их, когда всё будет сделано. Этот метод самый медленный из всех упомянутых в этой статье. Зато, с помощью него можно переносить данные на SQL Server из гетерогенных источников, например: Oracle, Sybase, DB2 и т.д.

ССЫЛКИ НА СТАТЬИ

Проблема создания современных бизнес-приложений СУБД
Автор: Андреев А. М., Березкин Д. В., Кантонист.
Одна из важнейших целей современного информационного бизнеса - создание информационной системы, охватывающей виртуальное предприятие с доступом к архиву документов, управление бизнес-процессами, получение адекватной инфомации для поддержки принятия решений, планирование, мониторинг контактов с внешним миром. Абсолютно обязательно условие обеспечить доступ работника к ресурсам виртуального предприятия независимо от того, где он находится - на рабочем месте, дома, в командировке. Такая система, помимо всего прочего, должна обладать простыми, но эффективными средствами администрирования... [подробнее]
Доступ к данным средствами ASP.NET
Автор: А. Гладченко.
Доступ к базам данных из прикладных программ ASP.NET является одной из современных методик представления данных посетителям Web сайтов. ASP.NET делает это проще чем её предшественники, особенно при обращениях к базам данных, и обеспечивает поддержку управления данными в базе. В целях обеспечения высокой эффективности таких приложений, рекомендуется использование баз данных, поддерживающих SQL запросы и работающие с приложениями Web серверов. Поэтому, обращение к SQL базам данных будет первой нашей задачей... [подробнее]
Загрузка XML в объект
Автор: Андрей Чудин.
После того, как мы рассмотрели возможность превода данных объекта в XML следует перейти к следующей задаче. Задача состоит в реализации обратного процесса, а именно - загрузки XML данных в объект... [подробнее]
Crystal Reports 8.0 — бизнес-информация во всемирной паутине
Автор: Денис Матвеев.
Очень часто корпоративные пользователи хотят иметь возможность не только работать с Web-приложениями, но и получать доступ к различным отчетным формам, не покидая браузер. Существует огромное количество технологий создания подобных отчетов, но в ряде случаев либо получаемые документы не полностью удовлетворяют предъявляемым к ним требованиям, либо процесс их создания слишком трудоемкий и занимает много времени, что мешает быстрой разработке систем, применяющих такие отчеты. Поэтому необходим инструмент, который позволит быстро создавать документы любой сложности, работающие с данными из корпоративных источников информации, и распространять их без серьезных затрат на программирование. Одним из средств решения таких задач является профессиональный генератор отчетов Crystal Reports версии 8.0 производства компании Crystal Decisions (ранее Seagate Software), который стал стандартом де-факто для многих корпоративных систем обработки и хранения информации... [подробнее]

Новые технические статьи Microsoft

INF: How to Work with More Than 64,000 Children Per Parent (Q303969)
INF: Disaster Recovery Articles for Microsoft SQL Server (Q307775)
INF: File Size Limitations For Use of Archive/Restore for OLAP (Q303415)
FIX: "Unable To Run The Script Files" Error Message Occurs with Desktop Engine Modification (Q306491)
INF: Use of Multiple Hierarchies Versus the Creation of Separate Hierarchies (Q306408)
INFO: SQL Server CE Performance Tips and Efficient Memory Handling (Q274112)
PRB: Scheduled Tape Backup Waits Indefinitely if No Tape is in Drive (Q281665)
FIX: Full-Text Search Queries with CONTAINS Clause Search Across Columns (Q294809)
HOW TO: Prebuild a SQL Server CE Database (Q301217)
Support WebCast: Understanding INSTEAD OF Triggers in Microsoft SQL Server 2000
Support WebCast: Microsoft SQL Server 2000 Windows CE Edition Overview and Programming
Support WebCast: Troubleshooting Distributed Queries in SQL Server 7.0
Support WebCast: Microsoft SQL Server 2000 Log Shipping
Support WebCast: Multi-instancing in Microsoft SQL Server 2000
Support WebCast: Microsoft SQL Server 2000: Merge Replication Enhancements
Support WebCast: Microsoft SQL Server 2000: New XML Features
Support WebCast: Analyzing Optimal Compiled Plan Caching
Support WebCast: Understanding User-Defined Functions in Microsoft SQL Server 2000
Support WebCast: Introduction to Microsoft SQL Server 2000 Clustering
Support WebCast: How to Effectively Use SQL Server Profiler
Support WebCast: Effective Indexing and Statistics with SQL 2000
Support WebCast: Implementing ADOX in Jet and SQL Server Applications
Support WebCast: How to Collect and Analyze Performance Data in Microsoft SQL Server
Support WebCast: Microsoft SQL Server 7.0 Common Problems and Resolutions
Support WebCast: Optimizing SQL Server 7.0 on Windows 2000 Advanced Server and Windows 2000 Datacenter Server
Support WebCast: Troubleshooting Microsoft SQL Mail
Support WebCast: Accessing and Manipulating Data in Microsoft SQL Server 2000 Databases by Using SQLXML UpdateGrams
Support WebCast: Inside Microsoft SQL Server 6.5 Replication
Support WebCast: Cascading Referential Integrity Constraints in SQL Server 2000
Support WebCast: SQL Server 7.0 Full-Text Search and Basic Troubleshooting Methods
Support WebCast: SQL Server 2000 Profiler: What's New and How to Effectively Use It
Support WebCast: SQL Server 2000 Database Recovery: Backup and Restore
Support WebCast: SQL Server 7.0: Features of Data Transformation Services
PRB: Error When You Implement Nested Transaction with OLE DB Provider for SQL Provider (Q306649)
INF: How to Change Network IP Addresses on a Virtual SQL Server (Q244980)
FIX: Distribution Agent Ignores Quoted Identifier Option on Initial Sync to Oracle Subscribers (Q278509)
FIX: SQL Server ODBC Driver Reuses Incorrect Parameter Length (Q280294)
INF: List of Bugs Fixed in SQL Server 2000 Service Pack 1 (1 of 2) (Q290212)
HOWTO: Configure MSDTC in a Windows 2000 Cluster Environment (Q290624)
PRB: Subquery with Non-existent Column Returns Results Instead of Error Message (Q298674)
FIX: SQL Server Performance Condition Alerts do not Fire After You Install SQL Server 2000 Service Pack 1 (Q303005)
FIX: SP1 Regression: Table Scan Chosen Over Index Seek for INSERT/SELECT Statement Against the Same Table (Q306374)
FIX: ISQLWCE for PocketPC SH3 Has Incorrect MFC and OLE DLLs (Q292616)
BUG: Error Message 7355 "..Inconsistent metadata for a column" Occurs When You Use a Linked Server (Q306401)
FIX: Reinstall with Long Command May Cause Setup to Fail (Q306488)
BUG: Objects May Fail to Retain Quoted Identifier Setting When You Use SQL-DMO to Create or Alter Objects (Q306334)

ФОРУМ SQL.RU: САМЫЕ ПОПУЛЯРНЫЕ ТОПИКИ НЕДЕЛИ

Refresh таблиц или аналог IBEvents для MSSQL
Как записать в файл с помощью TSQL?
Просмотр логов (sql инструкций) ? <
ServerName
Туплю..... Помогите!!!
Нумерация полей в таблице
Выбор случайной записи из таблицы
Может не стоит мучатся с SQLMail? Я написал свою прогу для посылки почты.Неправ?
help ! create the copy of db

ФОРУМ SQL.RU: ВОПРОСЫ ОСТАЛИСЬ БЕЗ ОТВЕТА

Русский текст в таблице <
Аудит в SQL
mssql php unicode
Различия версий SQL 2000
Проблема с русским при переходе с SQL 6.5 на SQL 2000
репликация баз данных .nsf Lotus и MS SQL <
Разрушительный сбой???
Проблемы с украинской 'і' при экспорте в dbf.