Как составит алгоритм для баз данных

К настоящему времени внимательным читателям, не пропустившим ни од­ной статьи, возможно, не терпится. Мы уже перешли к третьей статье — и до сих пор говорим о теории! Когда же мы будем писать SQL код?

Очень скоро! В этой статье рассматривается последняя часть обработки запросов, и в конце у нас будет все необходимое для понимания планов вы­полнения.

Во второй статье рассказывается о реляционных операциях, и в ней гово­рится, что для выполнения запросов нужны физические операции, или ал­горитмы. Сопоставить эти алгоритмы с логическими операциями непросто; иногда сложная логическая операция заменяется несколькими физическими операциями, или несколько логических операций объединяются в одну фи­зическую.

В этой главе мы описываем эти алгоритмы, начиная с алгоритмов извлече­ния данных, а затем переходим к алгоритмам для более сложных операций.

Понимание этих алгоритмов позволит нам вернуться к планам выполне­ния и лучше понять их компоненты. Таким образом, мы будем всего в одном шаге от нашей цели, которая состоит в том, чтобы научиться настраивать запросы.

стоимостные модели алгоритмов

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

Вместо этого оптимизатор использует внутренние показатели, основанные на объеме вычислительных ресурсов, необходимых для выполнения запроса или отдельной физической операции в рамках плана. Наиболее важными ресурсами являются те, что влияют на время выполнения, а именно циклы процессора и количество операций ввода-вывода (чтение и запись дисковых блоков). Другие ресурсы, такие как память или дисковое пространство, тоже косвенно влияют на время выполнения; например, количество доступной памяти будет влиять на соотношение циклов процессора и количество опе­раций ввода-вывода. Распределение памяти контролируется параметрами сервера и здесь не рассматривается.

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

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

Стоимостная модель физической операции оценивает ресурсы, необходи­мые для выполнения операции. Как правило, стоимость зависит от таблиц, указанных в качестве аргументов операции. Для представления стоимост­ных моделей мы будем использовать простые формулы со следующими обо­значениями: для любой таблицы или отношения R символы TR и BR обознача­ют количество строк в таблице и количество дисковых блоков, занимаемых таблицей, соответственно. Дополнительные обозначения будут вводиться по мере необходимости.

В следующем разделе обсуждаются физические операции и рассматри­ваются алгоритмы и стоимостные модели для каждой из них. Поскольку относительная скорость процессора и внешнего хранилища может варьиро­ваться в широких пределах, затраты на процессор и ввод-вывод рассматри­ваются отдельно. Мы не будем говорить про логические операции проекции и фильтрации, которые обсуждали в предыдущей статье. Обычно они объ­единяются с предшествующей им операцией, потому что могут применяться независимо к каждой строке, не завися от других строк в таблице аргумента.

алгоритмы достуПа к данным

Чтобы начать выполнение запроса, движок должен извлечь сохраненные данные. Этот раздел касается алгоритмов, используемых для чтения данных из объектов базы данных. На практике эти операции часто сочетаются с по­следующей операцией в плане выполнения запроса. Это выгодно в тех слу­чаях, когда можно сэкономить время выполнения, избегая чтения, которое впоследствии будет отфильтровано.

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

Представление данных

Неудивительно, что данные хранятся в файлах на жестких дисках. Любой файл, используемый для объектов базы данных, делится на блоки одинако­вой длины; по умолчанию PostgreSQL использует блоки по 8192 байта каж­дый. Блок — это единица, которая передается между жестким диском и опе­ративной памятью, а количество операций ввода-вывода, необходимое для выполнения любого доступа к данным, равно количеству блоков, которые читаются или записываются.

Объекты базы данных состоят из логических элементов (строк таблиц, ин­дексных записей и т. д.). PostgreSQL выделяет место для этих элементов бло­ками. Несколько мелких элементов могут находиться в одном блоке; более крупные элементы могут быть распределены между несколькими блоками. Общая структура блока показана на рис. 3.1.

Рис. 3.1 ❖ Общая структура блока в PostgreSOL

Распределение элементов по блокам также зависит от типа объекта базы данных. Строки таблицы хранятся с использованием структуры данных, на­зываемой кучей (heap): строка может быть вставлена в любой блок, в котором достаточно свободного места, без специального упорядочивания. Другие объекты (например, индексы) могут использовать блоки иначе.

Полное (последовательное) сканирование

При полном сканировании движок базы данных последовательно считывает все строки в таблице и для каждой строки проверяет условие фильтрации. Чтобы оценить стоимость этого алгоритма, требуется более подробное опи­сание, показанное псевдокодом в листинге 3.1.

Листинг 3.1 ❖ Псевдокод алгоритма доступа к данным полным сканированием

FOR each block IN a_table LOOP

read block

FOR each row IN block LOOP

IF filter_condition (row)

THEN output (row)

END IF

END LOOP

END LOOP

Количество операций ввода-вывода равно BR; общее количество итера­ций внутреннего цикла равно TR. Нам также необходимо оценить стоимость операций, порождающих выходные строки. Она зависит от селективности (которая обозначается S) и равняется S * TR. Собрав все эти части воедино, мы можем вычислить стоимость полного сканирования:

c1 * BR + c2 * TR + c3 * S * TR,

где константы c1, c2 и c3 представляют характеристики аппаратного обес­печения.

Полностью просканировать можно любую таблицу; для этого не нужны до­полнительные структуры данных. Остальные алгоритмы зависят от наличия индексов в таблице, как описано ниже.

Доступ к таблицам на основе индексов

Обратите внимание, что пока мы не перешли к физическим операциям, мы даже не упоминали алгоритмы доступа к данным. Нам не нужно «читать» отношения — это абстрактные объекты. Если следовать идее того, что от­ношения отображаются в таблицы, нет другого способа получить данные, кроме как прочитать всю таблицу в оперативную память. Как еще мы уз­наем, какие значения содержатся в каких строках? Но реляционные базы данных не были бы таким мощным инструментом обработки данных, если бы на этом мы и остановились. Все реляционные базы данных, включая PostgreSQL, позволяют создавать дополнительные, избыточные структуры, значительно ускоряя доступ к данным по сравнению с простым последова­тельным чтением.

Эти дополнительные структуры называются индексами.

Как создаются индексы, мы рассмотрим позже; пока нам нужно знать два факта, касающихся индексов. Во-первых, индексы — «избыточные» объекты базы данных; они не хранят никакой дополнительной информации, которую нельзя найти в исходной таблице.

Во-вторых, индексы предоставляют дополнительные пути доступа к дан­ным; они позволяют определить, какие значения хранятся в строках таб­лицы, без необходимости чтения самой таблицы — так работает доступ на основе индексов. И как упоминалось ранее, это происходит полностью про­зрачно для приложения.

Если условие (или условия) фильтрации поддерживается индексом в таб­лице, индекс можно использовать для доступа к данным из этой таблицы. Алгоритм извлекает список указателей на блоки, содержащие строки со зна­чениями, удовлетворяющими условию фильтрации, и только эти блоки чи­таются из таблицы.

Чтобы получить строку таблицы по указателю, необходимо прочитать блок, содержащий эту строку. Основная структура данных таблицы — это куча, то есть строки хранятся неупорядоченно. Их порядок не гарантирован и не соответствует свойствам данных. Есть две отдельные физические операции, используемые PostgreSQL для получения строк с помощью индексов: индекс­ное сканирование (index scan) и сканирование по битовой карте (bitmap heap scan). При индексном сканировании движок базы данных считывает одну за другой все записи индекса, которые удовлетворяют условию фильтра­ции, и в этом же порядке извлекает блоки. Поскольку базовая таблица пред­ставляет собой кучу, несколько записей индекса могут указывать на один и тот же блок. Чтобы избежать многократного чтения одного и того же блока, в PostgreSQL реализована операция сканирования по битовой карте, которая создает битовую карту блоков, содержащих необходимые строки. Потом все строки в этих блоках фильтруются. Преимущество реализации PostgreSQL состоит в том, что она упрощает использование нескольких индексов в од­ной и той же таблице в одном запросе, применяя логические операторы «и» и «или» к битовым картам блоков, порождаемым каждым индексом.

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

Сканирование только индекса

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

Алгоритм считывает данные из индекса и применяет оставшиеся условия фильтрации, если это необходимо. Обычно не нужно обращаться к таблич­ным данным, но иногда необходимы дополнительные проверки — мы под­робно рассмотрим эту тему в главе 5.

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

Сравнение алгоритмов доступа к данным

Выбор лучшего алгоритма доступа к данным в основном зависит от селек­тивности запроса. Отношение стоимости к селективности для различных алгоритмов доступа к данным показано на рис. 3.2. Мы намеренно ограни­чиваемся качественным сравнением; все числа на этом графике опущены, поскольку они зависят от аппаратного обеспечения и размера таблицы.

Рис. 3.2 ❖ Связь стоимости и селективности запросов для разных алгоритмов доступа к данным

Линия, соответствующая полному сканированию, прямая и почти гори­зонтальная: ее рост происходит из-за генерации выходных строк. Как прави­ло, стоимость генерации незначительна по сравнению с другими затратами для этого алгоритма.

Линия, обозначающая стоимость доступа к таблице на основе индекса, начинается (почти) с нуля и быстро растет с ростом селективности. Рост замедляется при больших значениях селективности, где стоимость этого алгоритма значительно выше, чем стоимость полного сканирования.

Самым интересным моментом является пересечение двух линий: для меньших значений селективности предпочтительнее доступ на основе ин­дексов, а полное сканирование лучше подходит для больших значений се­лективности. Точное положение пересечения зависит от аппаратного обеспе­чения и может зависеть от размера таблицы. Для относительно медленных вращающихся дисков доступ на основе индексов предпочтительнее, только если селективность не превышает 2-5 %. Для твердотельных накопителей или виртуального окружения это значение может быть выше. На старых вращающихся дисках произвольный доступ к блокам может быть на порядок медленнее последовательного доступа, поэтому дополнительные накладные расходы на индексы при той же пропорции строк получаются выше.

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

Оптимизатор запросов оценивает селективность запроса и селективность, соответствующую точке пересечения для данной таблицы и данного индекса. Условие фильтрации запроса, показанного в листинге 3.2, выбирает значи­тельную часть таблицы.

Листинг 3.2 ❖ Фильтрация по диапазону, выполняемая полным сканированием таблицы

SELECT flight_no, departure_airport, arrival_airport

FROM flight

WHERE scheduled_departure BETWEEN ‘2020-05-15’ AND ‘2020-08-31’;

В данном случае оптимизатор выбирает полное сканирование (см. рис. 3.3).

Рис. 3.3 ❖ Последовательное сканирование

Однако меньший диапазон в том же запросе приводит к доступу к таблице на основе индекса. Запрос показан в листинге 3.3, а его план выполнения — на рис. 3.4.

Листинг 3.3 ❖ Фильтрация по диапазону с доступом к таблице на основе индекса

SELECT flight_no, departure_airport, arrival_airport

FROM flight

WHERE scheduled_departure BETWEEN ‘2020-08-12’ AND ‘2020-08-13’;

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

Рис. 3.4 ❖ Сканирование по битовой карте (доступ на основе индекса)

Таким образом, среди алгоритмов доступа к данным нет победителей и проигравших. Любой алгоритм может выиграть при определенных услови­ях. Далее, выбор алгоритма зависит от структур хранения и статистических свойств данных. База данных поддерживает для таблиц метаданные, назы­ваемые статистикой: информация о кардинальности столбца, разреженности и т. д. Обычно эта статистика неизвестна во время разработки приложения и может изменяться на протяжении жизненного цикла приложения. Следо­вательно, декларативный характер языка запросов важен для производи­тельности системы. В частности, при изменении статистики таблицы или при корректировке других факторов стоимости для одного и того же запроса может быть выбран другой план выполнения.

индексные структуры

Этот раздел начинается с абстрактного определения того, какую структу­ру хранения можно назвать индексом; кратко рассматриваются наиболее распространенные индексные структуры, такие как деревья и хеш-индексы, и затрагиваются некоторые особенности PostgreSQL.

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

Что такое индекс?

Можно предположить, что любой человек, работающий с базами данных, знает, что такое индекс. Увы, удивительно много людей — разработчиков баз данных и составителей отчетов, а в некоторых случаях даже администра­торов баз данных — используют индексы и даже создают их, лишь поверх­ностно представляя, что это за объекты и какова их структура. Во избежание недоразумений мы начнем с определения того, что мы подразумеваем под индексом.

Существует множество типов индексов, поэтому мы ориентируемся не на структурные свойства, а определяем индекс по способу его использования. Структура данных назы­вается индексом, если:

• это избыточная структура данных;
• она невидима для приложения;
• она предназначена для ускорения выбора данных по определенным критериям.

Избыточность означает, что индекс можно удалить без потери данных и восстановить по информации, хранящейся где-то еще (конечно, в табли­цах). Невидимость означает, что приложение не может узнать о наличии ин­декса или о его отсутствии. Иначе говоря, любой запрос дает те же результаты как с индексом, так и без него. И наконец, индекс создается в надежде (или с уверенностью), что это улучшит производительность конкретного запроса или (что еще лучше!) нескольких запросов.

Улучшение производительности не происходит бесплатно. Поскольку индекс избыточен, он должен обновляться при обновлении данных таб­лицы. Это приводит к накладным расходам для операций обновления, которыми иногда нельзя пренебречь. В частности, индексы PostgreSQL могут оказывать большое влияние на операцию очистки (VACUUM). Однако многие учебники по базам данных переоценивают эти расходы. Совре­менные высокопроизводительные СУБД используют алгоритмы, которые снижают стоимость обновлений индексов, поэтому несколько индексов в таблице — обычное дело.

Хотя индексные структуры могут значительно различаться для разных ти­пов индексов, ускорение всегда достигается за счет быстрой проверки неко­торых условий фильтрации, указанных в запросе. Такие условия фильтрации устанавливают определенные ограничения на атрибуты таблицы. На рис. 3.5 показана структура наиболее распространенных индексов.

В правой части рисунка показана таблица, а в левой — индекс, который можно рассматривать как особый вид таблицы. Каждая строка индекса со­стоит из индексного ключа и указателя на строку таблицы. Значение ключа обычно совпадает со значением атрибута таблицы. В примере на рис. 3.5 в качестве значения используется код аэропорта; следовательно, данный индекс поддерживает поиск по коду аэропорта.

У столбца может быть одно и то же значение в нескольких строках табли­цы. Если этот столбец индексирован, индекс должен содержать указатели на все строки, содержащие это значение индексного ключа. В PostgreSQL индекс содержит несколько записей, то есть ключ индекса повторяется для каждого указателя на строку таблицы.

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

Рис. 3.5 ❖ Индексная структура

B-деревья

Самая распространенная индексная структура — это B-дерево. Структура B-дерева показана на рис. 3.6; коды аэропортов являются индексными клю­чами. Дерево состоит из иерархически организованных узлов, связанных с блоками, хранящимися на диске.

Листовые узлы (показанные на рис. 3.6 в нижней строке) содержат точно такие же записи индекса, как на рис. 3.5; эти записи состоят из индексного ключа и указателя на строку таблицы.

Нелистовые узлы (расположенные на всех уровнях, кроме нижнего) со­держат записи, состоящие из наименьшего ключа (на рис. 3.5 это наимень­шее буквенно-цифровое значение) в блоке, расположенном на следующем уровне, и указателя на этот блок. Все записи во всех блоках упорядочены, и в каждом блоке используется не менее половины доступного объема.

Любой поиск ключа K начинается с корневого узла B-дерева. Во время поиска по блоку будет найден самый большой ключ P, не превышающий K, и затем поиск продолжается в блоке, на который ссылается указатель, свя­занный с P. Поиск продолжается, пока мы не дойдем до листового узла, где указатели ссылаются на строки таблицы. Количество просмотренных при поиске узлов равно глубине дерева. Конечно, ключ K не обязательно хранится в индексе, но при поиске обнаруживается либо ключ, либо то место, где он мог быть расположен.

Рис. 3.6 ❖ Пример В-дерева

B-деревья также поддерживают поиск по диапазону (представляемый операцией between в SQL). Как только будет найдена нижняя граница диапа­зона, все индексные ключи диапазона можно получить последовательным сканированием листовых узлов до тех пор, пока не будет достигнута верх­няя граница диапазона. Сканирование листовых узлов необходимо также для получения всех указателей, если индекс не является уникальным (то есть значение индексного ключа может соответствовать более чем одной строке).

Почему так часто используются B-деревья?

Из информатики мы знаем, что ни один алгоритм поиска не может найти индексный ключ среди N различных ключей быстрее, чем за время log N (вы­раженное в инструкциях процессора). Такая производительность достигает­ся с помощью двоичного поиска по упорядоченному списку или с помощью двоичных деревьев. Однако стоимость обновлений (например, вставки но­вых ключей) может быть очень высока как для упорядоченных списков, так и для двоичных деревьев: вставка одной записи может привести к полной реструктуризации. Это делает обе структуры непригодными для хранения на диске.

Напротив, B-деревья можно изменять без значительных накладных рас­ходов. Когда вы вставляете запись, реструктуризация ограничена одним блоком. Если емкость блока превышена, то он расщепляется на два блока, и обновление распространяется на верхние уровни. Даже в худшем случае количество измененных блоков не будет превышать глубины дерева.

Чтобы оценить стоимость поиска в B-дереве, нужно вычислить его глубину. Если каждый блок содержит f указателей, то количество блоков на каждом уровне в f раз больше, чем в предыдущем. Следовательно, глубина дерева, содержащего N записей, равна log N / log f. Эта формула дает количество об­ращений к диску, необходимое для поиска по одному ключу. Количество ин­струкций процессора для каждого блока ограничено, и обычно внутри блока используется двоичный поиск. Следовательно, стоимость ресурсов процес­сора лишь ненамного хуже теоретически возможного лучшего варианта. Раз­мер блока в PostgreSQL составляет 8 Кбайт. В такой блок помещаются десятки индексных записей; следовательно, индекс с шестью-семью уровнями может вместить миллиарды записей.

В PostgreSOL индекс на основе B-дерева можно создать для любого поряд­кового типа данных; то есть такого, что из любых двух различных значений этого типа одно значение меньше другого. В эту категорию входят и поль­зовательские типы.

Битовые карты

Битовая карта — это вспомогательная структура данных, которая использу­ется внутри PostgreSQL с разными целями. Битовые карты можно рассмат­ривать как своего рода индекс: они созданы для облегчения доступа к дру­гим структурам данных, содержащим несколько блоков. Обычно битовые карты используются для компактного представления свойств табличных данных.

Чаще всего битовая карта содержит по одному биту для каждого блока (8192 байта). Значение бита равно 1, если блок обладает нужным свойством, и 0, если нет. На рис. 3.7 показано, как битовые карты используются для до­ступа к данным по нескольким индексам.

Рис. 3.7 ❖ Использование битовых карт для доступа к таблицам по нескольким индексам

Движок базы данных начинает со сканирования двух индексов и построе­ния для каждого из них битовой карты, которая указывает на блоки с под­ходящими табличными строками. Эти битовые карты показаны на рисунке в строках, обозначенных «Индекс 1» и «Индекс 2». Как только битовые карты будут созданы, движок выполняет побитовую операцию «и», чтобы найти блоки, содержащие подходящие значения для обоих критериев отбора. Нако­нец, сканируются блоки данных, соответствующие единицам в полученной битовой карте. Таким образом, к блокам, которые удовлетворяют только одному из двух критериев, не придется обращаться.

Обратите внимание, что подходящие значения могут находиться в раз­ных строках одного блока. Битовая карта гарантирует, что соответствующие строки не будут пропущены, но не гарантирует, что все просканированные блоки содержат подходящие строки.

Битовые карты очень компактны; однако для очень больших таблиц они могут занимать много блоков.

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

PostgreSQL предлагает множество индексных структур, поддерживающих разные типы данных и разные классы условий поиска.

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

R-дерево поддерживает поиск по пространственным данным. Индексный ключ для R-дерева всегда представляет собой прямоугольник в многомерном пространстве. Поиск возвращает все объекты, имеющие непустое пересе­чение с прямоугольником запроса. Структура R-дерева похожа на структу­ру B-дерева; однако расщепление переполненных узлов устроено намного сложнее. R-деревья эффективны для небольшого числа измерений (обычно от двух до трех).

Другие типы индексов, доступные в PostgreSQL, полезны для полнотексто­вого поиска, поиска в очень больших таблицах и многого другого. Дополни­тельная информация по этим темам представлена в главе 14. Любой из этих индексов можно относительно легко настроить для пользовательских типов данных. Однако в этой книге мы не обсуждаем индексы по пользовательским типам.

сочетание отношений

Настоящая мощь реляционной теории и баз данных SQL основана на соче­тании данных из нескольких таблиц.

В этом разделе описываются алгоритмы операций, сочетающие данные, в том числе декартово произведение, соединение, объединение, пересече­ние и даже группировка. Удивительно, но большинство этих операций мож­но реализовать с помощью практически идентичных алгоритмов. По этой причине мы обсуждаем алгоритмы, а не операции, которые они реализуют. Мы будем использовать имена R и S для входных таблиц при описании этих алгоритмов.

Вложенные циклы

Первый алгоритм предназначен для получения декартова произведения, то есть множества всех пар строк из входных таблиц. Самый простой способ вычислить произведение — перебрать строки таблицы R и для каждой строки из R перебрать строки таблицы S. Псевдокод этого простого алгоритма пред­ставлен в листинге 3.4, а графическое представление алгоритма показано на рис. 3.8.

Листинг 3.4 ❖ Псевдокод для вложенных циклов

FOR row1 IN table1 LOOP

FOR row2 IN table2 LOOP

output (row)

END LOOP

END LOOP

Время, необходимое для этого простого алгоритма, пропорционально про­изведению размеров таблиц ввода: rows(R)*rows(S).

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

Небольшие модификации алгоритма вложенного цикла позволяют вы­числить практически любую логическую операцию, сочетающую данные из двух таблиц. Псевдокод из листинга 3.5 реализует соединение.

Листинг 3.5 ❖ Алгоритм вложенного цикла для соединения

FOR row1 IN table1 LOOP

FOR row2 IN table2 LOOP

IF match(row1,row2) THEN

output (row)

END IF

END LOOP

END LOOP

Обратите внимание, что соединение вложенными циклами является прос­той реализацией абстрактного определения соединения как декартова про­изведения, за которым следует фильтр. Поскольку вложенный цикл обраба­тывает все пары входных строк, стоимость остается той же, хотя количество выходных строк меньше, чем в случае декартова произведения.

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

Хотя стоимость обработки остается прежней, варианты алгоритма вло­женного цикла в сочетании с полным сканированием выполняют вложенные циклы по блокам входных таблиц и еще один уровень вложенных циклов по строкам, содержащимся в этих блоках. Более сложные алгоритмы миними­зируют количество обращений к диску, загружая несколько блоков первой таблицы (внешний цикл) и обрабатывая все строки этих блоков за один про­ход по таблице S .

Рис. 3.8 ❖ Алгоритм вложенного цикла

Вышеупомянутые алгоритмы могут работать с любыми условиями соеди­нения. Тем не менее большинство соединений, которые нужны на практике, являются естественными (natural): их условие соединения требует, чтобы некоторые атрибуты таблицы R были равны соответствующим атрибутам таблицы S.

Алгоритм соединения вложенными циклами также можно комбинировать с индексным доступом к данным, если в таблице S есть индекс по атрибутам, используемым в условии соединения. Для естественных соединений внут­ренний цикл такого алгоритма сокращается до нескольких строк таблицы S для каждой строки таблицы R. Внутренний цикл может даже полностью ис­чезнуть, если индекс по таблице S уникален, например атрибут соединения таблицы S является его первичным ключом.

Алгоритм вложенного цикла с индексным доступом обычно предпочтите­лен, если количество строк в таблице R тоже мало. Однако доступ на основе индекса становится неэффективным, когда количество строк, подлежащих обработке, увеличивается, как описано в этой статье.

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

Алгоритмы на основе хеширования

Результат естественного соединения состоит из пар строк из таблиц R и S, которые имеют равные значения атрибутов, по которым выполняется со­единение. Идея алгоритма соединения хешированием проста: если значения равны, то и хеш-значения тоже равны.

Алгоритм разбивает обе входные таблицы по корзинам в соответствии со значениями хеш-функции, а затем независимо соединяет строки в каждой корзине. Схема этого алгоритма показана на рис. 3.9.

Рис. 3.9 ❖ Алгоритм соединения хешированием

Базовая версия алгоритма соединения хешированием включает две фазы: 1) на этапе построения все кортежи таблицы R сохраняются в корзинах согласно значениям хеш-функции;

2) на этапе проверки каждая строка таблицы S направляется в соответ­ствующую ей корзину. Если подходящие строки таблицы R находятся в этой корзине, порождаются выходные строки.

Самый простой способ найти подходящие строки в корзине — использовать вложенные циклы (фактически нужно перебирать все строки в корзине для каждой строки таблицы S).

Две фазы алгоритма на основе хеширования показаны как отдельные фи­зические операции в плане выполнения.

Стоимость соединения хешированием приблизительно можно оценить по следующей формуле, где JA — атрибут, по которому выполняется соединение:

cost(hash,R,S) = size(R) + size(S) + size(R)*size(S)/size(JA)

Первое и второе слагаемые в этой формуле приблизительно равны стоимо­сти одного прохода по всем строкам таблиц R и S. Последнее слагаемое обо­значает размер порождаемого результата соединения. Конечно, стоимость вывода одинакова для всех алгоритмов соединения, но нам не нужно было включать его в оценку стоимости алгоритма вложенного цикла, потому что она меньше, чем стоимость вложенных циклов.

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

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

Сортировка слиянием

Еще один алгоритм для естественных соединений, который называют сор­тировкой слиянием, показан на рис. 3.10.

Рис. 3.10 ❖ Алгоритм сортировки слиянием

На первом этапе алгоритма обе входные таблицы сортируются в порядке возрастания по атрибутам соединения.

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

Стоимость фазы слияния можно выразить той же формулой, что и для соединения хешированием, то есть она пропорциональна сумме размеров входных и выходных данных. Фактическая стоимость несколько ниже, по­тому что нет необходимости в этапе построения хеш-таблицы.

Стоимость сортировки можно оценить следующей формулой:

size(R)*log(size(R)) + size(S)*log(size(S))

Алгоритм сортировки слиянием особенно эффективен, если одна или обе входные таблицы уже отсортированы. Это может произойти в серии соеди­нений по одним и тем же атрибутам.

Сравнение алгоритмов

Как и в случае с алгоритмами доступа к данным, здесь нет заведомых по­бедителей или проигравших. Любой из алгоритмов может оказаться лучше в зависимости от обстоятельств. Алгоритм вложенного цикла более универ­сален и лучше всего подходит для небольших соединений с использованием индексов; сортировка слиянием и хеширование более эффективны для боль­ших таблиц, если они применимы.

выводы

Рассмотрев стоимостные модели алгоритмов, алгоритмы доступа к данным, назначение и структуру индексов и алгоритмы для более сложных опера­ций вроде соединения, мы наконец-то набрали достаточно строительных блоков, чтобы взяться за результат работы планировщика запросов — план выполнения.

В следующей статье рассказывается, как читать и понимать планы выпол­нения и улучшать их.

Уровень сложности
Средний

Время на прочтение
6 мин

Количество просмотров 1.6K

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

Введение

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

Традиционные методы обработки данных vs представленный алгоритм

Традиционные методы обработки данных в MLM, такие как рекурсивные функции, часто оказываются медленными и неэффективными, особенно при работе с большими объемами данных. Это может привести к длительным задержкам в обработке информации, что негативно сказывается на оперативности и эффективности работы компании.

Допустим, у нас есть бинарная MLM-структура с 10 миллионами пользователей и 23 уровнями. Стандартный подход к обработке таких структур заключается в использовании рекурсивных функций, что может занять значительное время и ресурсы сервера.

Например, для выборки всех пользователей на 23-м уровне с использованием рекурсии. Сложность рекурсии оценивается как O(n * h), где n — количество пользователей на уровне, а h — высота дерева. В данном случае, это равно 2^23 * 24 ≈ 201,326,592 операций. (в которые входят и SQL запросы), что займет очень много времени, даже на мощных серверах. Компания которая обращалась ко мне для оптимизации базы данных, расчеты проводила раз в день по ночам чтобы не прерывать основную работу. Ощутимые задержки вычислений начинаются уже после 50000 пользователей даже на оптимизированной базе данных.

Проблема решилась созданием дополнительной таблицы, в которую начал записывать древовидную структуру в следующем виде:

id |iduser| id_rek| road        | level
---|------|-------|-------------|-----
1  | 1    | 0     | |1|         | 1
2  | 2    | 1     | |1|2|       | 2
3  | 3    | 1     | |1|3|       | 2
4  | 4    | 2     | |1|2|4|     | 3
5  | 5    | 2     | |1|2|5|     | 3
6  | 6    | 3     | |1|3|6|     | 3

Теперь мы основную нагрузку перекладываем на SQL запросы (запрос с LIKE не самый эффективный, но по сравнению с рекурсивными методами значительно выигрывает), которые выполняются значительно быстрее и нагляднее, пример на php, одним запросом находит всех последователей пользователя id-3 в порядке иерархии, тогда как рекурсией нам бы пришлось с корневого id обойти всех пользователей.

<?php 

class MLMTree {
    private $db;

    public function __construct($db) {
        $this->db = $db;
    }

    public function getAllDescendants($rootUserId) {
        $query = "SELECT * FROM users WHERE road LIKE CONCAT('%|', :root_user_id, '|%') AND id != :root_user_id ORDER BY level";
        $stmt = $this->db->prepare($query);
        $stmt->bindValue(':root_user_id', $rootUserId, PDO::PARAM_INT);
        $stmt->execute();

        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }
}

// Пример использования
$db = new PDO('mysql:host=localhost;dbname=mlm_database;charset=utf8', 'username', 'password');
$mlmTree = new MLMTree($db);
$rootUserId = 3;

$descendants = $mlmTree->getAllDescendants($rootUserId);
print_r($descendants);

?>

Пример класса пользователя на php, на его основе Вы можете создать свой вариант, по данной методике можно реализовать практически все варианты и виды MLM структур.

<?php

class User
{
    private $pdo;

    public function __construct($pdo)
    {
        $this->pdo = $pdo;
    }

    public function find($userId)
    {
        $sql = "SELECT * FROM users WHERE id = :id";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':id' => $userId]);
        return $stmt->fetch(PDO::FETCH_ASSOC);
    }

    public function create($data)
    {
        $sql = "INSERT INTO users (username, email, password, id_rek) VALUES (:username, :email, :password, :id_rek)";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([
            ':username' => $data['username'],
            ':email' => $data['email'],
            ':password' => $data['password'],
            ':id_rek' => $data['id_rek']
        ]);
        $userId = $this->pdo->lastInsertId();

        // Create corresponding tree entry
        $this->createTreeEntry($userId, $data['id_rek']);
    }

    private function createTreeEntry($userId, $id_rek)
    {
        if ($userId == 1) {
            $sql = "INSERT INTO tree (id_user, id_rek, col, lvl, road) VALUES (1, 0, 0, 1, '|1|')";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute();
        } else {
            $sql = "SELECT * FROM tree WHERE road LIKE CONCAT('%|', :id_rek, '|%') ORDER BY lvl, col ASC";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute([':id_rek' => $id_rek]);
            $treeRow = $stmt->fetch(PDO::FETCH_ASSOC);

            if ($treeRow) {
                $road = $treeRow['road'] . $userId . "|";
                $lvl = count(explode("|", $road)) - 2;

                $sql = "INSERT INTO tree (id_user, id_rek, col, lvl, road) VALUES (:id_user, :id_rek, 0, :lvl, :road)";
                $stmt = $this->pdo->prepare($sql);
                $stmt->execute([
                    ':id_user' => $userId,
                    ':id_rek' => $id_rek,
                    ':lvl' => $lvl,
                    ':road' => $road
                ]);

        $sql = "UPDATE tree SET col = col + 1 WHERE id_user = :id_rek";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':id_rek' => $id_rek]);
    }
}
    }

    public function delete($userId)
    {
        $user = $this->find($userId);
        if ($user) {
            $sql = "DELETE FROM users WHERE id = :id";
            $stmt = $this->pdo->prepare($sql);
            $stmt->execute([':id' => $userId]);

            $this->deleteTreeEntry($userId, $user['id_rek']);
            $this->updateRoadsAfterDeletion($userId, $user['id_rek']);
            $this->updateRekIdAfterDeletion($userId, $user['id_rek']);
        }
    }

    private function deleteTreeEntry($userId, $id_rek)
    {
        $sql = "DELETE FROM tree WHERE id_user = :id_user";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':id_user' => $userId]);

        $sql = "UPDATE tree SET col = col - 1 WHERE id_user = :id_rek";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':id_rek' => $id_rek]);
    }

    private function updateRoadsAfterDeletion($userId, $id_rek)
    {
        $sql = "UPDATE tree SET road = REPLACE(road, '|$userId|', '|'), lvl = lvl - 1 WHERE road LIKE '%|$userId|%'";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute();
    }
    private function updateRekIdAfterDeletion($userId, $id_rek)
    {
        $sql = "UPDATE users SET id_rek = :id_rek WHERE id_rek = :user_id";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':id_rek' => $id_rek, ':user_id' => $userId]);

        $sql = "UPDATE tree SET id_rek = :id_rek WHERE id_rek = :user_id";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':id_rek' => $id_rek, ':user_id' => $userId]);
    }
    public function getUsersByLevel($level)
{
    $sql = "SELECT tree.*, users.username, users.email, users.password FROM tree 
            JOIN users ON tree.id_user = users.id
            WHERE tree.lvl = :level";
    $stmt = $this->pdo->prepare($sql);
    $stmt->execute([':level' => $level]);
    return $stmt->fetchAll(PDO::FETCH_ASSOC);
}

    
    public function getUsersByRekId($rekId)
    {
        $sql = "SELECT * FROM tree WHERE id_rek = :rek_id";
        $stmt = $this->pdo->prepare($sql);
        $stmt->execute([':rek_id' => $rekId]);
        return $stmt->fetchAll(PDO::FETCH_ASSOC);
    }
    
    // ... другие методы, если необходимо ...
}
?>

Преимущества нового алгоритма

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

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

3. Упрощение процесса управления данными: новый алгоритм предоставляет интуитивно понятный и организованный способ анализа и управления данными MLM-структур, что облегчает работу администраторов и менеджеров.

1. Повышение точности: благодаря оптимизации алгоритма, обработка данных становится более точной, что позволяет избегать ошибок и противоречий в информации.

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

Подведем итоги

Мы рассмотрели эффективный алгоритм обработки больших баз данных MLM структур и привели примеры его реализации на PHP. Этот подход позволяет значительно сократить время обработки данных и упростить управление MLM структурами.

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

Надеемся, что данная статья поможет вам в решении задач, связанных с MLM структурами и позволит оптимизировать процессы ваших проектов. В случае возникновения дополнительных вопросов или предложений, буду рад вашим комментариям и обсуждениям. Удачи вам в реализации вашего MLM проекта!

Исходные коды примеров лежат на https://github.com/infosave2007/fastmlm

Третья нормальная форма

Пример аномалий у 3НФ

$R = (A, B, C, D)$ и $F = (Arightarrow B, Brightarrow A, ACrightarrow D)$

Два ключа:

первый — $AC$:

$(AC)^+=ACBD = R$

$A^+=ABneq R$

$C^+ = Cneq R$

второй — $BC$:

$(BC)^+=BCAD = R$

$B^+ = BAneq R$

Покажем, что в этом случае $R$ находится в 3НФ:

1)

неключевой атрибут $H$, $H = D$

2)

$Yrightarrow H$, $Hnotin Y$, $Y = AC$

3)

$X = BC$, $X = AC$

Нельзя подобрать нужную тройку, потому $R$ находится в 3НФ. Однако, отношение всё равно обладает аномалиями:

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

Для устранения этого вводится усиленная 3НФ — Бойса-Кодда.

Нормальная форма Бойса-Кодда

ФЗ $Xrightarrow Y$ является неприводимой, если для любого подмножества $Zsubset X$ выполняется $Znrightarrow Y$ или $Zrightarrow Ynotin F^+$

Пусть есть отношение $R$ и $F$ включает в себя нетривиальные неприводимые ФЗ. Тогда отношение $R$ находится в нормальной форме Бойса-Кодда, если для любого $Xrightarrow Yin F$ => $X$ — ключ.

Пример:

$R_1 = AB$, $F_1 = (Arightarrow B, Brightarrow A)$, $A$ — ключ, $B$ — ключ.

или

$R_2 = ACD$, $F_2 = (ACrightarrow D)$, $AC$ — ключ.

Алгоритм синтеза «хорошей» БД

Пусть $U$ — универсальная схема отношения (множество всех атрибутов предметной области) и $F$ — множество ФЗ.

Перед выполнением алгоритма можно привести все ФЗ к одному атрибуту в правой части (по свойству декомпозиции) и удалить лишние ФЗ. Но это не обязательно.

Алгоритм:

1. построить УНП для $F$;
2. если среди ФЗ в УНП нет ФЗ, включающей все атрибуты из $U$, то добавить в УНП тривиальную ФЗ $Urightarrowvarnothing$. Выполнение этого шага почти всегда обеспечивает свойство соединения без потерь будущей схемы БД;
3. привести все нетривиальные ФЗ из УНП к неприводимому виду (удалить лишние атрибуты в левых частях ФЗ);
4. разбить полученное множество ФЗ УНП на классы эквивалентности. Две зависимости $X_irightarrow Y_i$ и $X_jrightarrow Y_j$ будем называть эквивалентными, если $X_iY_i = X_jY_j$. Далее введём обозначение $K_r = X_iY_i$ — множество атрибутов в левой и правой частях ФЗ $r$-того класса эквивалентности;
5. построить граф иерархии полученных на предыдущем шаге классов эквивалентности (если это возможно). Правило построения: $j$-ый узел соединяем снизу с $i$-ым узлом, если $K_jsubset K_i$. В каждом узле записываются все ФЗ, соответствующего класса эквивалентности;
6. из каждого класса эквивалентности в графе иерархии оставить только одну ФЗ. Правила выбора:
   1. удалить из класса эквивалентности лишние ФЗ;
   2. если в классе эквивалентности осталось больше одной ФЗ, то выбрать ФЗ с меньшим числом атрибутов в левой части;
   3. если у оставшихся ФЗ число атрибутов в левой части одинаково, то выбрать ту ФЗ, которая позволит редуцировать (вычеркнуть) атрибуты справа у ФЗ, расположенных выше в графе иерархии;
   4. если в результате не удалось выбрать ни одной, то выбрать произвольную;
7. редуцировать атрибуты справа в оставшихся ФЗ. Для этого просмотреть каждый путь снизу вверх в графе иерархии. Двигаясь по выбранному пути, выполнить следующие действия в каждом узле пути:
   1. пусть $Xrightarrow Y$ — это ФЗ, записанная в данном узле. Каждый атрибут, принадлежащий правой части, вычеркнуть в правых частях ФЗ, расположенных в узлах этого пути по иерархии выше;
   2. для тривиальной ФЗ $Urightarrowvarnothing$ атрибуты вычёркиваются слева;
8. исключить из рассмотрения ФЗ с пустой правой частью (кроме редуцированной ФЗ $Urightarrowvarnothing$). Исключённые на этом шаге ФЗ являются лишними и выводятся из оставшихся;
9. каждую оставшуюся в графе иерархий ФЗ $Vrightarrow W$ заменить на множество $VW$. Получившееся множество схем отношений обозначить как $rho$;
10. для полученной на предыдущем шаге схемы БД проверить:
    1. обладает ли она свойством соединия без потерь. Если не обладает, то добавить ключ универсальной схемы $U$ в эту схему;
    2. обладает ли $rho$ свойством сохранения ФЗ. Если нет, то, использовать зависимости, не вошедшие в проекцию $Xrightarrow YnotinPi_{R_i}(F)$, для построения новых схем отношений, то есть добавить в $rho$ $XY$.

После выполнения всех шагов полученная схема $rho$:

• обладает свойством соединения без потерь;
• обладает свойством сохранения ФЗ;
• находится в 3НФ или НФБК;
• содержит минимальное число схем отношений.

Пример

$U = (поставщик, фирма, деталь, количество) = (A, B, C, D)$

$F = (Arightarrow B, Brightarrow A, ACrightarrow D, BCrightarrow D)$

Строим $rho$:

1)

$УНП = (Arightarrow B, Brightarrow A, ACrightarrow BD, BCrightarrow AD)$

2)

пропускаем этот шаг, так как есть ФЗ (даже не одна), включающая все атрибуты из $U$

3)

уменьшить число атрибутов не удаётся

4)

1 класс: $Arightarrow B$, $Brightarrow A$, $K_1 = AB$

2 класс: $ACrightarrow BD$, $BCrightarrow AD$, $K_2 = ABCD$

5)

6)

для $K_2$:

способ 1 — как во втором семинаре

можно ли вывести $ACrightarrow BDin(BCrightarrow AD)^+$?

$(AC)^+=AC$, $BDnsubseteq(AC)^+$, значит нельзя

можно ли вывести $BCrightarrow ADin(ACrightarrow BD)^+$?

$(BC)^+=BC$, $ADnsubseteq(BC)^+$, значит нельзя

способ 2 — вычеркнуть из правых частей ФЗ рассматриваемых классов эквивалентностей общие атрибуты. Если получаются ФЗ с пустой правой частью, то они являются лишними.

$ACrightarrow B$

$BCrightarrow A$

выше по иерархии ничего нет, выбираем $BCrightarrow AD$

нет лишних ФЗ, потому…

для $K_1$:

продолжение…