Database Transaction Processing & Deductive Databases

This assignment solution addresses key concepts in advanced database systems, focusing on transaction processing and deductive databases. The first part analyzes schedules S1 and S2 using the Basic Timestamp Ordering (BTO) algorithm, determining their allowability and discussing cascading rollback. It then explores serializability using serialization graphs and examines recoverability under the Strict Timestamp Ordering (STO) algorithm. The second part delves into deductive databases, constructing model-theoretic and proof-theoretic interpretations of rules like DESCENDANT and SIBLING. It further examines the implementation of rules to find cousins and cousins born before a specific year, demonstrating a comprehensive understanding of database concepts and rule-based systems. The assignment demonstrates the student's ability to apply database concepts to real-world scenarios.

ADVA C D DA A ASN E T B E
Student name
Affiliation
Date

ransaction rocessing3. T P
Consider schedules S and S below1 2 .
S r r r w r r w r r w w w w w1: 2(Y), 2(Z), 3(Y), 2(Z), 3(X), 1(Z), 3(X), 3(Z), 1(X), 3(Y), 2(Y), 1(X), 3(Z), 1(Z)
S r r r w r w r r r r w w w w2: 2(X), 3(Y), 2(Z), 3(Y), 1(X), 2(Z), 1(Y), 3(Z), 1(Z), 2(Y), 2(Y), 3(Z), 1(X), 1(Z)
a Apply the basic ti mestamp ordering algorithm to schedules S and S Determine( ) (BTO) 1 2.
whether or not the algorithm allows the e ecution of the schedules and discuss cascadingx ,
rollback if any ints each operation takes one ti me unit and ti mestamp of each transaction is( ). H : ,
the ti me associated to its fi rst operation or e ample ti mestamps of transactions and in. F x , T1, T2, T3
schedule S are and respectively marks1 6, 1, 3 ( ). [20 ]
ANSWER

T1 T2
T3
S2
b esting the serializability of S and S by serialization graph technique to prove that the( ) T 1 2
successful e ecution of a schedule under will ensure the serializability of the schedulex BTO .
marks[10 ]
ANSWER
S1
c amine the recoverable characteristic of S and S hat schedule S or S can be( ) Ex 1 2. W ( 1 2)
e ecuted under the strict ti mestamp ordering S algorithm and write an equivalent strictx ( TO)
schedule for it e assume that a transaction will be be committed or aborted right after its last? W
operation marks. [20 ]
ANSWER
rom the e amination of the two schedules schedule SF x , 2

Deductive Database4.
Consider a deductive database with the following rules:
D SC DA AR D SC DA D SC DA ARE EN NT(X, Y) :- P ENT(X, Y) E EN NT (X, Y) :- E EN NT (X, Z), P ENT (Z, Y)
otice that AR means that is the biological parent of D SC DAN P ENT (X, Y) X ( ) Y; E EN NT(X, Y)
means that is the descendant ofY X.
Consider the following fact base AR john steve AR john olivia AR olivia: P ENT( , ), P ENT( , ), P ENT( ,
emma AR olivia sophia), P ENT( , ).
a Construct either a model theoretic interpretation of the above rules using the given facts( ) .
mark[10 ]
Consider that a database contains the following relations RS AR and aPE ON(X), P ENT(X, Y),
third relation R where is the birth date of a personBI TH(X, B), B X.
ANSWER
f at all is the parent of then known facts can be constructed for this case as followsI Y X, ;
AR ohn Steve is trueP ENT (J , )
AR ohn livia is trueP ENT (J , O )
AR livia mma is trueP ENT (O , E )
AR livia Sophia is trueP ENT (O , )
arent is false for all possible combinationsP (X,Y) X,Y
he facts which can be derived from the above question is made up of known facts as followsT ;
D SC DA ohn Steve is trueE EN NT (J , )
D SC DA ohn livia is trueE EN NT (J , O )
D SC DA livia mma is trueE EN NT (O , E )
D SC DA livia Sophia is trueE EN NT (O , )
D SC DA is false for all possible combinationsE EN NT (X,Y) X,Y

he following information is used for question b c and d Assume that we have theT ( ), ( ) ( ).
following family tree:
john
steveolivia
michaelisabellaemmasophiadavidanthonysarahchristopher
ith given fact defined predicatesW :
RS john RS steve RS olivia RS michael RS isabellaPE ON( ). PE ON( ). PE ON( ). PE ON( ). PE ON( ).
RS emma RS sohia RS david RS anthony RS sarahPE ON( ). PE ON( ). PE ON( ). PE ON( ). PE ON( ).
RS christopherPE ON( ).
AR john steve AR john olivia AR olivia emma AR olivia sophiaP ENT( , ) P ENT( , ) P ENT( , ) P ENT( , )
AR steve michael AR steve isabella AR michael david AR michaelP ENT( , ) P ENT( , ) P ENT( , ) P ENT( ,
anthony AR emma sarah AR emma christopher) P ENT( , ) P ENT( , )
R john R steve R oliviaBI TH( , 01/01/1930). BI TH( , 01/01/1950). BI TH( , 01/01/1952).
R michael R isabella R emmaBI TH( , 01/01/1974). BI TH( , 01/01/1977). BI TH( , 01/01/1972).
R sohia R david R anthonyBI TH( , 01/01/1975). BI TH( , 01/01/2000). BI TH( , 01/01/2002).
R sarah R christopherBI TH( , 01/01/1995). BI TH( , 01/01/1999).
b( )
Construct a proof theoretic interpretation of D SC DA steve to fi nd all descendants of1. E EN NT( , X)
Steve marks. [10 ]
ANSWER
D SC DA steve michael is trueE EN NT ( , )
D SC DA steve isabella is trueE EN NT ( , )
D SC DA steve david is trueE EN NT ( , )
D SC DA steve anthony is trueE EN NT ( , )
D SC DA steve olivia is trueE EN NT ( , )
D SC DA steve emma is trueE EN NT ( , )

D SC DA Steve is false for all other possible steve combinationsE EN NT ( ,x) , X
State a rule named as S and construct a proof theoretic interpretation of this2. IBLING(X, Y)
rule to fi nd all siblings marks[10 ]
ANSWER
S ohn livia is trueIBLING (J , O )
S livia mma is trueIBLING (O , E )
S mma Christopher is trueIBLING (E , )
S steve Michael is trueIBLING ( , )
S livia Sophia is trueIBLING (O , )
S Steve sabella is trueIBLING ( , I )
S is false for all other possible combinationsIBLING X,Y X,Y
c iven the following rules( ) G :
RS C S A R A R SFI T_ OU IN(X, Y) :- F THE (X, Z), F THE (Y, T), IBLING(Z, T)
C S RS C S S C S A R A R C SOU IN(X, Y) :- FI T_ OU IN (X, Y) OU IN(X, Y) :- F THE (X, Z), F THE (Y, T), OU IN(Z,
T)
ote wo people are fi rst cousins if their parents are siblings Cousins means any kind ofN : T .
cousins Cousins can be second cousins who are the children of the two fi rst cousins or third.
cousins who are the children of two second cousins etc.
1. rove that RS C S isabella emma is true marksP FI T_ OU IN( , ) . [5 ]

ANSWER
he parent to sabella is steve whose parent is ohnT I J
he parent to mma is livia whose parent is ohnT E O J
herefore Steve and livia are siblings to ohnT O J
ence sabella and mma are cousins ence trueH I E . H
2. rove that C S david christopher is true marksP OU IN( , ) . [5 ]
ANSWER
arent of david is Michael whose parent is steveP
arent of Christopher is mma whose parent liviaP E O
herefore C S David Christopher is trueT OU IN( , )
d State a rule named as C S R R that computes a pair of cousins( ) OU IN_BO N_BEFO E_2000
such that both of them were born before the year ou may use less than as a2000. Y “<” ( )
built in predicate marks- . [10 ]
ANSWER
AR livia Sophia is trueP ENT(O , )
AR livia mma is trueP ENT(O , E )
AR mma Sarah is trueP ENT(E , )
C S is false for all possible combinationsOU IN >2000
Sarah is second cousin and Sophia fi rst cousin
enceH ;
C S R R Sarah SophiaOU IN_BO N_BEFO E_2000 ( , )