Дървета в SQL
Дървото е специален вид насочен граф. Графите са структури от данни, състоящи се от възли, свързани с дъги. Всяка дъга показва еднопосочна връзка между два възела. В организационна диаграма възлите са служители и всяка дъга описва йерархия. В спецификацията на материалите възлите са модули (евентуално показани преди отделни части), а дъгите описват връзка „направено от“.
Върхът на дървото се нарича корен. В организационна диаграма това е най-големият шеф; в спецификацията на материалите това е сглобената част. Двоично дърво е дърво, в което един възел може да има най-много две деца; Като цяло, едно n-измерно дърво е такова, в което един възел може да има не повече от n дъщерни възела.
Възлите на дървото, които нямат поддървета, се наричат листа. В списъка с материали това са минималните части, на които частта може да бъде разглобена. Наследници или деца на родителски възел са всички възли в поддървото, което има родителски възел като свой корен.
Дърветата често се изобразяват като диаграми. (Вижте фигура 1) Друг начин за представяне на дървета е да ги покажете като вложени набори (вижте фигура 2); Това е основата за моето вложено представяне на дървета в SQL.
В SQL всяка връзка е изрично описана от данните.Типичен начин за представяне на дървета е да се постави матрица на съседство в таблица. Тези. една колона е родителският възел, а другата колона в същия ред е дъщерният възел (двойката представлява дъга в графиката). Например, разгледайте организационната схема на компания с шестима служители:
Този модел има предимства и недостатъци. PRIMARY KEY е emp, но колоната на шефа е функционално зависима от него, следователно имаме проблеми с нормализирането.РЕФЕРЕНЦИИТЕ няма да ви дадат възможност да посочите като шеф, който не е служител. Но какво се случва, когато „Джери“ промени името си на „Джералдо“, за да получи телевизионно токшоу? Трябва също така да направите каскадни промени в линиите „Бърт“ и „Чък“.
Друг недостатък на този модел е, че е трудно да се определи пътя. За да намерите името на шефа за всеки служител, използвайте самосъединяваща се заявка като:
Но тук нещо липсва. Тази заявка ви дава само непосредствени ръководители на персонала. Шефът на вашия шеф също има власт над вас и така нататък нагоре в дървото. За да покажете две нива в дърво, трябва да напишете по-сложна заявка за самосъединяване като:
За да отидете повече от две нива по-дълбоко в дървото, просто разгънете шаблона:
За съжаление, нямате представа колко дълбоко е дървото, така че трябва да продължите да разширявате тази заявка, докато не получите празен набор.
Листата нямат потомство. В този модел те са доста лесни за намиране: Това са служители, които не са шефове на никой друг в компанията:
Коренът на дървото на шефа е NULL:
Истинските проблеми възникват, когато се опитвате да изчислите стойности нагоре и надолу в дървото. Като упражнение напишете заявка, обобщаваща заплатата на всеки служител и неговите/нейните подчинени; резултат:
Модел на множество дървета.
Друг начин за представяне на дървета е да ги покажете като вложени набори. Това е по-подходящ модел, т.к. SQL е език, ориентиран към множество. Коренът на дървото е множеството, съдържащо всички други множества, а връзката родител-дете се описва от факта, че множеството от потомци принадлежи на множеството на прародителя.
Има няколко начина за преобразуване на организационна диаграма във вложени.комплекти. Един от начините е да си представите, че движите обекта "овали" вътре в неговите родители, като използвате ръбовите линии като въжета. Коренът е най-големият овал и съдържа всички останали възли. Листата са най-вътрешните овали, не съдържат нищо вътре, а гнезденето съответства на йерархични връзки. Това е естествено представяне на модела на спецификацията, тъй като крайният блок е направен физически от вложени компоненти и се анализира на отделни части.
Друг подход е да си представите малък червей, който пълзи по „възлите и дъгите“ на едно дърво. Червеят започва от върха, от корена, и прави пълно пътуване около дървото.
Но сега нека си представим по-силен червей с брояч, който започва от едно. Когато червеят пристигне във възел, той поставя число в клетката от страната, която е посетил, и увеличава брояча. Всеки възел ще получи две числа, едно за дясната страна и едно за лявата страна.
Това дава предвидими резултати, които можете да използвате за формиране на заявки. Таблицата с персонала изглежда така, с числа отляво и отдясно във формата:
Коренът винаги има 1 в лявата колона и два пъти броя на възлите (2*n) в дясната колона. Това е лесно за разбиране: червеят трябва да посети всеки възел два пъти, веднъж от лявата страна и веднъж от дясната страна, така че крайният брой трябва да е два пъти броя на възлите в цялото дърво.
В модела на вложен набор разликата между лявата и дясната стойност на листата винаги е 1. Представете си червей, който се върти около лист, докато пълзи нагоре по дърво. Следователно можете да намерите всички листа със следната проста заявка:
Можете да използвате този трик, за да ускорите заявките: след това изградете уникален индекс в лявата колонапренапишете заявката, за да се възползвате от индекса:
Причината за увеличаването на производителността е, че SQL може да използва индекс в лявата колона, когато не се използва в израз. Не използвайте (ляво - дясно) = 1, защото това се възползва от индекса.
В модела на вложени и набори, пътищата се показват като вложени набори, които са представени от числа на вложен набор и предикати BETWEEN. Например, за да определите всички шефове на даден служител, ще напишете:
Колкото по-голяма е височината, толкова по-надолу в йерархията е шефът от служителя. Моделът на вложен набор използва факта, че всеки съдържащ набор е с по-голям размер (където размер = (дясно - ляво)) от наборите, които съдържа. Очевидно коренът винаги ще има най-големия размер.
Нивото, броят на дъгите между два дадени възела, е доста лесно за изчисляване. Например, за да намерите нивата между даден работник и мениджър, можете да използвате:
(COUNT(*) - 1) се използва за премахване на двойния индекс на самия възел като брат или сестра, тъй като възелът е нула нива, премахнати от себе си.
Можете да създавате други заявки от този шаблон. Например, за да намерите общите шефове на двама служители, обединете пътища и намерете възли, които имат (БРОЙ(*) > 1). За да намерите най-близките общи предшественици на два възела, обединете пътища, намерете възли, които имат (COUNT(*) > 1), и изберете тези с най-малка дълбочина.