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

УДК 681.3.07

Россия, МГТУ им. Н.Э. Баумана

breshenkov@rambler.ru

Введение

Вопросам проектирования реляционных баз данных (РБД) посвящен ряд теоретических и практических исследований [1-5, 8]. Однако возможности существующих методов и средств проектирования РБД далеко не исчерпаны. В частности представляют интерес методы проектирования РБД на основе анализа существующей информации.

В работах [6, 9, 8, 11] обоснована актуальность разработки методов и средств автоматизированного преобразования информации табличного типа (ИТВ) в реляционные таблицы (РТ). Актуальность преобразования связана с тем, что, с одной стороны, при наличии  информации в ИТВ возможна формализация процесса проектирования реляционных баз данных, а, с другой стороны, расточительно не использовать существующие данные и возможности РБД. Предлагается разработать метод, который основываясь на разрабатываемых алгоритмах, преобразует модель ИТВ в модель РТ. Использование метода обеспечит использование ИТВ в РБД. В статье рассмотрены модели РТ и ИТВ.

1. Укрупненная модель реляционных таблиц

Практически во всех работах, посвященных РБД, сформулированы требования к РТ. Однако эти требования, как правило, представляют собой перечисление свойств, которыми должны обладать таблицы. Требования не формализованы, да они и не могут быть формализованы, т.к. РБД проектируются на основе схем отношений. Например, схема отношения "Студент" может иметь вид: "Студент" = (Фамилия, Имя, Отчество, Дата рождения, Дата поступления, Адрес,…, Средний балл). Требования же предъявляются к данным, а данных во многих случаях еще и нет. Они появятся потом в процессе эксплуатации БД и может оказаться, что сформулированные на начальных этапах проектирования требования к РТ не удовлетворяются. В частности, отталкиваясь от схемы отношения "Студент", вполне можно предположить, что сочетание Фамилия, Имя, Отчество вполне подходит для первичного ключа. Однако, как показывает опыт, даже в рамках одного факультета, нередко встречаются полные тезки. А основным требованием к первичному ключу является его уникальность.

Нередко исходная информация присутствует в виде ИТВ. В этом случае ситуация существенно меняется в лучшую сторону. Ведь на основе реальных данных вполне возможно формализовать требования к ним.

В работе [7] описана формальная модель РТ. Основные ее черты следующие. Реляционная таблица (RT) представляется множеством

RT={Z, D},

где Z – множество заголовков,  D -  множество данных.  

z = {z₁, …, z_i, …, z_n},  i = 1, n; n >= 1,                                                   (1)

где n - степень множества заголовков.

Должно быть обеспечено условие z_i ≠ z_m , i =1, n ; m = 1, n; i ≠ m,                       (2)

где n – степень множества заголовков, т.е. недопустимо совпадение заголовков.  

D = {SD},  где SD – множество строк данных.                                           (3)

SD = {SD₁, …, SD_i, …, SD_n}, i = 1, n; n >> 1,                                       (4)

где n - мощность множества строк данных. 

SD_i = {ED_i1, ..., ED_ij, …, ED_ik},  j₌ 1, k;  k >= 1,

где k - степень множества i-ой строки данных,  ED_ij– элемент данных.

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

SD_i ≠ z_j, i = 1, n; n >> 1;  j ₌ 1, k;  k >= 1,                                             (5)

где n - мощность множества строк данных, k - степень множества заголовков.

Для реляционных таблиц выполняется правило:

(∀ED) (ED∈SD) (∃z(z∈Z) (z↔ED))                                                  (6)

Т.е. каждому элементу данных соответствует только один заголовок.

(∀ED) (ED∈ SD ) (∃ (TED)  (ED ↔TED)),                                              (7)

где TED  = string V integer V datetime V real V logical.Т.е. каждому элементу данных соответствует определенный тип данных.

В реляционных таблицах обязательно выполнение следующего требования:

TED₁₁ =, …, = TED_i1 =, …, = TED_n1

… … … … … … … … … … …

TED_1j =, …, = TED_ij =, …, = TED_nj

… … … … … … … … … … …

TED_1k =, …, = TED_ik =, …, = TED_nk, i = 1, n;n >> 1;j ₌ 1, k;  k >= 1,  (8)

где n - мощность множества строк данных, k - степень множества i-ой строки данных; ED_ij– элемент данных. Другими словами, значения типов данных одного столбца должны совпадать.

Недопустима ситуация, когда SD_i = SD_j, i = 1, n; j = 1, n; i ≠ j,                              (9)

 где n – мощность множества данных. Т.е. невозможно полное совпадение строк данных.

Однако в данном случае отражены не все свойства реляционной модели данных (РМД), которые в числе прочих предполагается взять за основу при разработке метода преобразования ИТВ в РТ.

Несмотря на достоинства этой модели, она не в полном объеме отражает особенности РТ и соответственно не может в полной мере служить исходной формализацией для метода преобразования.

В реляционной модели данных [4] не предусмотрено наличие первичных ключей.

ПустьSD_i = {ED_i1, ..., ED_ij, …, ED_ik},  j₌ 1, k;  k >= 1,                         ( 10)

где SD_i   - i-я строка данных множества, k - степень множества,  ED_ij– элемент данных.

Тогда должен быть найден такой заголовок Z_i (Z_i↔ ED_ij), чтобы выполнялось выражение:

ED_{i1 ……}ED_ij…… ED_in   , где n – мощность множества                              ( 11)

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

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

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

Z_i                                                                                                                ( 12)

В реляционной модели данных не должно быть пустых строк:

SD_i ( 11)

В реляционной модели данных содержимое никакого столбца не может использоваться как подзаголовки.     ( 13)

В реляционной модели данных не должно быть сочетаний различного типа подзаголовков.    ( 14)

2. Укрупненная модель ИТВ

Если в предыдущем параграфе рассматривалось целевая модель данных РТ, то здесь разговор пойдет об исходной модели, которую необходимо преобразовать в форму РТ – модель ИТВ.

Модель ИТВ в известной литературе, как правило, не рассматривается. В работе [11] представлена неполная формализованная модель ИТВ, которая c модификациями может быть принята в качестве базовой для решения задач преобразования ИТВ в РТ. Рассмотрим эту модель.

Информация табличного вида (ИТВ) представляется множеством  DT = {Z, D},  где  Z – множество заголовков ИТВ, D - множество данных, соответствующим заголовкам.   (15)

Z = {Z₁, …, Z₂, …, Z_n},  i = 1, n; n >= 1,                                                                 (16)

где n - степень множества заголовков. 

Допустима ситуация, когда

Z_i = Z_m,  i = 1, n ; m = 1, n; i ≠ m ,                             (17)

где n– степень множества заголовков, т.е. возможно полное совпадение заголовков.

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

Z_i = {PZ_i1, …, PZ_ij, …, PZ_ik},  j₌ 1, k;  k >= 2,                                                        (18)

где k - степень множества подзаголовков i-го заголовка.        

Z_p= {PZ_p1, …, PZ_pt, …, PZ_pm}, t =1, m;  m >= 2,                                                     (19)

где m - степень множества подзаголовков p-го заголовка.        

Допустима ситуация, когда  PZ_ij = PZ_pt.                                                                 (20)

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

PZ_ij = {PPZ_ij1, …, PPZ_ijm, …, PPZ_ijf}, m = 1, f; f >= 2,                                            (21)

где f - степень множества подзаголовков 2-го уровня ij-го подзаголовка 1-го уровня.      

PZ_pt = {PPZ_pti, …, PPZ_ptr, …, PPZ_ptg}, r = 1, q; q >= 2,                                            (22)

где q - степень множества подзаголовков 2-го уровня pt-го подзаголовка 1-го уровня      

Допустима ситуация, когда 

PPZ_ijm= PPZ_ptm.                                                          (23)

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

На рис. 1 приведен реальный пример таблицы ИТВ с подзаголовками.

Рис. 1. Пример таблицы ИТВ с подзаголовками

Здесь заголовок ”Тип оборудования” включает в себя 7 подзаголовков, заголовок “Цена” включает в себя 2-а подзаголовка.

D = {SD, Z}, где SD – множество строк данных.                                  (24)

Такого рода представление D допускает наличие нескольких заголовков и подзаголовков 1-го и 2-го уровней, расположенных в области данных.

В том числе допускается наличие заголовков и подзаголовков, расположенных до, после и между строк данных. На рис. 2 приведен реальный пример таблицы ИТВ с заголовками внутри области данных. Таковыми являются строки 1 и 9 и др. Кроме того, на рисунке представлен внутренний подзаголовок более высокого уровня  “Собрать свой компьютер”.

Рис. 2. Пример таблицы ИТВ с заголовками внутри области данных

SD = {SD₁, …, SD_i, …, SD_n},  i = 1, n; n >> 1,                                       (25)

где n - мощность множества строк данных.

SD_i = {ED_i1, ...,ED_ij, …, ED_ik},  j₌ 1, k;  k >= 1,                                     (26)

где k - степень множества элементов данных i-ой строки данных;

      ED_ij– элемент данных. 

Для информации табличного вида должно выполняться следующее правило:

(∀ED) (ED∈ SD) (∃ z  (z∈ Z) (z«ED))  V (∃ (PZ)) (z∈ PZ) (PZ↔ ED) V (∃ (PPZ)) (PPZ∈ PZ) (PPZ↔ ED)          (27)

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

(∀ED) (ED ∈ SD ) (∃TED  (TED ∈ T(ED))),                                         (28)

где TED  = string V integer V  datetime, где   T(ED) - тип ED. 

Но каждому элементу данных соответствует какой-либо тип данных.

В общем случае:

TED₁₁≠, …, ≠TED_i1≠, …, ≠TED_n1

… … … … … … … … … … …

TED_1j≠, …, ≠TED_ij≠, …, ≠TED_nj

… … … … … … … … … … …

TED_1k≠, …, ≠TED_ik≠, …, ≠TED_nk,  i = 1, n; n >> 1; j₌ 1, k;  k >= 1,   (25)

где n - мощность множества строк данных, k - степень множества элементов i-ой строки данных. Другими словами, значения типов данных одного столбца могут не совпадать.

Допустима ситуация, когда  SD_i = SD_j , i = 1, n ; j = 1, n; i ≠ j ,         (26)

где n – мощность множества данных, т.е. возможно полное совпадение строк данных. 

В модели ИТВ могут быть пустые заголовки:

Z_i =                                                                                                         (27)

В модели ИТВ могут быть пустые строки:

SD_i=                                                                                                       (28)

В ИТВ содержимые столбца могут использоваться как подзаголовки таблиц.  (26)

В ИТВ могут быть сочетания различного типа подзаголовков          (27)

Несмотря на некоторое сходство модели таблиц ИТВ и модели РТ, в них имеются существенные различия.

Сравним выражения для РТ и ИТВ.

1.     Выражения (17-24)  для ИТВ противоречат выражению (2) для РТ.

2.     Выражения (27-28)  для ИТВ противоречат выражению (5) для РТ.

3.     Выражение (28-27)  для ИТВ противоречат выражению (12-14) для РТ.

4.     Выражение (25)  для ИТВ противоречат выражению (8) для РТ.

5.     Выражение (26)  для ИТВ противоречат выражению (9) для РТ.

Кроме того, в исходной модели РТ не предусмотрено наличие первичного ключа. Соответственно отсутствуют требования к первичному ключу.

Основной задачей метода преобразования ИТВ в РТ и является разработка  средств, которые бы позволили ликвидировать указанные различия в их моделях.

Заключение

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

Литература

1. Монографии, брошюры и т.п.:

1.       Ульман Д., Уидом Д. Введение в системы баз данных: Пер. с англ. - М.: Лори, 2000. – 319 с.

2.       Гэри Хансен, Джэймс Хансен. Базы данных: разработка и управление: Пер. с англ. - М.: Бином, 1999. – 699 с.

3.Агальцов В.П. Базы данных. - М.: Мир, 2002. – 375 с.

4.Ахаян Р., Горев А., Макатирипов С. Эффективная работа с СУБД. - СПб.: Питер, 1997. – 704 с.

5.Хоменко А.Д., Цыганков В.М, Мальцев М.Г. Базы данных: Учебник для высших учебных заведений / Под ред. Проф. А.Д. Хомоненко – 6-е изд. – М.:Бином-Пресс.:СПб КОРОНА-Век, 2007. – 736 с.

6.       Брешенков А.В., Гудзенко Д.Ю., Казаков Г.И. Проектирование реляционных баз данных на основе информации табличного типа. Учебное пособие- М.: Изд-во МГТУ им. Н.Э. Баумана, 2009 – 150 с.

7.       Брешенков А.В. Методы решения задач проектирования реляционных баз данных  на основе использования существующей информации табличного вида. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. – 154 с.

8.       Брешенков А.В., Балдин А.В. Анализ  проблемы  проектирования реляционных баз данных на основе использования информации табличного вида и разработка модели методики проектирования. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. – 150 с.

2. Периодические издания:

9.Аграновский А.В., Арутюнян Р.Э, Хади Р.А. Современные аспекты проблемы поиска в текстовых базах данных // Телекоммуникации. – 2003. - №3. - С. 25-23.

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

11.    Брешенков А.В., Бараков Д.Д. Вопросы преобразования электронных таблиц в таблицы реляционных баз данных // Современные информационные технологии: Cб. трудов каф., посвященный 175-летию МГТУ им. Н.Э. Баумана. - М.: Эликс +, 2004. – С. 44-50.