3.4: Додатки та міграція даних

Last updated
Save as PDF

Page ID: 66399

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Ми говорили про те, як множинні функтори на схемі можна розуміти як заповнення цієї схеми даними. Але між схемами є і функтори. Коли два види функторів складаються, дані переносяться. Це найпростіша форма міграції даних; більш складні способи міграції даних походять від використання суміжних з'єднань. Все вищесказане є предметом даного розділу.

Відтягування даних вздовж функтора

Для початку ми перенесемо дані між схемою індексації графа Gr і схемою циклу, яку ми називаємо DDS, показаної нижче

$Знімок екрана 2021-01-12 в 4.37.23 PM.png$

Почнемо з запису зразка екземпляра I: DDS → Встановити на цій схемі:

$Знімок екрана 2021-01-12 в 4.37.59 PM.png$

Ми називаємо схему DDS стояти для дискретної динамічної системи. Дійсно, ми можемо думати про дані в DDS -екземпляр Eq. (3.65) як перерахування станів і рухів детермінованої машини: у кожен момент часу машина знаходиться в одному з перерахованих станів, і враховуючи машину в одному з станів, в наступну мить вона переходить до однозначно визначеного наступного держава.

Наша мета - перенести дані в еквалайзері (3.65) до даних про Gr; це дасть нам дані графіка і таким чином дозволить нам візуалізувати нашу машину.

Ми будемо використовувати функтор, що з'єднує ці схеми, щоб переміщати дані між ними. Читач може створити будь-який сподобався їй функтор, але ми будемо використовувати певний функтор F: Gr → DDS для міграції даних таким чином, який має сенс для нас, авторів. Тут ми малюємо F, використовуючи кольори, щоб, сподіваємось, допомогти зрозуміти:

$Знімок екрана 2021-01-12 о 4.38.37 PM.png$

Функтор F надсилає обидва об'єкти Gr до об'єкта 'State' DDS (як треба). На морфізмах він посилає морфізм «джерела» до морфізму ідентичності на «державі», а «цільовий» морфізм до морфізму «наступний».

Зразок екземпляра бази даних на DDS було надано в еквалайзері (3.65); нагадаємо, що це функтор I: DDS → Set. Отже, тепер у нас є два функтори наступним чином:

$\mathbf{G r} \stackrel{F}{\longrightarrow} \mathbf{D D S} \stackrel{I}{\longrightarrow} \text { Set. }$(3,66)

Об'єкти в Gr надсилаються F об'єктам у DDS, які надсилаються I об'єктам у Set, які є множинами. Морфізми в Gr посилаються F на морфізми в DDS, які відправляються I на морфізми в Set, які є функціями. Це визначає складений функтор F; I: Gr → Множина. І F, і я поважаю ідентичності та склад, тому F; Я теж. Таким чином, ми отримали екземпляр на Gr, тобто ми перетворили нашу дискретну динамічну систему з Eq. (3.65) у граф! Що це за графік?

Наприклад, на Gr, нам потрібно заповнити таблицю зі стрілками та таблицю Vertex. Обидва вони надсилаються F до держави, тому давайте заповнимо обидва рядками держави в еквалайзері (3.65). Аналогічно, оскільки F надсилає «джерело» до ідентичності та надсилає «target» на «next», ми отримуємо такі таблиці:

$Знімок екрана 2021-01-12 в 4.46.55 PM.png$

Тепер, коли у нас є графік, ми можемо його намалювати.

$Знімок екрана 2021-01-12 в 4.49.11 PM.png$

Кожна стрілка позначена своєю вершиною джерела, ніби кажучи: «Те, що я роблю далі, визначається тим, ким я є зараз».

Вправа 3.67.

Розглянемо функтор G: Gr → DDS, заданий шляхом надсилання «source» на «next» та надсилання «target» до ідентифікатора на «State». Перенесіть ті ж дані, які називаються I в Eq. (3.65), за допомогою функтора G. Запишіть таблиці і намалюйте відповідний графік. ♦

Ми посилаємося на вищевказану процедуру - в основному просто складаючи функтори, як у Eq. (3.66), як «витягування даних вздовж функтора». Ми просто тепер витягнув назад дані я вздовж функції F.

Визначення: 3.68.

Нехай C і D будуть категоріями, а F: C → D - функтором. Для будь-якого множинного функтора I: D → Set ми посилаємося на складений функтор F; I: C → Set як відкат I вздовж F.

З огляду на природне перетворення α: I ⇒ J, відбувається природне перетворення$α_{F}$: F; I ⇒ F; J, чия складова (F; I) (c) → (F; J) (c) для будь-якого c$\in$ Ob (C) задається ($α_{F}$)$_{c}$ :=$α_{Fc}$

$Знімок екрана 2021-01-12 о 5.10.51 PM.png$

Це використовує дані F для визначення функтора ↑ F: D- Inst → C- Inst.

Зауважте, що термін «відкат» також використовується для певного роду лімітів, докладніше див. Примітка 3.100.

ад'юнкції

У розділі 1.4 ми розглянули з'єднання Галуа, які є доповненнями між попередніми замовленнями. Тепер, коли ми визначили категорії і функтори, ми можемо обговорити ад'юнкції в цілому. Релевантність для баз даних полягає в тому, що функція міграції даних ⟩ З Defi- nition 3.68 завжди має два власних суміжні: лівий суміжний який ми позначаємо σ і правий суміжний який ми позначаємо.

Нагадаємо, що примикання між попередніми порядками P і Q - це пара монотонних карт f: P → Q і g: Q → P, які є майже зворотними: ми маємо

f (p) ≤ q якщо і тільки тоді, коли p ≤ g (q). (3,69)

Нагадаємо з розділу 3.2.3, що в попередньому порядку P домашня множина P (a, b) має один елемент, коли a ≤ b, і ніяких елементів інакше. Таким чином, ми можемо перефразувати Eq. (3.69) як ізоморфізм множин Q (f (p), q)$\cong$ P (p, g (q)): або обидва є одноелементними множинами, або обидва є 0-елементними множинами. Це говорить про те, як визначити ад'юнкції в загальному випадку.

Визначення: 3.70.

Нехай C і D будуть категоріями, а L: C → D і R: D → C - функторами. Ми говоримо, що L ліворуч примикає до R (і що R праворуч примикає до L), якщо для будь-якого$\in$ c C і $\in$d D існує ізоморфізм хом-множин

$\alpha_{c, d}: \mathcal{C}(c, R(d)) \stackrel{\cong}{\rightarrow} \mathcal{D}(L(c), d)$

що є природним в c і d. $^{8}$

З огляду на морфізм f: c → R (d) в C, його зображення g :=$α_{c,d}$ (f) називається його спорідненістю. Аналогічно, мат g: L (c) → d дорівнює f.

Для позначення примикання пишемо L R, або на діаграмах,

$Знімок екрана 2021-01-12 о 5.12.21 PM.png$

з ⇒ в напрямку лівого примикання.

Приклад 3.71.

Нагадаємо, що кожен передзамовлення Р можна розглядати як категорію. Зв'язки Галуа між попередніми замовленнями і ад'юнкціями між відповідними категоріями - це точно одне і те ж.

Приклад 3.72.

Нехай B$\in$ Ob (Set) буде будь-який набір. Існує прив'язка під назвою «каррі Б», після логіка Хаскелла Каррі:

$Знімок екрана 2021-01-12 о 5.17.23 PM.png$

Абстрактно ми пишемо це, як зліва, але це означає, що для будь-яких множин A, C є природний ізоморфізм, як справа.

Щоб пояснити це, нам потрібно поговорити про експоненціальні об'єкти в Set. Припустимо, що B і C - множини. Тоді множина функцій B → C також є множиною; позначимо його C B. Це написано таким чином, тому що якщо C має 10 елементів, а B має 3 елементи, то C B має 103 елементи, і в цілому для будь-яких двох скінченних множин$C^{B}$ | | = |C |$_{|B|}$.

Ідея каррі полягає в тому, що задані множини A, B і C існує відповідність один до одного між функціями (A × B) → C і функціями A →$C^{B}$. Інтуїтивно, якщо у мене є функція f двох змінних a, b, я можу «відкласти» введення другої змінної: якщо ви дасте мені просто a, я поверну функцію B → C, що чекає на вхід B. Це каррі варіант f. Як можна здогадатися, існує формальний зв'язок між експоненціальними об'єктами та тим, що ми називали hom-елементами b -o c у визначенні 2.79.

Вправа 3.73.

У прикладі 3.72 ми розглянули примикання між функторами − × B і$(−)^{B}$. Але ми тільки сказали, як ці функтори працювали над об'єктами: для довільного набору X вони повертають множини X × B і X$^{B}$ відповідно.

$Знімок екрана 2021-01-12 о 5.22.52 PM.png$

З огляду на морфізм f: X → Y, який морфізм повинен повернути − × B: X × B → Y × B?
З огляду на морфізм f: X → Y, який морфізм повинен (−)$^{B}$:$^X_{B}$ →$Y^{B}$ повернутися?
Розглянемо функцію +:$\mathbb{N}$ ×$\mathbb{N}$ →$\mathbb{N}$, яка посилає (a, b) → a + b. Карріруя +, отримуємо певну функцію p:$\mathbb{N}$ →$\mathbb{N}$$^{\mathbb{N}}$. Що таке р (3)? ♦

Приклад 3.74.

Якщо ви знаєте якусь абстрактну алгебру або топологію, ось деякі інші приклади доповнень.

Вільні конструкції: з урахуванням будь-якого набору ви отримуєте вільну групу, вільний моноїд, вільне кільце, вільний векторний простір тощо; кожен з них є лівим суміжним. Відповідний правий суміжний приймає групу, моноїд, кільце, векторний простір тощо і забуває алгебраїчну структуру, щоб повернути базову множину.
Аналогічно, за заданим графіком ви отримуєте безкоштовне попереднє замовлення або вільну категорію, як ми обговорювали в розділі 3.2.3; кожен з них є лівим суміжним. Відповідний правий суміжний є базовим графіком попереднього замовлення або категорії.
Дискретні речі: за допомогою будь-якої множини ви отримуєте дискретний передпорядок, дискретний графік, дискретний метричний простір, дискретну категорію, дискретний топологічний простір; кожен з них є лівим суміжним. Відповідний правий суміжний знову лежить в основі множини.
Кодискретні речі: за допомогою будь-якої множини ви отримуєте кодискретний передпорядок, повний графік, кодискретну категорію, кодискретний топологічний простір; кожен з них є правильним суміжним. Відповідний лівий суміжний є базовим набором.
За умови групи, ви можете коефіцієнт за її підгрупою комутатора, щоб отримати абелеву групу; це лівий суміжний. Правильно прилеглим є включення абелевих груп в групи.

Лівий і правий функтори$\Sigma$ pushford, і

За даними F: C → D, функція міграції даних ↑ F перетворює D-екземпляри на C-екземпляри. Цей функтор має як ліве, так і праве суміжні:

$Знімок екрана 2021-01-12 в 5.32.03 PM.png$

Використання імен$\Sigma$ і в цьому контексті є досить стандартним в теорії категорій. У випадку з базами даних вони мають наступну корисну мнемоніку:

$Знімок екрана 2021-01-12 в 5.32.48 PM.png$

Так само, як ми використовували F, щоб відтягнути будь-яку дискретну динамічну систему вздовж F: Gr → DDS і отримати графік, функції міграції σ F і F можуть бути використані для перетворення будь-якого графіка в дискретну динамічну систему. Тобто, враховуючи екземпляр J: Gr → Set, ми можемо отримати екземпляри$\Sigma$ F (J) та F (J) на DDS. Це, однак, досить технічно, і ми залишаємо його авантюрному читачеві, щоб обчислити приклад, за допомогою, можливо, з [Spi14a], який детально досліджує визначення σ та. Менш технічний ярлик - це просто кодування обчислень у програмному забезпеченні FQL з відкритим вихідним кодом.

Щоб отримати основну ідею, не занурюючись у технічні деталі, тут ми натомість обговоримо дуже простий приклад. Згадаймо схеми з ур. (3.5). Ми можемо встановити між ними функтор, який посилає чорні крапки чорним крапкам, а білі крапки до білих крапок:

$Знімок екрана 2021-01-12 в 5.36.07 PM.png$

З цим функтором F в руці, ми можемо перетворити будь-який B -екземпляр в A -екземпляр за допомогою Δ F. Тоді як ↑ був цікавий у випадку перетворення дискретних динамічних систем на графіки в Розділі 3.4.1, це не дуже цікаво в даному випадку. Дійсно, він просто скопіює ↑ для дублікатів - рядки в Airline сидіння як в економічному, так і в першому класі.

F має два суміжні,$\Sigma$ F і F, обидва з яких перетворюють будь-який A -екземпляр I в B -екземпляр. Функтор$\Sigma$ F робить те, що можна було б очікувати від читання імен на кожному об'єкті: він поставить в Airline Seat об'єднання економ і першого класу:

$\sigma$F (I) (Airline Seat) = I (Економ) I (Перший клас).

Функтор F ставить в Airline Seat набір тих пар (e, f) де e є економ сидіння, f - місце першого класу, і е і f мають однакову ціну і положення.

У цьому конкретному прикладі можна уявити, що таких місць не повинно бути в дійсному екземплярі I, в цьому випадку F (I) (Airline Seat) було б порожнім. Але в інших випадках використання цих же схем, F може бути корисною операцією. Наприклад, в схемі А замініть ярлик «Економ» на «Програма винагород», а в B замінити «Airline Seat» на «Місця першого класу». Тоді операція F знаходить ті місця першого класу, які також є нагородами програми місць. Ця операція є своєрідним запитом до бази даних; запит - це операція, для якої будуються бази даних.

Мораль полягає в тому, що складні міграції даних можуть бути визначені шляхом побудови функторів F між схемами та використання «індукованих» функторів$\Sigma$ ‰ F, F і F. Дійсно, на практиці по суті всі корисні міграції можуть бути побудовані саме з них. Отже, мова категорій забезпечує основу для уточнення та міркування щодо міграції даних.

Єдиний набір резюме баз даних

Щоб дати більш сильне уявлення про аромат$\Sigma$ і, розглянемо ще один особливий випадок, а саме, коли цільова категорія D дорівнює 1; див. Вправа 3.12. У цьому випадку існує рівно один функтор C → 1 для будь-якого C; давайте позначимо його

! : С → 1. (3.75)

Вправа 3.76.

Опишіть функтор! : С → 1 від ур. (3,75). Куди він надсилає кожен об'єкт? А як щодо кожного морфізму? ♦

Ми хочемо розглянути функції міграції даних$\Sigma$! : С- Інст → 1 - Інст і! : С- Інст → 1 - Інст. У прикладі 3.53 ми побачили, що екземпляр на 1 - це те ж саме, що і набір. Отже, давайте визначимо 1 - Inst з Set, а отже, обговоримо

$\Sigma$! : C- Інст → Набір і! : C- Inst → Встановити.

З огляду на будь-яку схему C і екземпляр I: C → Set, ми отримаємо множини$\Sigma$! (I) і! (I). Думаючи про ці набори як екземплярів бази даних, кожен відповідає одній таблиці з одним стовпцем, керованим словником, що підсумовує весь екземпляр бази даних на схемі C.

Розглянемо наступну схему

$Знімок екрана 2021-01-12 в 5.51.57 PM.png$

Ось приклад екземпляра I: G → Встановити:

$Знімок екрана 2021-01-12 в 5.52.51 PM.png$

Вправа 3.78.

Зверніть увагу, що G з Eq. (3.77) ізоморфний до схеми Gr. У розділі 3.3.5 ми побачили, що екземпляри на Gr - це графіки.

Намалюйте вищевказаний екземпляр I у вигляді графіка. ♦

Тепер у нас є унікальний функтор! : G → 1, і ми хочемо сказати що$\Sigma$! (I) і! (I) дайте нам як однозначні резюме. По-перше,$\Sigma$! (I) повідомляє нам усі групи електронної пошти «підключені компоненти» в I:

$Знімок екрана 2021-01-12 о 6.01.42 PM.png$

Ця форма резюме, що передбачає виявлення записів у загальні групи, або коефіцієнти, є типовою для$\Sigma$ -операцій. Функтор! (I) перераховує електронні листи від мене, які були надіслані від людини до неї або його самого.

$Знімок екрана 2021-01-12 о 6.02.37 PM.png$

Це знову свого роду запит, вибираючи записи, які відповідають критерію самоврядування електронної пошти. Знову ж таки, це характерно для π-операцій.
Звідки ці факти — що! і σ! діяти так, як ми сказали - походять з? Все випливає з визначення суміжних функторів (3.70): дійсно ми сподіваємося, що це разом з прикладами, наведеними в прикладі 3.74, дасть читачеві деяке уявлення про те, наскільки загальні і корисні ад'юнкції, як в математиці, так і в теорії баз даних.

Ще один момент: хоча ми не будемо докладати деталей, ми зауважимо, що ці операції також є прикладами конструкцій, відомих як коліміти та обмеження в Set. Ми закінчуємо цю главу бонусним матеріалом, досліджуючи ці ключові категорії теоретичних конструкцій. Читач повинен мати на увазі, що загалом і не тільки для функторів до 1, σ-операції будуються з колімітів у Set, а π-операції будуються з лімітів у Set.