Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Методика назначения ключевых полей в заполненных реляционных таблицах

#5 май 2004
автор: Брешенков А. В.

В работе [1] обоснована актуальность проблемы  преобразования информации табличного вида в таблицы базы данных (БД), выполнена неформальная постановка задачи такого преобразования. Основными аспектами постановки задачи являются: формирование реляционных таблиц на основе информации, представленной в табличной форме, назначение ключевых полей в таблицах, формирование связей между таблицами. Каждый аспект задачи нетривиален, нуждается в формализованном подходе к его решению и зависит от множества факторов. В статье рассмотрена одна из составляющих задачи преобразования – назначение ключевых полей.

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

Первичный ключ должен удовлетворять требованиям уникальности и минимальности. Уникальность ключевого поля обеспечивает одно из требований целостности БД – целостность согласования. Минимальность ключевого поля обеспечивает эффективное использование памяти БД. Эти требования часто противоречат друг другу – т.к. сложный ключ (ключ, состоящий из нескольких полей) с большей вероятностью будет уникальным, однако для него в БД будет отводиться больше памяти. В связи с этим необходим разумный компромисс. Кроме того, выбор или назначение первичного ключа существенно зависит от количества столбцов в таблице. Так, например, в Oraclе8 для таблиц в один столбец предусмотрена возможность не выделения дополнительной памяти под ключевое поле.

В современных системах управления БД (СУБД) обеспечивается возможность использования до 1000 столбцов. Поэтому теоретически сложный ключ может состоять из 1000 полей, что, конечно, абсурдно. Кроме того, при выборе или назначении ключевого поля необходимо учитывать типы и размеры полей. В частности, поле типа MEMO нельзя использовать в качестве ключевого поля. Учитывая сказанное, предлагается методика назначения первичных ключей в таблицах с данными. Логично выделить 3 ситуации: таблица состоит из одного поля; таблица состоит из нескольких полей, число которых не равно максимально возможному количеству полей для конкретной СУБД; таблица состоит из полей, число которых равно максимально возможному количеству полей для конкретной СУБД.

Если таблица состоит из одного поля, то его естественно назначить в качестве первичного ключа. Однако это решение может быть придется пересмотреть в процессе формирования связей между таблицами. В частности, если эта таблица с одним атрибутом справочного характера и ее поля используются для выбора значения поля для другой таблицы, то этот атрибут нельзя задействовать в качестве первичного ключа. Множество атрибутов таблицы в случае одного поля вырождается в один атрибут: А = {А1}. Множество значений по этому атрибуту: {К1 = К11, К1 2,…, К1 n} должно удовлетворять требованию уникальности, т.е. К1i К1j; i = 1, n; j = 1, n; i j . Для обеспечения этого необходимо на основе отношения R1 степени 1 построить другие отношения R2 степени 1, мощность которого будет меньшей или равной мощности отношения R1. В терминах SQL необходимо выполнить следующий запрос на создание таблицы: SELECT DISTINCT R1.A1 INTO R2 FROM R1;

Однако, такое решение возможно только в том случае, если тип атрибута А1 не является MEMO, OLE, LOB (в различных СУБД свои типы). В такой ситуации необходимо сформировать новое отношение R3 на основе отношения R1 с множеством атрибутов А = {А1, А2}. При этом необходимо сформировать n значений по атрибуту К2 = {К21, К2 2,…, К2 n}. Причем необходимо обеспечить условие К2i К2j; i = 1, n; j = 1, n; i j.

В физической реализации это сводится к назначению нового поля в таблицу, все значения которого уникальны. Проще всего в данном случае назначить новому полю тип – “счетчик”. Тогда автоматически сформируются уникальные значения этого поля для всех записей таблицы. Следует иметь в виду, что не во всех СУБД реализована возможность определения новых полей в заполненных таблицах, а тем более назначения их ключевыми. Поэтому эти манипуляции надо выполнять в СУБД, в которых они допустимы (например, в Access), а затем экспортировать преобразованные таблицы в целевую СУБД.

Если таблица включает в себя несколько полей, число которых не равно максимально возможному для инструментальной СУБД, то необходимо найти такое сочетание атрибутов, чтобы для всех записей таблицы их значения были бы уникальны. Пусть отношение R1, на котором построена таблица базируется на p – атрибутах А = {А1, А2, …, Аp}. Атрибут Ai имеет в таблице множество значений Кi = {Кi1, Кi2, …, Кin}. Атрибут Aj имеет в таблице множество значений Кj = {Кj1, Кj2, …, Кjm}. Так как при этом анализируемая таблица имеет фиксированное количество записей, то n и m имеют конкретные значения и в рассматриваемом случае n = m и равно числу записей таблицы. Необходимо найти кортеж атрибутов КА = {КА1, КА2, …, КАr} КА Й А такой, что все кортежи их значений были уникальны. В таком случае мы имеем r-множество значений по числу атрибутов в кортеже КА, мощность каждого множества n – по числу строк

КК1 = {КК11, КК12, …, КК1n}

                        …

ККi = {ККi1, ККi2, …, ККin}

                        …

ККr = {ККr1, ККr2, …, ККrn}

Тогда должно быть выполнено условие:

{КК11, …, ККi1, …, ККr1} {КК12, …, КKi2, …, ККr2}

{КК1n, …, КKin, …, ККrn}     (1)

Таким образом, необходимо выбрать кортеж атрибутов КА, чтобы выполнялось условие (1), которое обеспечивает уникальность сложного ключа. С другой стороны важно обеспечить другое требование к первичному ключу – минимальность. Для реализации этого требования нужно стремиться к минимизации числа полей, входящих в первичный ключ, т.е. к минимизации размера кортежа КА. Кроме того, необходимо учитывать длину полей и в качестве претендентов на поля, включаемые в первичный ключ, выбирать поля с минимальной длиной. Кроме того, нельзя рассматривать в качестве претендентов на поля, включаемые в первичный ключ поля с определенными типами – MEMO, OLE ,LOB.

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

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

Формализованная методика выглядит следующим  образом. Поиск оптимистичного варианта состоит в следующем: перебираются все атрибуты Ai; i=1,r; Ai О A; ТАi N, где ТА –  тип атрибута, N = {MEMO, OLE, LOB}.

Для  каждого атрибута проверяется условие (1). В этом случае каждое множество выражается в один элемент, и условие выглядит следующим образом:

{KKi1} {KKi2} {KKin}

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

П1. Для множества LA = {LA1, … LAi, …,LAr} ищется min(LA), где LAi -  длина атрибута Ai (физически это выражается количеством байтов, отводимым для значений Ai).

П2. Предположим min(LA) = LАk. Тогда выполняется анализ всех возможных пар атрибутов Ak и Ai, i k, i = 1, r, r – число атрибутов таблицы и проверяется условие (1), которое в этом случае будет выглядеть следующим образом:

{KKk1, KKi1} {KKk2, KKi2} {KKkn, KKin}, n – число строк таблицы. Если данное условие выполняется, то запоминается атрибут Ai и его длина.

П3. После завершения перебора ищется min (LAN), где LAN – длины найденных атрибутов. Предположим min(LAN) = LAq, тогда в качестве первичного ключа назначается сложный ключ  AkAq.

П4. Если условие (1) не выполняется ни для одной пары атрибутов Ak и Ai, то ищется min (LA-1), где LA-1 = {LA1, …, LAi, …LAp-1}, LAk П LA-1 . Предположим min (LA-1) = LAk1, тогда выполняется анализ всех возможных пар атрибутов Ak1 и Ai   i  k,  i k1,  i = 1, r-1 и проверяется условие (1) по аналогии с П2. Далее выполняется действие  аналогичные действиям П3. Если условие (1) не выполняется ни для одной пары атрибутов Ak1 и Ai, то ищется min (LA-2), где LA-2 = {LA1, …LAi, … LAp-2}, LAk П LA-2  , LAk1 П LA-2

Итерации такого рода осуществляются до тех пор, пока не выполнится условие (1) или не исчерпаются все атрибуты таблицы.

Если условие (1) так и не выполнилось, то это означает, что первичный ключ на основе 2-х атрибутов назначить невозможно. В случае наличия в таблице всего 2-х атрибутов необходимо ввести дополнительное поле и назначить его ключевым.

Если в таблице более 2-х атрибутов и ключ из 2-х атрибутов сформировать не удалось необходимо найти компромисс между введением дополнительного неинформативного атрибута и неоправданным использованием памяти для сложного ключа из 3-х полей. Для этого надо “измерить” суммарные длины всех возможных сочетаний троек  атрибутов (в случае 3-х атрибутов будет одно сочетание). Если минимальная суммарная длина сочетания превышает 4 байта, то компромисс разрешается в пользу введения дополнительного поля и назначения его ключевым. В противном случае имеет смысл попытаться найти 3-и атрибута для формирования сложного ключа.

Суммарная длина сравнивается с 4-я байтами в связи с тем, что поле типа “счетчик”, которое имеет смысл использовать в качестве дополнительного имеет длину 4 байта.

 В формализованном виде методика поиска первичного ключа выглядит следующим образом.

П1. Ищется min(LA3); LA3 =  {LA31, LA32, …LA3i, …LA3j, …LA3n};

LA3i  = length(Aqi + Api + Ati)

qi  =  1, n;  pi = 1, n;  ti = 1, n;   qi pi ti

LA3j = lenqth (Aqj + Apj + Atj);

qj  =  1, n;  pj = 1, n;  tj = 1, n;   qj pj tj;

(qi  qj ) Ъ  (pi pjЪ  (ti tj)

Если min(LA3) і 4 байт, то поиск атрибутов, из которых можно сформировать первичный ключ прекращается, вводится дополнительный атрибут и назначается ключевым. В противном случае выполняется переход к П2.

П2. Предположим, что min(LA3) = LA3k, тогда анализируется AK = {Aqk, Apk, Atk}; AKМA

Имеется 3 множества значений атрибутов:

KKqk   =  {KKqk1, …, KKqki, …,  KKqkn}

KKpk   =  {KKpk1, …, KKpki, …, KKpkn}

KKtk   =   {KKtk1, …,  KKtki, …,  KKtkn},

где n – число записей таблицы.

Необходимо проверить условие:

{KKqk1, KKpk1,…,KKtk1}, …,{KKqki, KKpki, KKtki},…,{KKqkn, KKpkn, KKtkn}(2)

Если это условие выполняется, то тройка атрибутов АК принимается в качестве сложного ключа. Процесс завершается. В противном случае выполнятся переход к П3.

П3. Ищется min(LA3-1);  LA3-1 М LA3; LA3k П LA3.

Предположим, что min(LA3-1) = LA3k1 . Если LA3k1 і 4 байт, то вводится дополнительный атрибут и назначается ключевым. Процесс завершается. В противном случае анализируется тройка атрибутов АК1 по аналогии с П2. Если условие (2) выполняется, то тройка атрибутов АК1 принимается в качестве сложного ключа и процесс завершается. В противном случае ищется min(LA3-2);  LA3-2 М LA3; LA3k П  LA3; LA3k1 П LA3 и выполняется анализ в соответствии с П3.

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

Если в процессе поиска 3-х ключевых атрибутов с уникальными значениями таковых не найдется, то распространять поиск на 4-е и более атрибутов не имеет смысла. Исходя из опыта работы с СУБД, сделан вывод, что использование 4-х и более полей для формирования сложного ключа неоправданно. Это связано с тем, что в подавляющем большинстве случаев их суммарная длина велика и, кроме того, более 4-х полей, входящих в ключевое поле, плохо воспринимаются пользователями БД. Это экспериментально доказано при выполнении ряда реальных разработок. В этом случае вводится дополнительное поле и назначается ключевым.

В третьей ситуации, когда таблица состоит из полей, число которых равно максимально возможному количеству полей конкретной СУБД, поиск атрибутов для формирования первичного ключа осуществляется в соответствии с методикой, рассмотренной выше. Однако когда возникает необходимость введения нового поля и назначения его в качестве ключевого, то это выполнить невозможно, т.к. будет превышено допустимое число атрибутов. Такое случается редко. Если же это произошло необходимо выделить все атрибуты, у которых все значения пустые. Как показывает опыт, такие атрибуты, как правило, находятся - столбцы сформированы на всякий случай. Затем нужно предложить потенциальному пользователю БД выбрать из числа найденных атрибутов ненужный, переопределить его тип и назначить ключевым. Если же пользователь БД настаивает на необходимости всех атрибутов, то нужно проанализировать таблицу на возможность нормализации (в некоторых СУБД, в частности в Access, это можно автоматизировать). Если нормализация возможна, то таблица преобразуется в две и более таблиц, а их первичные и внешние ключи назначаются, исходя из условий нормализации. Процесс же назначения ключевых полей в данном случае в основном относится к аспектам формирования реляционных таблиц на основе информации, представленной в табличной форме и формированию связей между таблицами, которые обозначены в начале статьи и в этой работе не рассматриваются. Если рассматриваемая таблица не нормализуется, то ее можно разбить на две таблицы, затем в каждой таблице ввести дополнительные поля, назначить их ключевыми и реализовать связь один к одному по этим полям.

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

 

Литература

 

 1. БрешенковА.В., Бараков Д.Д. Неформальная постановка проблемы преобразования   информации  табличного вида в файлы баз данных. Сборник трудов АУ МВД России "Актуальные вопросы использования информационных технологий в деятельности органов внутренних дел,-М.,2004., 15 с.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)