НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІНСТИТУТ КОМП'ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
/
Кафедра САПР
З В І Т
до лабораторної роботи №2
з курсу: “Організація Баз Даних та знань”
1.ТЕМА РОБОТИ
Прямий метод доступу до файлів на зовнішніх запам’ятовуючих пристроях
2.МЕТА РОБОТИ
Розглянути органiзацiю i ведення файлiв прямого доступу; набути практичнi навички у програмуваннi алгоритмiв доступу хешуванням.
3.ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Створити базу даних, для підтримки бази даних на тему «Ресторан», яка реалізовує наступні функції:
1.Створення файлу бази даних.
2.Друк бази даних.
3.Читання запису, за вказаним ключем.
4.Пошук за вказаним полем (до 3-х полів).
5.Вставка запису.
6.Видалення запису.
7.Модифікація запису.
Захист від переповнення – зв'язні блоки.
4.ТЕОРЕТИЧНІ ВІДОМОСТІ
Головною особливiстю прямого методу доступу є взаємна однозначна вiдповiднiсть мiж ключем запису i його фiзичною адресою. Фiзичне розмiщення запису визначається безпосередньо iз значення ключа.
Створивши файл прямого доступу i видiливши для нього необхiдну дiлянку пам’ятi, можна вставляти записи у будь-якi мiсця файла. Перевага такого пiдходу над послiдовною органiзацiєю файла полягає у тому, що вдається отримати запис за заданим значенням ключа без попереднього перегляду всiх попереднiх записiв файла.
На практицi кiлькiсть можливих значень ключiв набагато перевищує кiлькiсть реально присутнiх у будь-який момент значень цього ключа. У цьому випадку пряма адресацiя є невигiдною, оскiльки надто багато пам’ятi резервується длязаписiв, яких немає i нiколи не буде у файлi. Метод хешування дає змогу уникнути цього i водночас зберегти ефективнiсть, властиву прямiй адресацiї.
На основi iнформацiї про множину фактичних значень ключiв створюється файл прямого доступу з такою кiлькiстю записiв, яка дещо перевищує фактичне значення ключiв. Вибирається функцiя хешування, яка перетворює значення ключа кожного запису в адресу блока у файлi. Зрозумiло, що хеш-функцiя h - це функцiя, яка вiдображає принцип "багато в один".
Використовуючи хешування обчислюють номер блока для заданого значення первинного ключа. Вимоги до хеш-функцiї:
Забезпечення рiвномiрного розкиду значень ключiв по адресах блокiв.
Повинна якнайменше призводити до ситуацiї переповнення.
Повинна бути простою, тобто мiстити невелику кiлькiсть основних арифметичних операцiй.
ТЕКСТ ПРОГРАМИ
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace Laba2_blockBD
{
class Program
{
static string path = "default.txt";
static string second = "second.txt";
const int MAX_ZAP = 5;
static void Main(string[] args)
{
Console.WindowWidth = 195;
Console.WindowHeight = 40;
Console.WriteLine("////////////////////////////////////////////////////////////////////////////////////////");
Console.WriteLine("/ Лабораторна робота №2 /");
Console.WriteLine("/ Предметна область: Ресторан /");
Console.WriteLine("/ Виконав: студент КН-25 Омелян Дмитро /");
Console.WriteLine("////////////////////////////////////////////////////////////////////////////////////////");
menu();
Console.ReadLine();
}
static int menu_vvid()
{
try
{
int v = Int32.Parse(Console.ReadLine());
return v;
}
catch (FormatException)
{
return menu_vvid();
}
}
static void menu()
{
bool doit = true;
while (doit)
{
Console.WriteLine("\n=============================================================================================================================================================================================");
Console.WriteLine("Введiть номер команди \n1. Створення БД \n2. Друк БД \n3. Вставка запису \n4. Модифiкацiя записуч \n5. Видалення запису \n6. Читання запису за вказаним ключем \n7. Пошук запису \n8. Заверршення роботи з програмою");
int file_v = menu_vvid();
Console.WriteLine("=============================================================================================================================================================================================");
switch (file_v)
{
case 1:
creating();
break;
case 2:
show_zap();
break;
case 3:
{
Console.WriteLine("Введіть запис що бажаєте додати ");
add_zap(vvid_zapusy());
}
break;
case 4:
{
Console.WriteLine("Введіть запис що бажаєте модифікувати ");
mod_zap(vvid_zapusy());
}
break;
case 5:
vud_zapusy();
break;
case 6:
find_id_zap();
break;
case 7:
find_zap();
break;
case 8:
doit = false;
break;
default:
{
Console.WriteLine("Неправильно введена команда, введіть ще раз");
}
break;
}
}
}
static void creating()
{
Console.WriteLine("Введіть назву файлу (якщо БД(файл) було створено до того, то вона буде відкрита, у протилежному випадку буде створено нову БД)");
path = Console.ReadLine() + ".txt";
}
/// VVid zapusy ///////////////////////////////////////////////////////
static string vvid_zapusy()
{
Console.Write("Введіть id ");
string riadok = Console.ReadLine() + " ";
Console.Write("Введіть поставщика - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть страву - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть кількість порцій - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть чи наявна страва (y/n) - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть дату приготування - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть розділ - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть Вагу - ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть цiну- ");
riadok += Console.ReadLine() + " ";
Console.Write("Введіть рейтинг - ");
riadok += Console.ReadLine() + " ";
Console.WriteLine();
return riadok;
}
static void enter(string zapus, string way)
{
using (StreamWriter sw = new StreamWriter(way, true, System.Text.Encoding.Default))
{
sw.WriteLine(zapus);
}
}
static void add_zap(string str)
{
string[] zap = str.Split(' ');
int x = Int32.Parse(zap[0]);
int id = x % 10;
vvid_block(str, id + path);
}
static void vvid_block(string str, string path_blok)
{
if (File.Exists(path_blok) == false)
{
enter(str, path_blok);
}
else
{
string[] mas = File.ReadAllLines(path_blok);
string[] zap = str.Split(' ');
int x = Int32.Parse(zap[0]);
for (int i = 0; i < mas.Length; i++)
{
string[] stx = mas[i].Split(' ');
int y = Int32.Parse(stx[0]);
if (x == y)
{
Console.WriteLine("Запис з даним номером уже існує, модифікувати даний запис ? (y/n)");
string v = Console.ReadLine();
if (v == "y") mod_block(str, path_blok);
return;
}
}
if (mas.Length >= MAX_ZAP)
{
char s = path_blok[0];
vvid_block(str, s + path_blok);
}
else
{
enter_block(str, path_blok);
}
}
}
static void enter_block(string str, string path_blok)
{
string[] zap = str.Split(' ');
int x = Int32.Parse(zap[0]);
string[] mas = File.ReadAllLines(path_blok);
{
bool b = true;
int i = 0;
while (i < mas.Length)
{
string[] stx = mas[i].Split(' ');
int y = Int32.Parse(stx[0]);
if (x < y && b == true)
{
enter(str, second);
b = false;
}
else if (x != y)
{
enter(mas[i], second);
i++;
}
}
if (b == true)
{
enter(str, second);
}
File.Delete(path_blok);
File.Move(second, path_blok);
}
}
/// VuVid zapusy ///////////////////////////////////////////////////////
static void show_zap()
{
Console.WriteLine(" № \t Назва поставщика \t страва \t кількість порцій \t Наявність \t дата приготування \t розділ \t Вага \t Вартість \t Рейтинг ");
Console.WriteLine("запису \t \t \t \t \t \t \t \t \t ");
for (int i = 0; i < 10; i++)
{
Console.WriteLine("=============================================================================================================================================================================================");
show_block(i + path);
}
Console.WriteLine("=============================================================================================================================================================================================");
}
static void show_block(string path_block)
{
if (File.Exists(path_block) == false) return;
string[] mas = File.ReadAllLines(path_block);
for (int i = 0; i < mas.Length; i++)
{
string[] str = mas[i].Split(' ');
Console.WriteLine(str[0] + "\t " + str[1] + "\t " + str[2] + "\t " + str[3] + "\t\t " + str[4] + "\t " + str[5] + "\t " + str[6] + "\t\t " + str[7] + "\t\t" + str[8] + "\t\t " + str[9] + "\t\t" + path_block);
}
Console.WriteLine();
if (mas.Length >= MAX_ZAP)
{
char s = path_block[0];
show_block(s + path_block);
}
}
/// Modufikacia zapusy ///////////////////////////////////////////////////////
static void mod_zap(string str)
{
string[] zap = str.Split(' ');
int x = Int32.Parse(zap[0]);
int id = x % 10;
mod_block(str, id + path);
}
static void mod_block(string str, string path_blok)
{
if (File.Exists(path_blok) == false)
{
Console.WriteLine("Даного запису не знайдено, добавити його ? (y/n)");
string v = Console.ReadLine();
if (v == "y") vvid_block(str, path_blok);
}
string[] mas = File.ReadAllLines(path_blok);
string[] zap = str.Split(' ');
int x = Int32.Parse(zap[0]);
for (int i = 0; i < mas.Length; i++)
{
string[] zap0 = mas[i].Split(' ');
int y = Int32.Parse(zap0[0]);
if (x == y)
{
mas[i] = str;
File.Delete(path_blok);
for (int j = 0; j < mas.Length; j++)
enter(mas[j], path_blok);
return;
}
else if (y > x)
{
Console.WriteLine("Даного запису не знайдено, добавити його ? (y/n)");
string v = Console.ReadLine();
if (v == "y") vvid_block(str, path_blok);
return;
}
}
if (mas.Length >= MAX_ZAP)
{
char s = path_blok[0];
mod_block(str, s + path_blok);
return;
}
Console.WriteLine("Даного запису не знайдено, добавити його ? (y/n)");
string z = Console.ReadLine();
if (z == "y") vvid_block(str, path_blok);
}
/// Poshyk zapusyiv po ID////////////////////////////////////////////////////
static void find_id_zap()
{
Console.WriteLine("Введіть номер шуканого запису ");
int x = Int32.Parse(Console.ReadLine());
int id = x % 10;
bool b = find_id_block(x, id + path);
if (!b) Console.WriteLine("Запису не знайдено");
}
static bool find_id_block(int x, string path_block)
{
if (File.Exists(path_block) == false) return false;
string[] mas = File.ReadAllLines(path_block);
for (int i = 0; i < mas.Length; i++)
{
string[] str = mas[i].Split(' ');
int y = Int32.Parse(str[0]);
if (x == y)
{
Console.WriteLine("Результат пошуку\n");
Console.WriteLine(str[0] + "\t " + str[1] + "\t " + str[2] + "\t " + str[3] + "\t\t " + str[4] + "\t " + str[5] + "\t " + str[6] + "\t\t " + str[7] + "\t\t" + str[8] + "\t\t " + str[9] + "\t\t" + path_block);
return true;
}
}
if (mas.Length >= MAX_ZAP)
{
char s = path_block[0];
find_id_block(x, s + path_block);
}
return false;
}
/// Poshyk zapusyiv po zapusah////////////////////////////////////////////////
static void find_zap()
{
Console.WriteLine("=============================================================================================================================================================================================");
Console.WriteLine("Введіть команду \n 1. пошук запису за цiною \n 2. пошук запису за назвою поставщика ");
int x = Int32.Parse(Console.ReadLine());
Console.WriteLine("=============================================================================================================================================================================================");
switch (x)
{
case 1:
{
Console.WriteLine("Введіть шукану вартість");
string str = Console.ReadLine();
bool b = false;
Console.WriteLine("Результати пошуку:\n");
{
for (int i = 0; i < MAX_ZAP; i++)
{
if (find_block(str, i + path, 8, false) == true) b = true;
}
if (b == false) Console.WriteLine("Запису не знайдено");
}
}
break;
case 2:
{
Console.WriteLine("Введіть шукану фірму ");
string str = Console.ReadLine();
bool b = false;
Console.WriteLine("Результати пошуку:\n");
{
for (int i = 0; i < MAX_ZAP; i++)
{
if (find_block(str, i + path, 1, false) == true) b = true;
}
if (b == false) Console.WriteLine("Запису не знайдено");
}
}
break;
default:
Console.WriteLine("Неправильно введена команда");
break;
}
Console.WriteLine("=============================================================================================================================================================================================");
}
static bool find_block(string f_zap, string path_block, int n, bool b)
{
if (File.Exists(path_block) == false) return b;
string[] mas = File.ReadAllLines(path_block);
for (int i = 0; i < mas.Length; i++)
{
string[] str = mas[i].Split(' ');
if (f_zap == str[n])
{
b = true;
Console.WriteLine(str[0] + "\t " + str[1] + "\t " + str[2] + "\t " + str[3] + "\t\t " + str[4] + "\t " + str[5] + "\t " + str[6] + "\t\t " + str[7] + "\t\t" + str[8] + "\t\t " + str[9] + "\t\t" + path_block);
}
}
if (mas.Length >= MAX_ZAP)
{
char s = path_block[0];
find_block(f_zap, s + path_block, n, b);
}
return b;
}
/// Vudalenia zapusy////////////////////////////////////////////////
static void vud_zapusy()
{
Console.WriteLine("Введіть номер запису, що ви бажаєте видалити ");
int x = Int32.Parse(Console.ReadLine());
int id = x % 10;
bool b = vud_block(x, id + path);
if (b == false) Console.WriteLine("Даного запису не знайдено, тому і не видалено");
}
static bool vud_block(int x, string path_block)
{
if (File.Exists(path_block) == false) return false;
string[] mas = File.ReadAllLines(path_block);
bool b = false;
for (int i = 0; i < mas.Length; i++)
{
string[] zap = mas[i].Split(' ');
int y = Int32.Parse(zap[0]);
if (x == y)
{
b = true;
for (int j = 0; j < mas.Length; j++)
if (j != i) enter(mas[j], second);
if (File.Exists(second) == true)
{
File.Delete(path_block);
File.Move(second, path_block);
}
else File.Delete(path_block);
break;
}
}
if (b == true)
{
vud_zsyv(path_block);
}
else if (mas.Length >= MAX_ZAP)
{
char s = path_block[0];
return vud_block(x, s + path_block);
}
return b;
}
static void vud_zsyv(string path_block)
{
char s = path_block[0];
if (File.Exists(path_block) == false) return;
if (File.Exists(s + path_block) == true)
{
string[] mas = File.ReadAllLines(s + path_block);
enter_block(mas[0], path_block);
string[] str = mas[0].Split(' ');
int x = Int32.Parse(str[0]);
vud_block(x, s + path_block);
}
}
}
}
РЕЗУЛЬТАТ ВИКОНАННЯ
/
ВИСНОВКИ
На даній лабораторній роботі, я навчився створювати базу даних, побудовану на принципі прямого доступу до записів, а саме, за допомогою методу хешування. Створивши свою хеш-функцію, я отримав можливість доступу до окремих блоків, відповідно, це значно пришвидшує пошук, вставку, видалення і модифікацію.