Wykład 1
Wstęp
Jedną z podstawowych i najbardziej godnych uwagi cech współczesnych systemów komputerowych jest ich zdolność do przechowywania i obróbki gigantycznych ilości informacji.
Co to znaczy ilość informacji? Komputery wykonują operacje na bitach (cyfrach binarnych), ale w prawie wszystkich obecnie rozpowszechnionych komputerach podstawową jednostką danych jest bajt (8 bitów, 256 możliwych wartości). Również do kodowania danych tekstowych stosuje się reprezentację, w której każdej literze (i znakowi diakrytycznemu, cyfrze, ...) odpowiada 1 bajt (wyjątki: języki wschodnie, Unicode). Jest to dobrze znane kodowanie ASCII i jego rozszerzenia (iso8859-*, CP1250, ...). Pojemności pamięci, itp. podaje się więc w wielokrotnościach bajtu (2^10 B = 1 kB, 2^20 B = 1 MB, 2^30 B = 1 GB, ...). Niezgodność podanych przed chwilą definicji z dziesiętnym układem jednostek nie jest wielka (2^10 = 1024), ale czasami prowadzi do nieporozumień.
Aby sobie uzmysłowić, o jak wielkie ilości chodzi, rozważmy pojemność jednej płytki CD-ROM, bardzo dziś popularnego (i taniego) nośnika danych: 650 MB w przeliczeniu na strony tzw. znormalizowanego maszynopisu (1800 znaków) daje ponad 360,000 stron. Na stronie typowej drukowanej książki mieszczą się 2-3 strony maszynopisu, a więc (zakładając zapis informacji w postaci czysto tekstowej), na jednej płytce można pomieścić ponad 100,000 stron książek. Ile stron jesteś w stanie przeczytać przez całe życie? Niezłym tempem przy niezbyt nawet uważnym czytaniu jest 1 strona na minutę; 100,000 stron = 100,000 minut = ok. 1666 godzin = ok. 200 ośmiogodzinnych dni roboczych. (Nie sądzę jednak aby ktokolwiek był w stanie przeczytać 100,000 stron w ciągu roku).
Każdy użytkownik PC oczywiście wie, że podane powyżej liczby mają jedynie znaczenie ciekawostki. Znaczna część informacji z jaką mamy do czynienia (i jaką chcemy przechowywać i przetwarzać na komputerach) nie jest w postaci tekstowej, a komputerowe formy zapisu grafiki czy dźwięku są o wiele mniej wydajne. Również zapis tekstu jest o wiele mniej wydajny gdy chcemy go przechowywać w postaci uwzględniającej informację o jego formatowaniu czy strukturze logicznej (a więc szczególnie np. w postaci plików MS Word). Niemniej jednak jasne jest, że współczesna technika daje nam do ręki możliwości przechowywania i przetwarzania ogromnych ilości informacji, i to możliwości szeroko dostępne po przystępnych cenach. W chwili gdy piszę te słowa, typowa wielkość twardego dysku do komputera osobistego to 4.5 GB, a jego cena wynosi ok. 600 zł.
Z powyższego warto jednak zapamiętać, że postać ,,czysto tekstowa" jest niezwykle wydajna do przechowywania danych (w porównaniu z formatami stosowanymi w komercyjnych programach do obróbki tekstu jak MS Word, czy formatami ,,prezentacyjnymi" jak PostScript (Adobe) lub PDF (Adobe Acrobat). Co więcej, techniki kompresji danych działają całkiem wydajnie na plikach tekstowych (zapisanych w językach naturalnych, czy np. kodzie źródłowym języków programowania), umożliwiając kompresję w stosunku ok. 3/1. Ponadto, formaty ,,komercyjne" w wielu wypadkach podlegają częstym zmianom, nie posiadają publicznie dostępnych definicji, i tym samym są niemożliwe do odczytania bez korzystania z oprogramowania określonego producenta (a nieraz nawet ściśle określonej wersji programu). Natomiast format ASCII (lub pochodne -- np. HTML) z pewnością da się łatwo odczytać również i za 100 lat (o ile ktoś będzie tym jeszcze zainteresowany!). Wszystko to przemawia za jak najszerszym wykorzystaniem formatu tekstowego (i opartych na nim specjalnych formatów o publicznie znanej definicji, jak TeX, HTML, SGML), szczególnie do zapisu danych przeznaczonych do długoterminowej archiwizacji.
Opisanym tu imponującym możliwościom dostępnym obecnie w zakresie gromadzenia i przechowywania danych towarzyszy równie imponujący rozwój możliwości ich szybkiego przetwarzania (coraz szybsze procesory, coraz większe pojemności pamięci operacyjnych), oraz -- co nie mniej ważne -- rozwój sieci komputerowych umożliwiających zdalny dostęp do danych i dostęp do danych rozproszonych w niewyobrażalnym jeszcze niedawno zakresie. Wszystko to powoduje, że technologia baz danych -- a więc dziedzina zajmująca się sposobami organizacji zapisu, przechowywania, przetwarzania i udostępniania danych w ich postaci elektronicznej -- jest obecnie być może najważniejszym obszarem zastosowania techniki informatycznej i największą siłą napędową jej rozwoju. Ma to oczywiście wiele wspólnego z faktem, że elektroniczne przetwarzanie danych okazało się być potężnym narzędziem dla biznesu.
Powyższa definicja technologii baz danych wydaje się obejmować znaczną część techniki informatycznej wogóle. Rzeczywiście, ,,aspekt bazodanowy" jest w informatyce niemal wszechobecny (zobaczymy to poniżej na szeregu przykładów). Ze względów praktycznych warto jednak umówić się na nieco węższą definicję dziedziny technologii baz danych, w myśl której obejmuje ona systemy informatyczne (przede wszystkim oprogramowanie, ale aspekt sprzętowy również musi być brany pod uwagę), wyspecjalizowane w kierunku wprowadzania, przechowywania, przetwarzania i udostępniania dużych ilości danych w sposób strukturalnie zorganizowany. Trzeba jednak pamiętać, że (jak to zwykle bywa) granice tak określonej dziedziny są umowne i dość płynne. O bazie danych (w tym węższym znaczeniu) będziemy więc mówili wtedy, gdy zarządzanie danymi jest główną funkcją danego systemu informatycznego, a nie funkcją jedynie pomocniczą (oczywiście nie jest ono nigdy celem samym w sobie, ale to już inna historia).
Dane w plikach tekstowych - model rekord/pola
Podstawową strukturą służącą do trwałego przechowywania danych w postaci elektronicznej jest plik (file), będący (z naszego punktu widzenia) po prostu ciągiem bajtów o określonej (choć dość dowolnej) długości, zapisanym na urządzeniu zwanym pamięcią masową komputera (np. twardy dysk, dyskietka, taśma magnetyczna, płyta CDROM), dostępnym do odczytu i zazwyczaj (choć nie zawsze, np. CDROM) również do zapisu i modyfikacji. Pliki zorganizowane są w pewne struktury wyższego rzędu, zwane systemami plików, poprzez które system operacyjny komputera udziela użytkownikom (a dokładniej -- poszczególnym programom) dostępu do plików. Systemy plików zostaną pokrótce omówione dalej; obecnie rozważymy plik jako jednostkę danych.
Pliki mogą być wykorzystywane przez systemy operacyjne również i do innych celów aniżeli przechowywanie zapisanych w nich danych, nie będziemy się jednak tym tu zajmować.
O pliku tekstowym mówimy wtedy, gdy nie zawiera on bajtów spoza zakresu odpowiadającego kodom znaków służących do zapisu tekstu (litery, cyfry, znaki przestankowe, spacja) i niektórym kodom kontrolnym takim jak kod przejścia do nowego wiersza (\n), powrót karetki (\r), tabulator (\t) czy kod przejścia do nowej strony (\f). Ze względu na istnienie wielu różnych kodowań tekstu (stosowanych do zapisu tekstów w różnych alfabetach, choć nie tylko), nawet w ramach konwencji przyjętych w jednym systemie operacyjnym, definicja ta nie jest całkiem jednoznaczna; niektóre systemy operacyjne rozróżniają pliki tekstowe od binarnych na poziomie systemowym (DOS), inne nie (UNIX). W typowej sytuacji plik tekstowy dzieli się na pewną liczbę linijek (wierszy) tekstu, oddzielonych znakiem przejścia do nowego wiersza.
Jak już wspomniano, istnieje wiele różnych kodowań tekstu. Większość rozpowszechnionych obecnie kodowań stanowi rozszerzenia tzw. kodowania ASCII, będącego zatem ich ,,najmniejszym wspólnym mianownikiem".
Warto jednak wiedzieć, że szeroko stosowane systemy operacyjne różnią się co do konwencji dotyczącej separatora linijek tekstu: w systemach z rodziny UNIX separatorem wierszy jest znak nowej linijki (\n), w DOS (i Windows) sekwencja dwóch bajtów (\r\n), w systemach Apple kod powrotu karetki (\r).
Aby jednak można było mówić o najprostszym nawet przykładzie bazy danych, dane zapisane w pliku tekstowym powinny być ujęte w pewną dobrze określoną i dość sztywną strukturę; z jednej strony, struktura ta powinna jakoś odzwierciedlać znaczenie (semantykę) danych, a z drugiej -- umożliwiać pewną automatyzację operacji na danych. Najprostszym modelem takiej struktury jest przyjęcie podziału na tzw. rekordy, zapisywane jako wiersze pliku tekstowego, dzielące się z kolei na określoną liczbę pól, zapisywanych jako części wiersza oddzielone od siebie umownie przyjętym znakiem (lub sekwencją znaków) -- separatorem pól. Odpowiada to intuicyjnie zrozumiałej strukturze tabeli, w której każdy wiersz (rekord) odpowiada pewnemu elementowi opisywanego przez dane zbioru obiektów, a każde pole -- pewnemu określonemu atrybutowi tego obiektu.
Np. baza danych służąca jako prymitywny spis numerów telefonów mogłaby składać się z rekordów, z których każdy odpowiada jednej osobie i składa się z dwóch pól: zawierających odpowiednio nazwisko i numer telefonu.
Dla umożliwienia automatyzacji operacji na danych istotne jest, by liczba pól (oraz ich kolejność) w każdym rekordzie była dla danego zbioru danych ustalona; jeżeli przewiduje się wykonywanie na danych innych operacji poza wyszukiwaniem rekordów odpowiadających danemu kryterium, ich modyfikacja, usuwanie lub dopisywanie, to powinno się również ściśle ustalić format zapisu poszczególnych pól -- co umożliwi np. sumowanie wartości numerycznych z określonego pola wszystkich rekordów spełniających pewne kryterium (dotyczące zawartości pewnego pola). Liczba rekordów w tym modelu jest natomiast dość dowolna.
Niewątpliwą zaletą tak prostego modelu danych i ich zapisu jest właśnie jego prostota i czytelność, umożliwiająca np. ,,ręczne" wykonywanie operacji na danych za pomocą dowolnego edytora tekstu w sytuacji, gdy np. chodzi o operację rzadko wykonywaną czy ,,nietypową", której nie przewidziano projektując narzędzia do automatyzacji operacji na danym zbiorze danych. Inne zalety to: stosunkowa łatwość konstrukcji takich narzędzi -- szczególnie w systemach z rodziny UNIX dostępne są standardowo liczne programy narzędziowe, wprost idealnie przystosowane do operowania na danych tak zapisanych (zostaną one omówione poniżej); oraz łatwa przenośność zapisu danych (nie jest on ,,sztywno" związany z określonym oprogramowaniem).
Oczywiście, istnieje też szereg słabości tego modelu. Konieczna jest dbałość o integralność zapisu danych -- tj. o zgodność formy pól i rekordów z założonym wzorcem, której naruszenie może prowadzić do nieoczekiwanych (i niepożądanych) rezultatów. Sprawność operacji na danych maleje szybko ze wzrostem liczby rekordów oraz wielkości i liczby pól, choć za to nie ma potrzeby ścisłego definiowania z góry długości pola danych (poza ograniczeniami narzuconymi przez semantykę danych, tj. definicję formatu pól służącą automatyzacji pewnych operacji, o czym wspomniano powyżej). Trudności może wreszcie sprawić powiązanie ze sobą dwóch różnych zbiorów danych skonstruowanych w ten sposób, czy zapewnienie możliwości równoległej modyfikacji jednego zbioru danych przez różne osoby czy programy, bez naruszenia integralności danych. Niemniej jednak omawiany model zapisu danych całkiem nieźle się sprawdza w wielu zastosowaniach, szczególnie gdy liczba rekordów jest niewielka, składają się one z niewielu i raczej niewielkich rozmiarów pól, a przewidywane operacje na danych są raczej proste.
Narzędzia unixowe mogące służyć do operacji na tekstowych bazach danych
Omówię tu pokrótce narzędzia, które są standardowym wyposażeniem każdego systemu unixowego (Sun, HP, DEC, ..., BSD) czy unixo-podobnego (Linux), i które mogą być użyte w automatyzacji operacji na danych zapisanych w plikach tekstowych wg. prostego modelu opisanego powyżej (co nie znaczy, że nie mają one i innych zastosowań). Patrz rownież: szczegółowa dokumentacja tych (i szeregu innych) narzędzi, oraz wprowadzenie do metod ich stosowania.
* wc
wc [lista plików]
--> wypisuje, dla każdego pliku z listy argumentów, linię zawierającą trzy liczby, oznaczające liczbę linii (znaków nowego wiersza), wyrazów (napisów oddzielonych spacjami, znakiem nowej linii, tabulacji) i bajtów w pliku, oraz nazwę pliku. Jeżeli lista argumentów zawiera więcej niż jeden plik, wypisuje na końcu dodatkową linię zawierającą odpowiednie sumy i nazwę ,,total".
Opcje:
o -c podaje jedynie liczbę bajtów
o -w podaje jedynie liczbę wyrazów
o -l podaje jedynie liczbę linii
* grep
Przykład:
grep Jacek /etc/passwd
--> zwraca (na stdout) wszystkie linijki pliku /etc/passwd zawierające napis ,,Jacek" (zapewne będące rekordami wszystkich użytkowników danego komputera o imieniu ,,Jacek").
Opis: Pierwszym argumentem jest wzorzec wyszukiwania (w ogólności tzw. wyrażenie regularne), kolejne argumenty to nazwy plików podlegających przeszukaniu. Wynikiem domyślnym (wypisywanym do stdout) jest ciąg linijek z przeszukanych plików, zawierających napis pasujący do wzorca, pogrupowanych wg. plików, z każdą grupą poprzedzoną nazwą pliku z którego pochodzi (o ile podano więcej niż jedną nazwę pliku do przeszukania).
Szczególnie użyteczne opcje:
o -n poprzedza każdą linijkę tekstu wynikowego odpowiadającym jej numerem linii w przeszukiwanym pliku
o -h powoduje pominięcie nazw plików w wyniku
o -v wypisuje jedynie linijki tekstu nie zawierające napisu pasującego do wzorca
o -c wypisuje jedynie liczbę linijek zawierających napis pasujący do wzorca w każdym z przeszukiwanych plików, pomijając ich treść
Składnia wyrażeń regularnych (w zarysie):
o zwykły ciąg znaków (np. ,,Jacek") jest wzorcem do którego pasuje napis ,,Jacek". Wyjątkiem są znaki specjalne (metaznaki, p. poniżej); w celu wymuszenia ich interpretacji dosłownej należy poprzedzać je znakiem ,,\"
o lista znaków w nawiasach kwadratowych (np. [012345]) jest wzorcem do którego pasuje dowolny znak z listy (np. cyfra od 0 do 5). Wzorzec postaci zakresu znaków, np. [a-k] odpowiada (małym) literom od ,,a" do ,,k" (dokładniej -- znakom o kodach ASCII zawartych pomiędzy kodami odp. liter).
o Lista poprzedzona znakiem ,,^" pasuje do dowolnego znaku spoza listy.
o Kropka (,,.") oznacza dowolny pojedynczy znak.
o Znaki ,,^" i ,,$" oznaczają odpowiednio napis pusty na początku i na końcu linijki.
o Znak ,,?" oznacza zero lub jeden występień znaku pasującego do poprzedzającego go wzorca; ,,*" oznacza dowolną liczbę powtórzeń (z zerem włącznie); ,,+" oznacza co najmniej jedno wystąpienie poprzedzającego znaku.
Ogólnie, wyrażenie regularne ma postać ciągu wzorców opisujących pojedyncze znaki, z ewentualnymi modyfikatorami (?*+) opisującymi ich powtórzenia. Istnieje też operacja alternatywy, oznaczana znakiem ,,|" pomiędzy dwoma argumentami. Kolejnośc stosowania operacji to powtórzenia, zestawianie i alternatywa; zmianę kolejności można wymusić nawiasami ,,()".
* Powyższy opis składni wyrażeń regularnych jest niepełny, ale uwzględnia on najczęściej stosowane konstrukcje. Pełny opis: p. ,,man grep". sort
* Sortuje plik lub pliki (podane jako argumenty), porządkując linie tekstu (rekordy) według klucza (zawartości zadanych w opcjach pól) posługując się kryteriami zadanymi w opcjach. Dostępne opcje umożliwiają pewne kombinacje sortowania alfabetycznego (wg. wartości kodów ASCII, lub ew. bez rozróżniania małych i wielkich liter) i wg. wartości pól numerycznych. Wynik jest wypisywany na stdout. uniq
* Umożliwia wykrycie lub usunięcie powtórzeń rekordów. cut
* Umożliwia wydobycie zawartości określonych pól z każdego rekordu w pliku, lub stdin (lub napisów z określonych pozycji w każdej linii). paste
Umożliwia utworzenie pliku, którego rekordy składają się z pól o wartościach pobieranych z kolejnych plików podanych jako argumenty.