% Logik og sprog, Modul 2, datalogi RUC      Henning Christiansen
%
% 
% En fortolker for Relationel Algebra
% 
%
% Kapitel 9 i "Sprog og abstrakte maskiner"
%
% (c) 2000, Henning Christiansen
%

:- use_module(library(lists)).



% RELATIONEL DATABASE I PROLOG
%
% Databasen er repraesenteret ved foelgende praedikater
%
% skema( <relationelt udtryk>, <att.navneliste> )
%
% tupel( <relationelt udtryk>, <tupel som liste> )
%

% Et <relationelt udtryk> er defineret ved foelgende
% operatorer samt konstanter, som gennem fakta om
% skema(-,-) og tupel(-,-), er givet fra starten
% (se eksempel nedenfor)

:- op(500,yfx,union).
:- op(500,yfx,intersect).
:- op(500,yfx,minus).
:- op(500,yfx,project).
:- op(500,yfx,where).
:- op(500,yfx,join).

% Praedefinerede/tabulerede relationer

skema( kunde, [knr,knavn,kby]).
skema( ordre, [knr,vnr,antal]).
skema( vare, [vnr,vnavn,farve,vby]).

tupel( kunde, [k1,soeren,lilleby]).
tupel( kunde, [k2,janne,paars]).
tupel( kunde, [k3,benny,paars]).
tupel( kunde, [k4,conny,lilleby]).
tupel( kunde, [k5,adam,arrested]).
tupel( vare, [v1,noed,roed,lilleby]).
tupel( vare, [v2,banan,groen,paars]).
tupel( vare, [v3,skrue,blaa,rungsted]).
tupel( vare, [v4,skrue,roed,lilleby]).
tupel( vare, [v5,kam,blaa,paars]).
tupel( vare, [v6,kniv,roed,lilleby]).
tupel( vare, [v7,kost,gul,rungsted]).
tupel( ordre, [k1,v1,300]).
tupel( ordre, [k1,v2,200]).
tupel( ordre, [k1,v3,400]).
tupel( ordre, [k1,v4,200]).
tupel( ordre, [k1,v5,100]).
tupel( ordre, [k1,v6,100]).
tupel( ordre, [k2,v1,300]).
tupel( ordre, [k2,v2,400]).
tupel( ordre, [k3,v2,200]).
tupel( ordre, [k4,v2,200]).
tupel( ordre, [k4,v4,300]).
tupel( ordre, [k4,v5,400]).


skema( R1 union R2, Skema):-
    skema( R1, Skema),
    skema( R2, Skema).

skema( R1 intersect R2, Skema):-
    skema( R1, Skema),
    skema( R2, Skema).

skema( R1 minus R2, Skema):-
    skema( R1, Skema),
    skema( R2, Skema).

skema( R project AttList, AttList):-
    skema(R, R_AttList),
    liste_indeholdt(AttList, R_AttList).

skema( R where Betingelse, Skema):-
    skema(R, Skema).
    % Burde indeholde et check for, at attributter naevnt i
    % Betingelse faktisk optraeder i Skema.

skema( R1 join R2, SkemaJoin):-
    skema(R1, Skema1),
    skema(R2, Skema2),
    flet_skema(Skema1, Skema2, SkemaJoin).


%%% AFLEDTE TUPLER
% --- kaldene af 'skema(..' er i de fleste tilfaelde en
%     slags overfloedigt "typecheck"

tupel( R1 union R2, Tup):-
    skema( R1 union R2, _), % at det er veldefineret
    (tupel(R1, Tup) ; tupel(R2, Tup) ).

tupel( R1 intersect R2, Tup):-
    skema( R1 intersect R2, _), % at det er veldefineret
    tupel(R1, Tup),
    tupel(R2, Tup).

tupel( R1 minus R2, Tup):-
    skema( R1 minus R2, _), % at det er veldefineret
    tupel(R1, Tup),
    \+ tupel(R2, Tup).

tupel( R project AttList, Tup):-
   skema(R, Rskema),
   tupel(R, RTup),
   projicer_tupel(Rskema, AttList, RTup, Tup).

tupel( R where Betingelse, RTup):-
   skema(R, Rskema),
   tupel(R, RTup),
   check_betingelse(Rskema, Betingelse, RTup).

tupel( R1 join R2, Tup):-
    skema( R1 join R2, _),
    tupel( R1, Tup1), tupel( R2, Tup2),
    skema(R1, Skema1),
    skema(R2, Skema2),
    flet_tupler(Skema1, Skema2, Tup1, Tup2, Tup).

/*********************************
Eksempler paa forespoergsler.

?-tupel(vare,T).

?-tupel(kunde join ordre,T).

?-tupel(kunde join ordre join vare,T).

% Hvem faar har en vare i ordre i et antal 100?
?-tupel(kunde join ordre where (antal=100) project [knavn],T).


% Hvem har en roed vare i ordre
?-tupel(kunde join ordre join vare where (farve=roed) project [knavn],T).

% Hvilke varer er i ordre i et antal paa 200 eller 400?
?-tupel((ordre where (antal=200) project [vnr]) union (ordre where (antal=400) project [vnr]), T).

% ELLER bedre
?-tupel(((ordre where (antal=200) project [vnr]) union (ordre where (antal=400) project [vnr])) join vare project [vnavn], T).
No more solutions

******************/

%%%%%%%%%%%%%%%%%%%%%%%%
% HJŪLPE-PRŪDIKATER

liste_indeholdt([],_).

liste_indeholdt([E|EE],L):-
   member(E,L),
   liste_indeholdt(EE,L).

%%%%%

% vaelg_komponent( Skema, Att, Forekomst, Komponent)

vaelg_komponent([Att|_], Att, [K|_], K):- !.

vaelg_komponent([_|Atts], Att, [_|F], K):-
    vaelg_komponent(Atts, Att, F, K).


%%%%

% projicer_tupel(Skema, DelSkema, Forekomst, DelForekomst)

projicer_tupel(_, [],_,[]).

projicer_tupel(Skema, [Att|Atts], Forekomst, [E|EE]):-
    vaelg_komponent(Skema, Att, Forekomst, E),
    projicer_tupel(Skema, Atts, Forekomst, EE).

%%%%
% check_betingelse(Skema, (Att <op> Vaerdi), Tupel).


check_betingelse(Skema, OP_Att_Vaerdi, Tupel):-
    OP_Att_Vaerdi =.. [OP,Att,Vaerdi],
    vaelg_komponent(Skema, Att,Tupel, ObsVaerdi),
    Kald =.. [OP,ObsVaerdi,Vaerdi],
    Kald.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% flet_skema(Skema1  , Skema2, SkemaJoin)
% en append, som fjerner dubletter fra den sidste
% -- beregnet til join

flet_skema(Skema1, Skema2, SkemaJoin):-
    flet_skema(Skema1, Skema1, Skema2, SkemaJoin).

% flet_skema(Skema, Skema1, Skema2, SkemaJoin)
% Foerste argument slaebes uaendret med, bruges til at frasortere
% i Skema2...

% foerste delliste kopieres over
flet_skema(Skema1, [Att|Atts], Skema2, [Att|MoreJoinAtts]):-
    !, flet_skema(Skema1, Atts, Skema2, MoreJoinAtts).

% Anden delliste, ligesaa men uden dubletter:

flet_skema(Skema1, [], [Att|Atts], MoreJoinAtts):-
    member(Att, Skema1),
    !, flet_skema(Skema1, [], Atts, MoreJoinAtts).

flet_skema(Skema1, [], [Att|Atts], [Att|MoreJoinAtts]):-
    !, flet_skema(Skema1, [], Atts, MoreJoinAtts).

flet_skema(_,[], [], []).

%%%%
% flet_tupler(Skema1, Skema2, Tup1, Tup2, Tup)
% -- beregnet til join
% samme princip som flet_tupler
% dog er kontrollen for sammenfald paa attributnavn flyttet
% frem, idet den er kombineret med kontrol for sammenfald paa
% vaerdi


flet_tupler(Skema1, Skema2, Tup1, Tup2, Tup):-
    flet_tupler(Skema1, Skema1, Skema2, Tup1, Tup2, Tup).

flet_tupler(Skema1, [Att|Atts], Skema2,
    [E|Es], Tup2, [E|MoreJoinTup]):-
    ((member(Att, Skema2), !,
    vaelg_komponent( Skema2, Att, Tup2, E));true), % samme vaerdi!
    flet_tupler(Skema1, Atts, Skema2, Es, Tup2, MoreJoinTup).

% Anden delliste, ligesaa men uden dubletter:

flet_tupler(Skema1, [], [Att|Atts],
    [], [E|Es], MoreJoinTup):-
    member(Att, Skema1),
    !, flet_tupler(Skema1, [], Atts, [], Es, MoreJoinTup).

flet_tupler(Skema1, [], [Att|Atts],
    [], [E|Es], [E|MoreJoinTup]):-
    flet_tupler(Skema1, [], Atts, [], Es, MoreJoinTup).

% Slut

flet_tupler(_,[], [], [],[],[]).