Temat pracy:

TEMPORALNE MODELE ENCJA -

ZWI

ZEK

– PRZEGL

D Z PRZYKàADAMI

Promotor: dr in

*. Xxxxx Yyyyyy

Xxxxxx Yyyyyyyy
gr. Zzzzzzz

1

ZADANIA DO REALIZACJI

|

Omówienie sposobów klasyfikacji baz danych

uwzgl

dniajcych czas

|

Charakterystyka modeli temporalnych

z przykáadami ich zastosowa



|

Omówienie koncepcyjnego modelu danych jako

podstawy budowy modelu poj

ciowego na etapie analizy

systemu

|

Opracowanie wskazówek uáatwiaj

cych wybór modelu

poj

ciowego

2

WYCI

G Z HARMONOGRAMU

DOTYCZ

CY I ETAPU

|

Maj 2008 r.

- wybór tematu pracy magisterskiej

|

Maj / Pa

(dziernik 2008 r.

- kompletowanie literatury

|

Listopad 2008 r.

- przygotowanie prezentacji opisuj

cej jak b dzie realizowana praca

dyplomowa (ogólna prezentacja)

|

Listopad 2008 r. / Stycze

 2009 r.

-

kompletowanie literatury, opisanie znaczenia temporalnych

danych (problem czasu) , (Rozdziaá I) Koniec etapu 1

|

Luty 2009 r.

- usystematyzowanie temporalnych baz danych wg przyj

tych

parametrów (Rozdziaá II)

- opisanie modeli temporalnych wraz z ich przykáadami zastosowa



(Rozdziaá III) -> Koniec etapu 2

3

WYCI

G Z HARMONOGRAMU

DOTYCZ

CY I ETAPU

|

Marzec 2009 r.

- charakterystyka konceptualnego modelu danych jako bazy do

tworzenia modelu poj

ciowego (Rozdziaá IV) -> Koniec etapu 3

|

Kwiecie

 2009 r.

- wskazówki przy wybieraniu modelu poj

ciowego przy danej

temporalnej bazie (Rozdziaá IV, wnioski)

|

Maj 2009 r.

- estetyka, drobne poprawki, korekty pracy magisterskiej (Zako

czenie

pracy magisterskiej) -> Koniec etapu 4

|

Czerwiec 2009 r.

- obrona pa

stwowa pracy magisterskiej

4

SZCZEGÓàOWA CHARAKTERYSTYKA

DZIEDZINY I SPOTYKANYCH

PROBLEMÓW

|

Temporalne bazy danych s

 nowym kierunkiem rozwoju

dziedziny baz danych.

|

S

 to takie bazy danych, w których uwzgl dniony jest

aspekt czasu tak, aby mo

*liwe byáo przypisanie ka*demu

faktowi czasu, w którym jest on prawdziwy oraz czasu,
w którym informacja o nim jest zapisana w bazie danych

5

ZASTOSOWANIE:

|

Temporalne bazy danych znajduj

 zastosowanie w ka*dej

dziedzinie, w której czynnik czasowy jest niezb

dny dla

odzwierciedlenia rzeczywisto

ci np. :

|

w systemach bibliograficznych

|

w szpitalach

|

w geograficznych systemach informacyjnych

|

w kryminalistyce

|

w przedsi

biorstwach

|

…

6

STRUKTURA CZASU

|

Baza danych, w potocznym rozumieniu, jest przechowalni

 faktów o

wiecie rzeczywistym i powiza pomi dzy nimi. Jest wi c naturalne

wymaganie, aby ka

*demu faktowi towarzyszyá czas, w którym jest on

prawdziwy, oraz czas, w którym istnieje on w bazie danych.

|

Bazy danych, w których uwzgl

dniony jest przynajmniej jeden z tych

dwóch rodzajów czasu, nazywamy temporalnymi bazami danych..

|

Konwencjonalna baza danych zawiera dane o rzeczywisto

ci w

jednym danym momencie czasu. Chocia

* s one caáy czas

aktualizowane, caáy stan bazy odpowiada dokáadnie jednemu

momentowi (lub przedziaáowi) czasu, gdy

* nieaktualne dane (w

danym momencie lub przedziale czasu) s

 usuwane z bazy. W ten

sposób bie

*cy stan bazy danych mo*e byü postrzegany jako

migawka (ang. snapshot) rzeczywisto

ci.

7

REPREZENTACJE CZASU

|

Temporalna logika zajmuje si

dwiema strukturami

czasu: liniow

 (ang. linear) i rozgaá zion (ang.

branching)

|

W strukturze liniowej czas jest reprezentowany za
pomoc

 zbioru punktów, które s w liniowym porzdku.

|

W strukturze rozgaá

zionej czas jest liniowy od

przeszáo

ci do chwili obecnej, nast pnie rozgaá zia si na

kilka

cie*ek, z których ka*da reprezentuje inn

potencjaln

 wersj zdarze

8

REPREZENTACJE CZASU

|

Czas mo

*e byü dyskretny, tzn. reprezentowany za pomoc

niepodzielnych jednostek (ang. chronons), na przykáad
dzie

, sekunda etc. Jest to najcz ciej stosowany model

czasu.

|

Czas mo

*e byü równie* cigáy, tzn. reprezentowany za

pomoc

 przedziaáów czasu, np. „od godz. 10 do godz.

11.45”

|

Uwzgl

dniono równie* czas wzgl dny, np. „9 godzin”, i

czas bezwzgl

dny, np. „godzina 10 dnia 28.05.1996”.

9

OBRAZ ZDARZE

 - SCENARIUSZ

|

Z jednych temporalnych informacji mo

*na wywnioskowaü nast pne,

poprzez analiz

czasów, w których fakty miaáy miejsce i relacje jakie

zachodz

 pomi dzy tymi czasami.

|

Przy du

*ej liczbie faktów i ich niekompletnoci pojawia si problem,

jak uzyskaü na ich postawie obraz zdarze

 (tzw. scenariusz).

|

Post

puje si w nast pujcy sposób:

1) Najpierw dla ka

*dych dwóch okresów czasu zapisuje si wszystko, co

tylko si

da powiedzieü o ich wzajemnym poáo*eniu.

Definiuje si

w ten sposób pewien graf skierowany, którego

wierzchoákami s

 zdarzenia, a kraw dziami s relacje pomi dzy czasami

tych zdarze

.

2) Nast

pnie za pomoc pewnego algorytmu przeksztaáca si go tak, *eby

wyáoniü taki graf zdarze

, którego ka*da kraw d( reprezentuje

dokáadnie jedn

 relacj .

Ju

* samo tworzenie wejciowego grafu nie jest proste,

10

PRZYKàAD SCENARIUSZA

Zdanie: „Zenon czytaá gazet

przy niadaniu.”

Ze zdania wynika,

*e czynnoci czytania gazety oraz jedzenia

niadania byáy przez jaki czas równoczesne.

A taka sytuacja mo

*e mieü miejsce na dziewi ü ró*nych

sposobów!

S

 to: {o,oi,s,si,d,di,f,fi,eq}

Je

*eli pozycja dwóch przedziaáów wzgl dem siebie jest

dokáadnie znana, to mo

*e byü ona opisana dokáadnie jedn z

13 relacji: before, after, meets, met-by, overlaps,

overlappedby, during, includes, starts, started-by, finishes,

finished-by, equals:

11

RELACJE

12

RELACJE

|

Ka

*d informacj na temat wzajemnego poáo*enia dwóch

przedziaáów, mo

*na zapisaü jako alternatyw dowolnego

podzbioru wymienionych 13 relacji.

|

Zaliczamy tu równie

* zbiór pusty oraz zbiór wszystkich 13

relacji.

|

Jest wi

c 2

13

= 8192 mo

*liwych relacji pomi dzy dwoma

przedziaáami.

13

WNIOSKOWANIE

14

„Zenon czytaá gazet

przy niadaniu. Skoczyá czytaü i dopiá reszt kawy. Po

niadaniu poszedá na spacer.”

WNIOSKOWANIE

|

)eby uzyskaü dokáadniejsz informacj o relacjach pomi dzy

czasami poszczególnych czynno

ci, stosujemy wnioskowanie:

1)Skoro Zenon sko

czyá czytaü gazet zanim skoczyá piü kaw ,

a kawa stanowi cz

ü niadania, to std wniosek, *e czytanie

gazety zostaáo zako

czone przed zakoczeniem niadania.

2)Skoro picie kawy nale

*y do niadania, a spacer byá po

niadaniu, to spacer byá równie* po piciu kawy.

3) Wreszcie, skoro Zenon sko

czyá czytaü gazet zanim

sko

czyá niadanie, a poszedá na spacer po niadaniu, to

poszedá na spacer po tym, jak sko

czyá czytaü gazet .

Wnioskowanie takie pozwala wygenerowaü prostszy (tzn.

podaj

cy dokáadniejsze informacje) graf:

15

GRAF PO ZASTOSOWANIU
WNIOSKOWANIA

16

Do wyznaczania tego grafu (scenariusza) sáu

* opracowane algorytmy.

Powa

*nym mankamentem tych algorytmów jest du*a záo*onoü obliczeniowa.

CZAS W TEMPORALNYCH BAZACH

DANYCH

|

W temporalnych bazach danych rozró

*nia si 2 gáówne rodzaje czasu:

czas wáa

ciwy (ang. valid time) i czas transakcji (ang. transaction time).

|

Czas wáa

ciwy przypisany faktowi, jest to czas, kiedy fakt ten ma

miejsce. Czas ten mo

*e byü zarówno przeszáy, tzn. wydarzenie

naprawd

zdarzyáo, jak i przyszáy, tzn. ma si dopiero zdarzyü.

|

Czas transakcji jest to czas, kiedy fakt jest przechowany w bazie

danych, najcz

ciej jest on przedziaáem, który zaczyna si w momencie,

kiedy dany fakt zostaá wprowadzony do bazy, a ko

czy w momencie

kiedy fakt przestaá byü aktualny.

|

Baza danych jest temporalna je

li zawiera co najmniej jeden z tych

dwóch rodzajów czasu, a je

li zawiera obydwa, to nazywamy j

bitemporaln

.

17

TEMPORALNO-RELACYJNE BAZY
DANYCH

Do reprezentacji czasu w temporalno-relacynej bazie

danych wystarcz

 atrybuty, w których przechowywany

jest czas pocz

tkowy oraz czas kocowy wydarzenia lub

faktu.

18

TEMPORALNO-OBIEKTOWE BAZY
DANYCH

Czas wáaciwy

w obiektowych bazach danych najcz

ciej jest

reprezentowany jako punkty (np. 1945), przedziaáy (np. [1945,1975])

lub zbiory punktów

lub przedziaáów.

Czas transakcji

jest to czas, kiedy fakt jest przechowany w bazie

danych.

Je

li chodzi o reprezentowanie czasu transakcji w tego rodzaju bazie

danych istnieje kilka sposobów:

a)

wprowadzenie czasu bezpo

rednio do obiektowego modelu danych,

np. je

li pracownik zmienia zakáad to zostanie wprowadzona nowa

warto

ü funkcji f, nie ma potrzeby zmiany modelu danych ani j zyka

zapyta

.

To podej

cie zostaáo zastosowane w modelu OODAPLEX.

b) modyfikowanie zarówno modelu danych jak i j

zyka zapyta tak,

aby uwzgl

dniü rozgaá ziony czas transakcji, przykáadem jest model

VISION

.

19

TEMPORALNO-DEDUKCYJNE BAZY
DANYCH

Dedukcyjno-temporalna baza danych

jest definiowana jako sko

czony

zbiór predykatów.

Predykaty zawieraj

 pewn liczb nietemporalnych atrybutów oraz

jeden lub wi

cej atrybutów temporalnych.

Np. rozkáad jazdy poci

gów mo*emy przedstawiü za pomoc

predykatu:

Rozkáad_jazdy(Godz._przyjazdu, Godz._odjazdu)

Wyst

pieniem predykatu nazywamy dowolny zbiór predykatów

podstawowych, w których zmienne przyjmuj

 konkretne wartoci.

Opracowano 2 temporalno-dedukcyjne modele danych, DETALOG i

TEMPLOG

, w których mo

*liwe jest reprezentowanie nieskoczonych

wyst

pie predykatów.

J

zyki te, choü s dobrze formalnie opracowane, s trudne do

implementacji.

20

WNIOSKI Z ANALIZY MAJ

CE WPàYW

NA DALSZ

 REALIZACJ PRACY

|

Przedstawienie bardziej szczegóáowo metod reprezentacji
czasu

zarówno czasu wáa

ciwego jak i czasu transakcji w

najpopularniejszych modelach baz:

Temporalno-relacyjne bazy danych
Temporalno-obiektowe bazy danych
Temporalno-dedukcyjne bazy danych

Dzi

ki temu b dzie mo*na usystematyzowaü,

sklasyfikowaü takie bazy danych

21

SZCZEGÓàOWY PRZEGL

D

LITERATURY

|

Date C. J. , Darwen H. and Lorentzos N.A. - TemporalDataand the Relational Model , Morgan

Kaufmann, 2003

|

Jensen C. S. , Clifford J. , Elmasri R. , Gadia S. K. , P. Hayes and S. Ja-jodia (eds.) - “A Glossary of
Temporal Database Concepts”

ACM SIGMODRecord, March, 1994.

|

Jensen Christian S. - Temporal Database Management, praca doktorska 2000

http://www.cs.aau.dk/~csj/Thesis/

|

Kania K.

„Temporalne bazy danych w systemach informatycznych”

|

Knight B., Ma J.- Temporal Database Model Supporting Relative and Absolute Time, TheComputer

Journal 1994, Vol. 37, nr 7,

|

Nguyen N. T. , Sekuradzki W. - Temporalne bazy danych

, Politechnika Wrocáawska, WROCàAW

|

Snodgrass, R. - Temporal Object-Oriented Databases: A Critical Comparison, W:ModernDatabase
Systems, The Object Model, Interoperability, and BeyondKim W. (ed.),

Addison Wesley Pub. Comp.

1995,

|

Snodgrass R. T. (ed), The TSQL2 Temporal Query Language, KluwerAcademic Publishers, 1995.

|

Tansel A. , Clifford J. , Gadia S. K. , S. Jajodia, A. Segev, and R. T. Snodgrass, editors, Temporal

Databases: Theory, Design, and Implementation, Database Systems and Applications Series

.

Benjamin/Cummings, RedwoodCity, CA, 1994

|

Wódz D. - Zastosowanie modeli danych odwzorowuj

cych zmienn w czasie rzeczywistoü. Modele

temporalne - teoria i realizacja – praca doktorska SGH , 1998

22

OMÓWIENIE ZADA

 DO REALIZACJI

W NAST

PNYM ETAPIE

|

Charakterystyka modeli temporalnych :

-

Analiza i porównanie

-

Zastosowania i przykáady modeli

23

24