DATALOG
RECURSIVE QUERIES AND
DEDUCTIVE DATABASE
MEENA POORANI K.N
(2018202029)
SARUMATHI R.S
(2018202050)
What is Datalog ?
Datalog is a programming language used in deductive database
work. It is part of another language called Prolog and incorporates
basic logic principles for data integration, database queries, etc.
Datalog is used by many open-source systems and other database
systems.
Deductive Database:
A deductive database is a database system that can make
conclusions about its data based on a set of well-defined rules and
facts. This type of database was developed to combine logic
programming with relational database management systems. Usually,
the language used to define the rules and facts is the
logical programming language Datalog.
Recursive Queries:
Recursive queries are used to query hierarchical data.
A recursive CTE has three elements:
Non-recursive term: the non-recursive term is a CTE query
definition that forms the base result set of the CTE structure.
Recursive term: the recursive term is one or more CTE query
definitions joined with the non-recursive term using
the UNION or UNION ALL operator. The recursive term
references to the CTE name itself.
Termination check: the recursion stops when no rows are
returned from the previous iteration.
PostgreSQL executes a recursive CTE in the following sequence:
1. Execute the non-recursive term to create the base result set (R0).
2. Execute recursive term with Ri as an input to return the result
set Ri+1 as the output.
3. Repeat step 2 until an empty set is returned. (termination check)
4. Return the final result set that is a UNION or UNION ALL of the
result set R0, R1, … Rn
Example:
Office.sql
create table position(pos string primary key);
create table dependency(boss string,sub string, foreign key(boss)
references position(pos),foreign key(sub) references position(pos));
create table emp(ename string,pos string,foreign key(pos) references
position(pos));
insert into position values('ceo'),('manager'),('supervisor'),('trainee'),
('clerk');
insert into dependency values('ceo','manager'),('manager','supervisor'),
('manager','trainee'),('supervisor','clerk');
insert into emp values('hamen','ceo'),('john','manager'),
('paulin','supervisor'),('devi','trainee'),('ram','clerk');
% To find direct boss
WITH RECURSIVE fb(boss,sub) AS (SELECT ep1.ename,
ep2.ename FROM dependency, emp AS ep1, emp AS ep2 WHERE
dependency.boss=ep1.pos AND dependency.sub=ep2.pos) SELECT *
FROM fb;
% To find boss
WITH RECURSIVE find(boss,sub) AS (SELECT * FROM dboss)
UNION (SELECT b1.boss,b2.sub FROM find AS b1, find AS b2
WHERE b1.sub=b2.boss) SELECT * FROM find;
Office.dl
dependency(ceo,manager).
dependency(manager,supervisor).
dependency(manager,trainee).
dependency(supervisor,clerk).
emp(devi,trainee).
emp(hamen,ceo).
emp(john,manager).
emp(paulin,supervisor).
emp(ram,clerk).
position(ceo).
position(clerk).
position(manager).
position(supervisor).
position(trainee).
:-type(position(pos:string)).
:-type(dependency(boss:string,sub:string)).
:-type(emp(ename:string,pos:string)).
:-pk(position,[pos]).
:-fk(dependency,[boss],position,[pos]).
:-fk(dependency,[sub],position,[pos]).
:-fk(emp,[pos],position,[pos]).
% direct boss
dboss(B,S) :-
emp(B,BP),
emp(S,SP),
dependency(BP,SP).
% boss
findboss(B,S) :-
dboss(B,S).
findboss(B,S) :-
findboss(B,I),
findboss(I,S).
Result:
Graph:
