Scribd
Upload
9 views

Deductive Database

Uploaded by

deepak52764
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views

Deductive Database

Uploaded by

deepak52764
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Deductive Databases

Recursive Queries
Assembly(part,subpart, qty)

“what are components of trike?” – cant be expressed in simple SQL


To solve this let’s define
Datalog – a query langugage inspired by prolog
Let components(part,subpart) :- Assembly(part,subpart,qty)
Datalog rules can be –
1. For all part,subpart if it exists in assembly it should also exist in components
2. If Assembly(parta,partb,qty) exist, components(partb,partc) exist then there must
also be component(parta,partc) -> Transitivity
If _headOfRule_ then _bodyOfRule_
If there are some set of Components, we can use these rules to deduce some new tuples
until no further deduction is possible
That is why this is called as deductive database system
First rule helps us make projection of assembly in components, second helps us to
deduce new tuples
FixPoint Operation – Recursively generating new tuples based on fixed rules until no new
tuples are possible.
Two Stratagies
1. Least Model Symantics –
Terms -
Model – under which a set of statements are true
Facts – Statemenets unconditionally true -> Parent(A,B) A is parent of B
Rule – Conditions that describe how new facts can be inferred
Grandparent(A,B): - Parent(A,C) and Parent(C,B)
Least Model – Among all possible models, least model is model with least possible facts.
Least Model Symantics help us derive new facts based on known facts and rules
Processs –
Start from basic facts, apply the rule, add inferred facts to known facts and repeat until no
new operation is possible
Importance of this model –
1. Uniqueness – The least model is unique for given set of facts
2. Query Evaluation – When a query is posted, the system checks if the queried fact is
present n least model to determine wheather it is true

Remember fixed point == stable state == no further deduction possible == f(v) -> v
Least fixed point - is fixed point smaller than any other fixed point

Safe Datalog Programs


Complex(parts):- assembly(part,subpart,qty), qty > 2
Unsafe program – infinite recursions
Eg -parts(x,y) :- assembly(x,z,q)
Since Y is present in head but not in body, any value for Y is a valid value, thus leading to
unsafe condition
To disallow this,
“every variable in head must also be present in body” – range-restricted programs
Use of Negation in Datalogs
This may cause problem
Big(x) :- asembly(x,y,q) , q > 2, NOT Small(x)
Small(x):- asembly(x,y,q), NOT Big(x)
If we apply rule 1 first something may become Big, and same thing will become small if we
apply rule 2 first,
This is the problem of “NOT” (Negation), creating 2 fix points neither smaller than other
Solution – Stratisfaction
STRATISFACTION
Terms –
1. Strata – A layer in which rules are evaluated,Rules in higher stratum will depend on
lower stratum but not vice versa
2. Negative Dependencies – let table T contain NOT S, then Table T and Table S are
negatively dependent
Stratisfied Program (remember to show big-small problem solved using strata)
1. Each rule is assied to stratum
2. Let a rule belong to stratum i then, that rule can only belong to rules in same stratum
or lower stratum
3. If a rule “a” is negatively dependent on some other rule, lets say “b”, then b must be
in lower stratm than a

Relational Algebra and Stratification


Selection: Result(Y):- R(X,Y), X=c
Projection: Result(Y):- R(X,Y)
Cross-Product: Result(X,Y,U,V):- R(X,Y),S(U,V)
Set-Difference: Result(X,Y) :- R(X,Y) NOT S(U,V)
Union: Result(X,Y) :- R(X,Y) Result(X,Y) :- S(U,V)

Big Small Problem using Stratiftication


DATALOG AND SQL
Two main SQL Features missing in Datalog:
1. SQL Treats data in multiset and not in set
2. SQL Permits grouping and agregation
Point 1 can be preserved by not checking duplicacy through rules
For Point 2 something like below can be done:
NumParts(Part,Sum(QTY)) :- Assembly(Part,subpart,qty)

Evaluating Recursive Queries

As of now we evaluate recursive queries using least model /fixedpoint method, by


repeatedly calculating least possible fixedpoint, until no further calculation is possible
But this method has 2 disadvantages
1. Repeated Interference: Repeatations of same tuples across multiple iterations
2. Unnecessary Interferance: Suppose we want to calculate components of only
“wheel”, but for that we need need to perform our operation across all tuples, also
verifying unnecessary tuples in the process
Solving these Problems –>
a. Solving Problem 1 -
Firstly while evaluating fixed points, by naieve recursive calls is called as naïve Fixpoint
evaluation
Now by “remembering” which tuples were calculated before, we may improve this.
Remembering can be done by carrying a new relation called as delta_components, thus
halting repeated calculations same tuples.
This is called as Semi Naïve Fixpoint Evaluation

b. Solving Problem 2 –
SameLevel(subpart1,subpart2) :- assembly(part1,subpart1,q1), assembly(part1,subpart2,q2)
SameLevel(subpart1,subpart2) :- assembly(part1,subpart1,q1),
assembly(part2,subpart2,q2), samelevel(part1,part2)
But calculating same level for all part is wastefull, so instead we will use Magic Set
Transformation
We will create MagicSameLevel, where we will calulcate samelevel where argument in query
is given part
MagicSameLevel(part):- MagicSameLevel(subpart), assembly(part,subpart,q)
It restricts the query search space to relevent fields thereby improving its time complexity

Algorithm
1. Generate Adorned Program – program is rewritten for clarification ofqueries and
subqueries
2. Add Magic Filters – Modify rules in Adorned program, by adding magic condition to
the body that acts as a filter to tuples generated by the rules
3. Define Magic Table

Understanding Adorned Program


It is modifciation of datalog program
Here every argument is either bounded (b), or free(f), bounded if it is known, else free.
Lets say we have a predicate P(x,y)
P_bb – both bounded, p_bf, p_fb, p_ff, simmilar

You might also like