.: Компьютерный учебник- Процедурно-ориентированное программирование :.

.: [предыдущая | оглавление | следующая] :.

11.6 Базы данных

11.6.1 Общие сведения о базах данных

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

Развитие этого направления привело к понятию систем управления базами данных (СУБД). Эти системы обеспечивают некоторые универсальные средства для хранения и манипулирования данными. Как правило, СУБД - это инструментальная система программирования для создания корпоративных информационных систем. В основе которой лежит специальный алгоритмический язык. Боле подробное описание можно найти в литературе[ ]

В настоящее время имеется три основных модели, лежащих в основе построения баз данных: иерархические, сетевые и реляционные [ ]. Для исследования последней модели разработан специальный математический аппарат-реляционная алгебра[ ]. В настоящее время практически все СУБД основаны на реляционной модели представления данных.

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

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

11.6.2 Библиотека файловых функций io.h

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

Основные функции этой библиотеки следующие:

Эти функции похожи на функции, описанные в заголовочном файле stdio.h.

11.6.3 Физическая организация файла данных

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

// описание записи
typedef struct MyRecord
{
      char sdel; //признак удаления записи
      char Name[40]; //имя автора
      char Caption[255]; //название
      char Year[20]; //год издания
      int Pages; //количество страниц
      int Nal; //сколько имеется
} RECORD;

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

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

Итак, к данным можно добраться, зная индекс записи.

Формула вычисления адреса записи по ее индексу следующая:

Рассмотрим структура заголовка файла данных:: typedef struct MyBaseContBlock
{
      int n_rec; //количество записей
      int n_del; //количество удаленных записей
      int hand; //дескриптор файла
      int sizeBCB; //размер блока
      int sizeRecord; //длина записи
      long sizeBase; //длина файла (базы данных)
} BCB;

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

11.6.4 Основные функции для работы с файлом данных

Основные функции следующие:

Функция открыть или создать файл данных проверяет наличие файла данных с таки именем, если нет то создает заголовок и записывает его в новый файл. Если такой файл существует, то открывает его и читает заголовок файла данных и заполняет структуру BCB. Далее все остальные функции могут работать с файлом, используя структуру BCB.

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

int OpenBase(char* NameBase,BCB *b)
{
      int fm;
      if(access(NameBase, 0) != 0)
      {//файл с таким именем не существует?
            Init(b); //да - создать
            fm=open(NameBase,O_CREAT|O_RDWR|O_BINARY,S_IREAD|S_IWRITE
            if(fm==-1)
            {//обработка ошибки
                  printf("Error open base: errno- %d \ n",errno);
                  return -1;
            }
            b->hand=fm; //установить дескриптор
            write(fm,b,sizeof(BCB)); //записать блок управления
            PrintBCB(b); //печать блока управления
      }
      else
      { //база данных существует
            fm=open(NameBase,O_CREAT|O_RDWR|O_BINARY);
            if(fm==-1)
            { //обработка ошибки
                  printf("Error open base: errno- %d\n",errno);
                  return -1;
            }
            read(fm,b,sizeof(*b)); //читать заголовок
            b->hand=fm; //установить дескриптор
            PrintBCB(b); //печать блока управления
      }
      return 1;
}

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

void CloseBase(BCB *b)
{
      lseek(b->hand,0L,SEEK_SET); //сбросить указатель файла в начало
      write(b->hand,b,sizeof(BCB)); //записать новое значение бока управления
      close(b->hand); //закрыть файл
      b->hand=-1; //сбросить дескриптор файла
}

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

void AddRecord(BCB *b,RECORD *rec)
{
      lseek(b->hand,0L,SEEK_END); //указатель файла переместить в конец
      write(b->hand,rec,b->sizeRecord); //произвести запись
      b->n_rec++; //увеличить счетчик записей
}

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

void ReadRecord(BCB *b,int addr,RECORD *rec)
{//вычислить и переместить указатель файла на заданную запись
lseek(b->hand,(b->sizeBCB+addr*b->sizeRecord),SEEK_SET);
read(b->hand,rec,b->sizeRecord); //читать запись
}

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

void RewriteRecord(BCB *b,int addr,RECORD *rec)
{//вычислить и переместить указатель файла на заданную запись
lseek(b->hand,(b->sizeBCB+addr*b->sizeRecord),SEEK_SET);
write(b->hand,rec,b->sizeRecord); //произвести новую запись
}

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

void DeleteRecord(BCB *b,int addr)
{
      char sdel=’*’;
      if(addr>=b->n_rec) return; //неверный номер записи
      //вычислить и переместить указатель файла на заданную запись
      lseek(b->hand,(b->sizeBCB+addr*b->sizeRecord),SEEK_SET);
      write(b->hand,&sdel,1); //произвести логическое удаление записи
      b->n_del++;
}

Функция сборки мусора производит физическое удаление записей из файла данных. Реорганизацию файла данных можно осуществить двумя путями: Перезапись всех не удаленных записей данных в текущем файле данных ( упаковка) и второй это создание нового файла и запись в новый всех действительных записей. После выполнения операции старый файл удаляется, а новый переименуется. Второй вариант более надежен, т.к. при сбое в первом случае можно потерять информацию, во втором случае информация не теряется, т.к. старый удаляется после создания нового. Ниже представлен текст функции сборки мусора по второму варианту. При этом используется две стандартные функции. Функция unlink производит удаление указанного файла, описана в io.h. Вторая функция rename переименовывает файл с именем, указанном в первом аргументе, на имя указанное во втором аргументе, описана в stdio.h.

void Sborka(BCB *b)
{
      BCB nb;
      RECORD rec;
      if(OpenBase("tmp$$$.dat",&nb)==-1) //создать новую базу
      return;
      for(int i=0; i<b->n_rec; i++)
      { //прочитать все записи в файле данных
            ReadRecord(b,i,&rec);
            if(rec.sdel!=’*’) //эта запись удалена?
                  AddRecord(&nb,&rec); //нет, записываем в новую.
      }
      CloseBase(&nb); //закрыть новую базу
      CloseBase(b); //закрыть старую базу
      unlink("mybook.dat"); //удалить старую
      rename("tmp$$$.dat","mybook.dat"); //переименовать новую в старую
}
//Удалить базу
void DeleteBase()
{
      if(unlink("mybook.dat")) //удалить
            printf("Error open base: errno- %d\n",errno);
}
//печать блока управления
void PrintBCB(BCB *b)
{
      printf("BCB: number of record %d\n",b->n_rec);
      printf("BCB: number of delete record %d\n",b->n_del);
      printf("BCB: size of BCB: %d\n",b->sizeBCB);
      printf("BCB: size of record: %d\n",b->sizeRecord);
      printf("BCB: size of base: %d\n",b->sizeBase);
}
//инициализация блока управления
void Init(BCB *b)
{
      b->n_rec=0;
      b->n_del=0;
      b->sizeBCB=sizeof(BCB);
      b->sizeRecord=sizeof(RECORD);
      b->sizeBase=200000;
}
#include <stdio.h>
#include <io.h>
#include <fcntl.h>
#include <string.h>
#include <sys\stat.h>
#include <errno.h>
#include <conio.h>
#include <stdlib.h>
#include <mem.h>
// описание блока управления базой данных
//печать записи
void PrintRecord(RECORD *r)
{
      printf("%c %s %s %s %d %d\n",r->sdel,
      r->Name,r->Caption,r->Year,r->Pages,r->Nal);
}
//Сгенерировать и записать nrec записей в базу данных
void CreateBase(int nrec,BCB *b)
{
      RECORD r;
      int i, k;
      char bu[10];
      randomize(); //используется датчик случайных чисел
      for(i=0; i<nrec; i++)
      {
            k=random(100);//получить номер автора
            sprintf(bu,"%d",k);
            strcpy(r.Name,"Author");
            strcat(r.Name,bu);
            k=random(100); //получить номер книги
            sprintf(bu,"%d",k);
            strcpy(r.Caption,"Book");
            strcat(r.Caption,bu);
            k=1900+random(104); //получить год издания
            sprintf(bu,"%d",k);
            strcpy(r.Year,bu);
            r.Pages=100+random(100); //получить количество страниц
            r.Nal=1+random(20);//получить количество имеющихся книг
            AddRecord(b,&r);
      }
}

11.6.5 Индексные файлы

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

Индексным файлом называется файл, содержащий индексы записей файла данных в соответствии с некоторым критерием сортировки. Таким образом, для одного файла данных может быть несколько индексных файлов.

Рассмотрим построение индексного файла для нашего примера. Индексный файл создается на основе сортировки файла данных по какому либо критерию. Поэтому для создания индексного файла необходимо задать критерий сортировки (или ключ сортировки). В нашем случаем в качестве ключа выбрано поле Name в структуре записи (сортировка по имени автора книги).

Функция создания индексного файла CreateIndex. Это упрощенный пример сортировки фала данных и создание упорядоченного индексного файла. Первоначально распределяется память под массив индексов и он инициализируется. Далее он упорядочивается в соответствии с алгоритмом лексикографического упорядочения (см. раздел Сортировка строк). После сортировки массив записывается в файл.

void CreateIndex(BCB *b)
{
      int key=1;
      int tmp;
      RECORD rec1, rec2;
      int *index=(int*)malloc(sizeof(int)*b->n_rec);
      for(int i=0; i<b->n_rec; i++) index[i]=i;
      while(key)
      {
            key=0;
            ReadRecord(b,index[0],&rec1);
            for(int i=1; i<b->n_rec; i++)
            {
                  ReadRecord(b,index[i],&rec2);
                  if(strcmp(rec1.Name,rec2.Name)>0) {
                        tmp=index[i-1];
                        index[i-1]=index[i];
                        index[i]=tmp;
                        key=1;
                  }
                  else
                        memcpy(&rec1,&rec2,sizeof(RECORD));
            }
      } //end while
      int fm=open("mybook.inx",O_CREAT|O_RDWR|O_BINARY,
      S_IREAD|S_IWRITE);
      if(fm==-1){ //обработка ошибки
            printf("Error open base: errno- %d\n",errno);
            return;
      }
      write(fm,index,sizeof(int)*b->n_rec); //записать индексы
      close(fm);
}

Функция ViewIndex предназначена для выдачи всего файла данных в соответствии со следованием индексов в индексном файле. Используется функции ReadRecord и PrintRecord

void ViewIndex(BCB *b)
{
      RECORD rec;
      int *index=(int*)malloc(sizeof(int)*b->n_rec);//распределяем память
      //открываем файл
      int fm=open("mybook.inx",O_CREAT|O_RDWR|O_BINARY,
      S_IREAD|S_IWRITE);
      if(fm==-1)
      {//обработка ошибки
            printf("Error open base: errno- %d\n",errno);
            return;
      }
      read(fm,index,sizeof(int)*b->n_rec);//читать индексы
      close(fm);
      for(int i=0; i<b->n_rec; i++)
      {
            ReadRecord(b,index[i],&rec);
            printf("%d index=%d rec:",i,index[i]);
            PrintRecord(&rec);
      }
}

Функция FindName производит быстрый поиск нужной записи по полю Name. Поиск организован следующим образом, задается интервал индексов g1 и g2, первоначально интервал охватывает весь файл индексов. Затем берется середина интервала, читается запись и сравниваются - поле Name и заданная строка, используя функцию strcmp. Далее если строки совпали (равенство нулю), то нужную запись нашли. Если strcmp вернула 1, то g2 = addr (смещение влево относительно середины addr), в противном случае смещение вправо g1=addr. Поиск будет производиться пока либо не найдется запись, либо интервал не станем равным единице.

int FindName(BCB *b,char *Name, RECORD *rec)
{
      int g1,g2;
      int res, addr, newaddr;
      int *index=(int*)malloc(sizeof(int)*b->n_rec);
      int fm=open("mybook.inx",O_CREAT|O_RDWR|O_BINARY,
      S_IREAD|S_IWRITE);
      if(fm==-1)
      { //обработка ошибки
            printf("Error open base: errno- %d\n",errno);
            return -1;
      }
      read(fm,index,sizeof(int)*b->n_rec);//читать индексы
      close(fm);
      addr=(b->n_rec-1)/2;//середина
      g1=0; g2=b->n_rec-1;
      while(1)
      {
            ReadRecord(b,index[addr],rec);
            printf("%d index=\d rec:",addr,index[addr]);
            PrintRecord(rec);
            if((res=strcmp(rec->Name,Name))==0) return 1;
            else
                  if(res>0) g2=addr-1;
                  else g1=addr+1;
            newaddr=g1+(g2-g1)/2;
            if(addr==newaddr) return 0;
            addr=newaddr;
      }//end while
}

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

11.6.6 Функции диалога для ввода записи, манипуляции с записями в базе, манипуляции с самой базой данны

//ввод записи
void InputRecord(RECORD *r)
{
      char ch;
      char str[80];
      setmem(r,sizeof(RECORD),0);//очистить буфер записи
      while(1) { //цикл для ввода полей записи
            puts("1-Name; 2-Caption; 3-Year; 4-Pages; 5-Nal;
            6-View; esc-Exit");
            ch=getch();
            printf("%c\n",ch);
            switch(ch)
            {
                  case ’1’: printf("Name>"); gets(r->Name); break;
                  case ’2’: printf("Caption>"); gets(r->Caption); break;
                  case ’3’: printf("Year>"); gets(r->Year); break;
                  case ’4’: printf("Pages>"); gets(str); r->Pages=atoi(str)
                  break;
                  case ’5’: printf("Nal>"); gets(str); r->Nal=atoi(str);
                  break;
                  case ’6’: PrintRecord(r); break;
                  case 27: return;
            }
      }
}

Функция для ввода, чтения, перезаписи, добавления, просмотра и удаления записей

Функция Work организует простой диалог для работы с базой данных.

.: [предыдущая | оглавление | следующая] :.