home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / 1990 / 01 / algorith / sql.pro < prev    next >
Encoding:
Text File  |  1989-11-01  |  14.9 KB  |  412 lines
  1. /********************************************************/
  2. /*                     SQL.PRO                          */
  3. /*      Selektieren und Sortieren von Datensätzen       */
  4. /*         Mit einer SQL-ähnlichen Abfrage-Sprache      */
  5. /*           (C) 1989,1990 O.P.Prem & TOOLBOX           */
  6.  
  7. code=3500 
  8. trail=100
  9.  
  10. DOMAINS
  11.   file = f
  12.   t = t(string,string)
  13.   infolist = reference sortinfo*
  14.   /* z.B. [h("+",1),h("-",2)] 
  15.      = es wird nach dem ersten Feld aufsteigend
  16.        und nach dem zweiten Feld absteigend sortiert */
  17.   sortinfo = reference h(string,integer) 
  18.   strulist = t*
  19.   /* z.B. [t("ZUNAME","s"),t("VORNAME","s"),t("ALTER","i")] 
  20.      = die Datei besteht aus zwei Datenfeldern vom 
  21.        Typ 'string' und einem vom Typ 'integer'         */ 
  22.   element = i(integer); s(string); r(real)
  23.   list = string*
  24.   slist = element* 
  25.   exp = reference g(integer,slist); 
  26.         und(exp,exp); oder(exp,exp); nicht(exp) 
  27.   /* z.B. oder(g(1,[s("IN"),s("A"),s("H")]),g(2,
  28.                [s("="),s("Thomas")])) 
  29.      = Zuname in A..H oder Vorname=Thomas (Zuname ist 
  30.        das erste Datenfeld und Vorname das zweite)      */
  31.   gew = reference daten(slist); selektiert(slist)
  32.   gewlist = reference gew*
  33.   /* notwendig, um das vordefinierte Prädikat 
  34.      findall für die Datenbasis verwenden zu können */
  35.  
  36. DATABASE
  37.   eingabe(list)  
  38.   /* enthält die abgearbeitete Liste der eingegebenen 
  39.      Selektierkriterien; wenn ein sinnvoller Ausdruck 
  40.      eingegeben wurde, ist diese Liste leer.            */
  41.   daten(slist)           /* Die eingelesenen Datensätze */
  42.   feldnamen(strulist)    /* enthält die Dateistruktur */ 
  43.   name_der_Datei(string) /* enthält den Dateinamen */
  44.   selektiert(slist)      /* Die selektierten Datensätze */
  45.   ende(string)           /* Bedingung für das Programmende */
  46.   n(integer)             /* Zähler für die Ausgabe von Datensätzen
  47.                             durch das Prädikat 'out1' */
  48.  
  49. PREDICATES
  50.   readexp(exp,list). 
  51.   member(string,string,integer,integer,strulist).
  52.   tokl(string,list). 
  53.   ausgabe_struktur(string).
  54.   ausgabe(strulist,integer)
  55.   umwandeln(list,list,exp). 
  56.   konversion(string,string,element).
  57.   ch_exp(list,list,exp). ch_term(list,list,exp)
  58.   ch_term1(list,list,exp,exp). 
  59.   art_der_auswahl(infolist,exp).
  60.   vorn(string,list,list)
  61.   erzeugen(list,list,string,slist). run. 
  62.   loeschen(dbasedom).
  63.   felder(strulist,integer,integer). 
  64.   read_Data(string,integer).
  65.   read_Records(strulist,integer) 
  66.   read_One_Record(strulist,integer,integer,slist)
  67.   lesen. suchen(exp). verarbeite(integer). menu
  68.   pruefe_satz(slist,exp). pruefe_relation(element,slist). 
  69.   comp_string(element,slist). comp_int(element,slist). 
  70.   comp_real(element,slist). 
  71.   out1. out(gewlist,integer)   
  72.   n_tes(slist,integer,element). zerlegen(list,list,list). 
  73.   check(list,infolist). 
  74.   qsort(gewlist,gewlist,gewlist,infolist).
  75.   split(slist,gewlist,gewlist,gewlist,infolist)
  76.   dem(infolist,gew,slist). choose(gew,slist)
  77.   ab(gew,slist,element,element,infolist)
  78.   auf(gew,slist,element,element,infolist)
  79.   wahl1(gew). wahl2(gew). mode1(exp). mode2(infolist).
  80.   schreibe(slist,integer). warte(integer)
  81.   sammle(gew,slist,infolist)
  82.  
  83. CLAUSES
  84.   /* MENÜAUFBAU */
  85.   run:- 
  86.     makewindow(1,7,7,
  87.     "Selektieren und Sortieren von Datensätzen",0,0,25,80),
  88.     menu.
  89.   run:- not(ende("ENDE")),run.  
  90.   menu:- clearwindow,
  91.          cursor(6,15),write("(1)  neue Datei"),
  92.          cursor(8,15),
  93.          write("(2)  Auswahl von Datensätzen"),
  94.          cursor(10,15),write("(3)  Ende"),
  95.          cursor(13,15),write("Wählen Sie: "),
  96.          readint(Wahl),nl,
  97.          verarbeite(Wahl),!,menu.
  98.  
  99.   /* AUSFÜHRUNG DER MENÜWAHL */
  100.   verarbeite(1):- lesen,!,readexp(Exp,Sort),
  101.                   check(Sort,Sort1),
  102.                   eingabe([]),art_der_auswahl(Sort1,Exp).
  103.   verarbeite(1):- removewindow,closefile(f),
  104.                   readdevice(keyboard),fail.
  105.   verarbeite(2):- name_der_Datei(_),!,
  106.                   loeschen(selektiert(_)),
  107.                   loeschen(n(_)),
  108.                   readexp(Exp,Sort),check(Sort,Sort1),
  109.                   eingabe([]),art_der_auswahl(Sort1,Exp).
  110.   verarbeite(2):- verarbeite(1).
  111.   verarbeite(3):- !,asserta(ende("ENDE")),fail.
  112.   verarbeite(_).                                
  113.  
  114.   /* ART DER SELEKTION UND SORTIERUNG */
  115.   art_der_auswahl(S,E):- not(mode1(E)),not(mode2(S)),
  116.       suchen(E), findall(X,wahl1(X),Ungeordnet),
  117.       qsort(Ungeordnet,Geordnet,_,S),
  118.       clearwindow,out(Geordnet,1),readchar(_).  
  119.       /* Selektieren und Sortieren */
  120.   art_der_auswahl(S,E):- not(mode1(E)),mode2(S),suchen(E),
  121.       findall(X,wahl1(X),L),clearwindow,
  122.       out(L,1),readchar(_). 
  123.       /* Selektieren, kein Sortieren */ 
  124.   art_der_auswahl(S,E):- mode1(E),not(mode2(S)),
  125.       findall(X,wahl2(X),Ungeordnet),
  126.       qsort(Ungeordnet,Geordnet,_,S),
  127.       clearwindow,out(Geordnet,1),readchar(_).
  128.       /* alle Datensätze sortiert */
  129.   art_der_auswahl(S,E):- mode1(E),mode2(S),asserta(n(1)),
  130.       clearwindow,out1,readchar(_).
  131.       /* alle Datensätze unsortiert */
  132.  
  133.   /* EINGABE DER SELEKTIER- UND SORTIERKRITERIEN */
  134.   readexp(Exp,Sort):- clearwindow,name_der_Datei(S),
  135.       ausgabe_struktur(S),nl,nl,
  136.       write(" Selektier- und Sortierkriterien:"),nl,
  137.       write(" "),readln(Str),tokl(Str,Tok),
  138.       zerlegen(Tok,Selekt,Sort),umwandeln(Selekt,L,Exp),
  139.       asserta(eingabe(L)),!.
  140.   readexp(_,_):- nl,nl,write("falscher Ausdruck"),
  141.                  readchar(_),fail.               
  142.  
  143.   /* Umwandeln einer Zeichenkette in eine Tokenliste */
  144.   tokl(STR,[H|T]):- fronttoken(Str,H,Str1),!,tokl(Str1,T).
  145.   tokl(_,[]).
  146.  
  147.   /* UMWANDELN DER EINGEGEBENEN SELEKTIERKRITERIEN 
  148.      IN EINEN AUSDRUCK IN PRÄFIXNOTATION 
  149.      (siehe das Beispiel zum domain 'exp')          */
  150.  
  151.   umwandeln([],[],g(0,[])):- !. 
  152.   /* Ausgabe aller Datensätze */
  153.   umwandeln(S,L,Exp):- ch_exp(S,L,Exp).
  154.  
  155.   ch_exp(In,Out,Exp):- ch_term(In,Out1,Exp1),
  156.                        ch_term1(Out1,Out,Exp1,Exp).
  157.  
  158.   ch_term([X|IL],Ol,nicht(Exp)):- 
  159.     upper_lower("NICHT",X),!,ch_exp(IL,Ol,Exp).
  160.   ch_term(["("|IL],Ol,Exp):- !,ch_exp(IL,Ol1,Exp),
  161.                              vorn(")",Ol1,Ol),!.
  162.   ch_term([H|IL],Ol,g(Nr,Bed)):- 
  163.     feldnamen(Flist),member(H,Art,Nr,1,Flist),
  164.     erzeugen(IL,Ol,Art,Bed).
  165.  
  166.   ch_term1([X|IL],Ol,Exp1,Exp):- 
  167.     upper_lower("UND",X),!,ch_term(IL,Ol1,Exp2),
  168.     ch_term1(Ol1,Ol,und(Exp1,Exp2),Exp).
  169.   ch_term1([X|IL],Ol,Exp1,Exp):- 
  170.     upper_lower("ODER",X),ch_term(IL,Ol1,Exp2),
  171.     ch_term1(Ol1,Ol,oder(Exp1,Exp2),Exp).
  172.   ch_term1(IL,IL,Exp,Exp):- !.
  173.  
  174.   /* Darstellung eines bestimmten Auswahlkriteriums 
  175.      in Listenform z.B. 
  176.      <=20 in Form von [s("<="),i(20)]               */
  177.   erzeugen([Op,X,C,C,Y|T],T,Art,[s("IN"),X1,Y1]):- 
  178.     upper_lower("IN",Op),
  179.     str_char(C,'.'),!,
  180.     konversion(Art,X,X1),konversion(Art,Y,Y1).
  181.   erzeugen(["<","=",X|T],T,Art,[s("<="),Y]):-
  182.     !,konversion(Art,X,Y).
  183.   erzeugen([">","=",X|T],T,Art,[s(">="),Y]):-
  184.     !,konversion(Art,X,Y).
  185.   erzeugen(["<",X|T],T,Art,[s("<"),Y]):-
  186.     !,konversion(Art,X,Y).
  187.   erzeugen([">",X|T],T,Art,[s(">"),Y]):-
  188.     !,konversion(Art,X,Y).
  189.   erzeugen(["=",X|T],T,Art,[s("="),Y]):-
  190.     !,konversion(Art,X,Y).
  191.   erzeugen(["<",">",X|T],T,Art,[s("<>"),Y]):-
  192.     !,konversion(Art,X,Y).
  193.   erzeugen(_,_,_,_):- asserta(eingabe([""])),fail.
  194.  
  195.   /* Abspalten des Listenkopfes und 
  196.      Rücklieferung des Restes der Liste */
  197.   vorn(X,[X|T],T).  
  198.  
  199.   /* Löschen der gesamten Datenbasis 
  200.     oder eines Teils der Datenbasis */
  201.   loeschen(X):- retract(X),fail.
  202.   loeschen(_).
  203.   
  204.   /* ERMITTLUNG DER DATEISTRUKTUR 
  205.      UND EINLESEN DER DATENSÄTZE
  206.      Die Dateistruktur ist unter NAME.STR gespeichert; 
  207.      die Datei, die die Datensätze enthält, 
  208.      muß den Zusatz 'DAT' besitzen; die Datensätze 
  209.      werden der Datenbasis hinzugefügt                  */
  210.  
  211.   lesen:- loeschen(_),
  212.           makewindow(2,7,7,"Datei wählen!",5,20,15,40),
  213.           clearwindow,dir(".","*.dat",Dateiname),
  214.           tokl(Dateiname,[H|_]),concat(H,".str",SDatei),
  215.           write(""),openread(f,SDatei),readdevice(f),
  216.           felder(FeldL,NoF,0),asserta(feldnamen(FeldL)),
  217.           closefile(f),read_Data(Dateiname,NoF),!,
  218.           removewindow,asserta(name_der_Datei(Dateiname)).
  219.  
  220.   /* Lesen der Dateistruktur: 
  221.      Lesen der Feldnamen und Feldtypen;
  222.      Ermittlung der Zahl der Datenfelder; 
  223.      siehe das Beispiel zum domain 'strulist'           */
  224.   felder([t(A,B)|R],Anzahl,N):- 
  225.     not(eof(f)),!,readln(A),readln(B),
  226.     N1=N+1,felder(R,Anzahl,N1).
  227.   felder([],N,N).        
  228.  
  229.   /* Routinen zum Lesen der Datei und zum 
  230.      Transfer der Datensätze in das Prädikat 'daten' 
  231.      der Datenbasis                                    */
  232.   read_Data(FileName,FeldProRec):- 
  233.     openread(f,FileName),readdevice(f),
  234.     feldnamen(L),read_Records(L,FeldProRec),
  235.     readdevice(keyboard),closefile(f).
  236.  
  237.   read_Records(L,NrFeld):- 
  238.     not(eof(f)),!,read_One_Record(L,1,NrFeld,X),
  239.     assertz(daten(X)),read_Records(L,NrFeld).
  240.   read_Records(_,_).    /* Lesen der Datei */
  241.   
  242.   read_One_Record(_,N,NrFeld,[]):- 
  243.     N>NrFeld.  /* Lesen eines Datensatzes */
  244.   read_One_Record([t(_,Typ)|T1],N,NrFeld,[E|T2]):- 
  245.     !,readln(Str),konversion(Typ,Str,E),N1=N+1,
  246.     read_One_Record(T1,N1,NrFeld,T2).
  247.  
  248.   /* Umwandeln in den richtigen Datentyp */                                      
  249.   konversion("s",X,s(X)):-!.    
  250.   konversion("i",X,i(Y)):- !,str_int(X,Y).
  251.   konversion("r",X,r(Y)):- str_real(X,Y).               
  252.                           
  253.   /* Feststellung, ob der eingegebene Feldname 
  254.      richtig ist; außerdem Ermittlung von 
  255.      Feldnummer und Feldart                           */
  256.   member(Y,Art,Nr,Nr,[t(X,Art)|_]):- upper_lower(X,Y),!.
  257.   member(X,Art,Nr,N,[_|T]):- N1=N+1,member(X,Art,Nr,N1,T).
  258.   
  259.   /* Ausgabe der Dateistruktur */
  260.   ausgabe_struktur(Name):- 
  261.     cursor(1,1),   
  262.     write("Die Datei ",Name," hat folgende Struktur:"),nl,
  263.     write(" "),feldnamen(Felder),ausgabe(Felder,1).
  264.  
  265.   ausgabe([],_)./* Ausgabe der Feldnamen und ihrer Typen */
  266.   ausgabe([t(A,B)|T],N):- 
  267.     N mod 4=0,!,write(A,"(",B,")  "),nl,write(" "),
  268.     N1=N+1,ausgabe(T,N1).        
  269.   ausgabe([t(A,B)|T],N):- 
  270.     write(A,"(",B,")  "),N1=N+1,ausgabe(T,N1).                  
  271.  
  272.   /* AUSWAHL DER DATENSÄTZE die selektierten Datensätze 
  273.      werden in der Datenbank unter 'selektiert' 
  274.      gespeichert                                       */
  275.   suchen(Exp):- daten(Rec),pruefe_satz(Rec,Exp),
  276.                 assertz(selektiert(Rec)),fail.
  277.   suchen(_).
  278.   
  279.   /* werden die Auswahlkriterien erfüllt? */  
  280.   pruefe_satz(_,g(0,[])):- !. 
  281.   pruefe_satz(Rec,g(Nr,Rel)):- !,n_tes(Rec,Nr,Feld),
  282.                                pruefe_relation(Feld,Rel).
  283.   pruefe_satz(Rec,und(Exp1,Exp2)):- 
  284.     !,pruefe_satz(Rec,Exp1), pruefe_satz(Rec,Exp2).
  285.   pruefe_satz(Rec,oder(Exp1,_)):- 
  286.     pruefe_satz(Rec,Exp1),!.
  287.   pruefe_satz(Rec,oder(_,Exp2)):- pruefe_satz(Rec,Exp2),!.
  288.   pruefe_satz(Rec,nicht(Exp)):- not(pruefe_satz(Rec,Exp)).
  289.                  
  290.   /* Überprüfen eines bestimmten Kriteriums */
  291.   pruefe_relation(s(X),Y):- !,comp_string(s(X),Y).
  292.   pruefe_relation(i(X),Y):- !,comp_int(i(X),Y).
  293.   pruefe_relation(r(X),Y):- comp_real(r(X),Y).
  294.  
  295.   /* Stringvergleiche */
  296.   comp_string(s(F),[s("<="),s(X)]):- F<=X.
  297.   comp_string(s(F),[s(">="),s(X)]):- F>=X.
  298.   comp_string(s(F),[s("<"),s(X)]):- F<X.
  299.   comp_string(s(F),[s(">"),s(X)]):- F>X.
  300.   comp_string(s(F),[s("="),s(X)]):- F=X.
  301.   comp_string(s(F),[s("<>"),s(X)]):- F<>X. 
  302.   comp_string(s(F),[s("IN"),s(X),s(Y)]):- F>=X,F<=Y.
  303.  
  304.   /* Integervergleiche */
  305.   comp_int(i(F),[s("<="),i(X)]):- F<=X.
  306.   comp_int(i(F),[s(">="),i(X)]):- F>=X.
  307.   comp_int(i(F),[s("<"),i(X)]):- F<X.
  308.   comp_int(i(F),[s(">"),i(X)]):- F>X.
  309.   comp_int(i(F),[s("="),i(X)]):- F=X.
  310.   comp_int(i(F),[s("<>"),i(X)]):- F<>X. 
  311.   comp_int(i(F),[s("IN"),i(X),i(Y)]):- F>=X,F<=Y.  
  312.  
  313.   /* Realzahlenvergleiche */
  314.   comp_real(r(F),[s("<="),r(X)]):- F<=X.
  315.   comp_real(r(F),[s(">="),r(X)]):- F>=X.
  316.   comp_real(r(F),[s("<"),r(X)]):- F<X.
  317.   comp_real(r(F),[s(">"),r(X)]):- F>X.
  318.   comp_real(r(F),[s("="),r(X)]):- F=X.
  319.   comp_real(r(F),[s("<>"),r(X)]):- F<>X. 
  320.   comp_real(r(F),[s("IN"),r(X),r(Y)]):- F>=X,F<=Y.
  321.  
  322.   n_tes([K|_],1,K):-!.    /* n-tes Element einer Liste */
  323.   n_tes([_|T],N,E):- N1=N-1,n_tes(T,N1,E).
  324.  
  325.   /* Ausgabe der selektierten und sortierten Datensätze */
  326.   out([],_).
  327.   out([H|T],N):- choose(H,X),schreibe(X,N),nl,
  328.                  N1=N+1,out(T,N1).
  329.   
  330.   /* Zerlegen der Tokenliste in eine Selektionskriterien- und in eine
  331.      Sortierkriterienliste                              */ 
  332.   zerlegen([H|T],[H|R],S):- 
  333.     not(upper_lower("SORTIERT",H)), zerlegen(T,R,S),!.
  334.   zerlegen([],[],[]):-!.
  335.   zerlegen([_|T],[],T).                            
  336.  
  337.   /* Überprüfung der Sortierkriterien und Umwandlung in 
  338.      eine Liste; siehe das Beispiel zum domain 'infolist'*/
  339.   check([],[]):- !.
  340.   check([","|R],T):- check(R,T).
  341.   check(["-",X|R],[h("-",N)|T]):- 
  342.     !,feldnamen(F),member(X,_,N,1,F), check(R,T).
  343.   check([X|R],[h("+",N)|T]):- 
  344.     feldnamen(F),member(X,_,N,1,F),check(R,T).
  345.  
  346.   /* SORTIERROUTINEN */
  347.   qsort([H|T],S,X,Krit):- 
  348.     sammle(H,L,Krit),split(L,T,A,B,Krit),!,
  349.     qsort(A,S,[H|Y],Krit),
  350.     qsort(B,Y,X,Krit).
  351.   qsort([],X,X,_).
  352.   
  353.   split(L,[A|X],[A|Y],Z,Krit):- 
  354.     dem(Krit,A,L),!,split(L,X,Y,Z,Krit).
  355.   split(L,[A|X],Y,[A|Z],Krit):- 
  356.     not(dem(Krit,A,L)),!,split(L,X,Y,Z,Krit).
  357.   split(_,[],[],[],_).
  358.  
  359.   /* Auswahl jener Datenfelder, die das 
  360.      Sortierkriterium bilden                            */
  361.   dem([h("+",Nr)|R],A,[W|T]):-   
  362.     choose(A,X),!,n_tes(X,Nr,V),auf(A,T,V,W,R).
  363.   dem([h("-",Nr)|R],A,[W|T]):-
  364.     choose(A,X),!,n_tes(X,Nr,V),ab(A,T,V,W,R).
  365.   dem([],_,_).
  366.   
  367.   /* Festlegung, welches Prädikat der Datenbank 
  368.      die zu sortierenden Datensätze enthält             */
  369.   choose(selektiert(X),X).
  370.   choose(daten(X),X).
  371.  
  372.   /* aufsteigend sortieren */
  373.   auf(_,_,s(V),s(W),_):- V<W,!. 
  374.   auf(_,_,i(V),i(W),_):- V<W,!.
  375.   auf(_,_,r(V),r(W),_):- V<W,!.
  376.   auf(A,H,V,V,R):- dem(R,A,H).  
  377.   /* das erste Sortierkriterium reicht 
  378.      für die Sortierreihenfolge nicht aus */
  379.   
  380.   /* absteigend sortieren */
  381.   ab(_,_,s(V),s(W),_):- V>W,!.
  382.   ab(_,_,i(V),i(W),_):- V>W,!.  
  383.   ab(_,_,r(V),r(W),_):- V>W,!.
  384.   ab(A,H,V,V,R):- dem(R,A,H).
  385.     
  386.   sammle(_,[],[]).
  387.   sammle(H,[V|T],[h(_,Nr)|R]):- 
  388.     choose(H,Y),n_tes(Y,Nr,V),sammle(H,T,R).
  389.   
  390.   /* von 'findall' benötigt */
  391.   wahl1(selektiert(X)):- selektiert(X).  
  392.   wahl2(daten(X)):- daten(X).
  393.   
  394.   mode1(g(0,[]))./* keine Selektierkriterien eingegeben */
  395.   mode2([]).     /* keine Sortierkritererien eingegeben */
  396.  
  397.   /* Ausgabe aller Datensätze in unsortierter Form */
  398.   out1:- 
  399.     daten(X),n(N),schreibe(X,N),retract(n(N)),N1=N+1,
  400.     asserta(n(N1)),nl,fail.
  401.   out1.
  402.  
  403.   schreibe([],N):- warte(N).
  404.   schreibe([s(X)|T],N):- !,write(X,"   "),schreibe(T,N).
  405.   schreibe([i(X)|T],N):- !,write(X,"   "),schreibe(T,N).
  406.   schreibe([r(X)|T],N):- write(X,"   "),schreibe(T,N).
  407.   
  408.   warte(N):- N mod 10 = 0,readchar(_).
  409.   warte(_).
  410.     
  411. GOAL
  412.   run