cacol89 avatar cacol89 committed bede162 Merge

Merge branch 'feature/negation' into develop

Comments (0)

Files changed (7)

     in
     "SELECT "^(alias 0 cols)
 
+(** Calculates the SQL of negated rterms with an inner query of
+ * the form ( NOT EXISTS SELECT * FROM Table WHERE ... ).
+ * @param idb       Symtable of the IDB
+ * @param vt        Vartab with the name of the variables
+ * @param cnt       Colnamtab with the name of relation's columns 
+ * @param eqtab     Eqtab with the variables that appear as equalities
+ * @param neg_rt    List of negated rterms.
+ * @return          List of SQL restrictions that ensures the negation
+ * *)
+let sql_of_negated_rterms (idb:symtable) (vt:vartab) (cnt:colnamtab) (eqt:eqtab) neg_rt =
+    let gen_neg_sql rt =
+        (*get basic info of the rterm*)
+        let key = symtkey_of_rterm rt in
+        let pname = get_rterm_predname rt in
+        let arity = get_arity rt in 
+        let alias = pname^"_a"^(string_of_int arity) in
+        let vlst = get_rterm_varlist rt in
+        let cnames = Hashtbl.find cnt key in
+        (*Get the from sql of the rterm*)
+        let from_sql =
+            if Hashtbl.mem idb key then
+                "FROM "^alias
+            else
+                "FROM "^pname^" AS "^alias
+        in
+        (*Get the where sql of the rterm*)
+        let build_const acc col var =
+            let eq_to = alias^"."^col^" = " in
+            match var with
+            | NamedVar vn -> 
+                if Hashtbl.mem vt vn then
+                    (eq_to^(List.hd (Hashtbl.find vt vn)))::acc
+                else if Hashtbl.mem eqt vn then
+                    (eq_to^(string_of_const (Hashtbl.find eqt vn)))::acc
+                else raise (Yadi_error (
+                    "Program is unsafe, variable "^vn^
+                    " in negated call to predicate "^
+                    (string_of_symtkey key)^" does not appear in a positive "^
+                    "goal or strict equation. Try anonimous variables."
+                )) 
+            | ConstVar c -> (eq_to^(string_of_const c))::acc
+            | AnonVar -> acc
+            | NumberedVar _ -> invalid_arg "There is a numbered var in a negated rterm"
+        in
+        let const_lst = List.fold_left2 build_const [] cnames vlst in
+        let where_sql =
+            if const_lst = [] then ""
+            else "WHERE "^(String.concat " AND " const_lst)
+        in
+        (**Return the final string*)
+        "NOT EXISTS ( SELECT * "^from_sql^" "^where_sql^" )"
+    in
+    List.map gen_neg_sql neg_rt
+
 (** Calculates the relations that must be in the where clause. 
- * @param vartab    Vartab with the name of the variables
+ * @param idb       Symtable of the IDB
+ * @param vt        Vartab with the name of the variables
+ * @param cnt       Colnamtab with the name of relation's columns 
  * @param eqtab     Eqtab with the variables that appear as equalities
  * @param ineq      List of inequalities in the form (operator,varname,value)
+ * @param neg_rt    List of negated rterms.
  * @return WHERE clause including necessary tabs, 
  * if there is not any returns an empty string*)
-let get_where_clause (vt:vartab) (eqt:eqtab) ineq = 
+let get_where_clause (idb:symtable) (vt:vartab) (cnt:colnamtab) (eqt:eqtab) ineq neg_rt = 
     (*Transform a list of column names in eq relations [a,b,c] -> ['a=b';'a=c']*)
     let var_const _ cols acc = match cols with
         | [] -> acc
         let cname = List.hd (Hashtbl.find vt vname) in
         (cname^" "^op^" "^(string_of_const value))::acc in
     let fineq = List.fold_right ineq_const ineq [] in
+    (*Transform the negated rterms into SQL*)
+    let fnrt = sql_of_negated_rterms idb vt cnt eqt neg_rt in
     (*merge all constraints*)
-    let constraints = fvt@feqt@fineq in
+    let constraints = fvt@feqt@fineq@fnrt in
     match constraints with
         | [] -> ""
         | _ -> "WHERE "^(String.concat " AND " constraints)
 let split_terms terms =
     let rec split t (pos,neg,eq,inq) = match t with
         | Rel rt -> (rt::pos,neg,eq,inq)
-        | Not t -> (pos,t::neg,eq,inq)
+        | Not rt -> (pos,rt::neg,eq,inq)
         | Equal (x,y) -> (pos,neg,(x,y)::eq,inq) 
         | Ineq (op,x,y) -> (pos,neg,eq,(op,x,y)::inq) in
     List.fold_right split terms ([],[],[],[])
     let head = rule_head rule in
     let body = rule_body rule in
     (*Extract positive rterms from the rule*)
-    let (rterms,_,equalities,ineq) = split_terms body in
+    let (p_rt,n_rt,equalities,ineq) = split_terms body in
     (*Build vartab, and eqtab for select and where clauses*)
-    let vt = build_vartab cnt rterms in
+    let vt = build_vartab cnt p_rt in
     let eqt = build_eqtab equalities in
     let select_sql = get_select_clause vt eqt head in
-    let from_sql = get_from_clause idb rterms in
-    let where_sql = get_where_clause vt eqt ineq in
+    let from_sql = get_from_clause idb p_rt in
+    let where_sql = get_where_clause idb vt cnt eqt ineq n_rt in
     String.concat " " [select_sql;from_sql;where_sql]
 
 (**Takes a list of similar rules (same head) and generates the SQL statement
     | Rel of rterm
     | Equal of var * const
     | Ineq of string * var * const
-    | Not of term
+    | Not of rterm
 and const =
     | Int of int
     | Real of float
 
 (** get the list of variables of a term *)
 let rec get_varlist t = match t with
-    | Rel r            -> ( match r with
-                            | Pred (x, vl) -> vl
-                        )
+    | Rel r            -> get_rterm_varlist r
     | Equal (s, i)     -> s :: []
     | Ineq  (op,s, i)  -> s :: []
-    | Not t            -> get_varlist t
+    | Not r            -> get_rterm_varlist r
 ;;
 
 (** Given a query, returns the rterm that is defined inside*)
     | Rule(_, t) ->
         let rec extract_rterm acc = function
             | Rel x -> x::acc
-            | Not x -> extract_rterm acc x
+            | Not x -> x::acc
             | _ -> acc in
         List.fold_left extract_rterm [] t
     | Query _    -> invalid_arg "function get_all_rule_rterms called with a query"
 
+(*Given an equation, returns the equivalent of a negation of it*)
+let negate_eq = function
+    | Equal (v,c) -> Ineq ("<>",v,c)
+    | Ineq ("<>",v,c) -> Equal (v,c)
+    | Ineq ("<",v,c) -> Ineq (">=",v,c)
+    | Ineq (">",v,c) -> Ineq ("<=",v,c)
+    | Ineq ("<=",v,c) -> Ineq (">",v,c)
+    | Ineq (">=",v,c) -> Ineq ("<",v,c)
+    | _ -> invalid_arg "function negate_eq called without an equation"
 
 (****************************************************
  *
     | Rel r             -> string_of_rterm r
     | Equal (s, i)      -> string_of_var s ^ " = " ^ string_of_const i
     | Ineq (op,s, i)    -> string_of_var s ^ " " ^ op ^ " " ^ string_of_const i
-    | Not t             -> "not " ^ string_of_term t
+    | Not rt            -> "not " ^ string_of_rterm rt
 ;;
 
 (** support function for smart stringify of the AST - see to_string below *)
 
   literal:
   | predicate							{ Rel $1 }
-  | NOT predicate 						{ Not (Rel $2) }
+  | NOT predicate 						{ Not $2 }
   | equation							{ $1 }
-  | NOT equation					        { Not $2 }
+  | NOT equation					        { negate_eq $2 }
   ;
 
   predicate:

src/rule_preproc.ml

     | Rel rt ->
         let rt_key = symtkey_of_rterm rt in
         (key_comp key rt_key) = 0
-    | Not t ->
-        if (check_rec_term key t) then
+    | Not rt ->
+        if (check_rec_term key (Rel rt)) then
             raise (Yadi_error (
                 "Predicate "^(string_of_symtkey key)^
                 " is negatively recursive"

test/expected/integration/beer.out

+
+yadi$ 
+---------
+| col0  |
+---------
+| Leffe |
+---------
+
+yadi$ 
+--------
+| col0 |
+--------
+| Bob  |
+| Bob  |
+| Joe  |
+--------
+
+yadi$ 
+------------
+| col0     |
+------------
+| IrishPub |
+| IrishPub |
+| IrishPub |
+------------
+
+yadi$ 
+--------------
+| col0       |
+--------------
+| DrinkPlace |
+--------------
+
+yadi$ 
+------------
+| col0     |
+------------
+| IrishPub |
+------------
+
+yadi$ 
+----------------------
+| col0  | col1       |
+----------------------
+| Jane  | DrinkPlace |
+| Jane  | DrinkPlace |
+| Suzie | IrishPub   |
+| Suzie | IrishPub   |
+| Suzie | IrishPub   |
+| Jane  | TheBar     |
+| Jane  | TheBar     |
+| Jane  | TheBar     |
+| Jane  | TheBar     |
+| Joe   | TheBar     |
+| Joe   | TheBar     |
+----------------------
+
+yadi$ 
+------------
+| col0     |
+------------
+| IrishPub |
+------------
+
+yadi$ 
+--------------
+| col0       |
+--------------
+| IrishPub   |
+| IrishPub   |
+| IrishPub   |
+| DrinkPlace |
+--------------
+
+yadi$ 
+---------
+| col0  |
+---------
+| Jane  |
+| Jane  |
+| Suzie |
+---------
+
+yadi$ 
+---------
+| col0  |
+---------
+| Joe   |
+| Jane  |
+| Jane  |
+| Suzie |
+---------
+
+yadi$ YADI execution error: Program is unsafe, variable y in negated call to predicate Serves/2 does not appear in a positive goal or strict equation. Try anonimous variables.
+
+yadi$ 

test/integration/beer.datalog

+%%%%%%%%%%%%%%%%%%
+% General negation
+%%%%%%%%%%%%%%%%%%
+
+%Beers that no one likes
+
+Lame_beers(x) :- Serves(_,x), not Likes(_,x).
+?- Lame_beers(x).
+/
+
+%Drinkers who frequent only bars that serve some beer that they like
+
+Can_go(drinker,bar) :- Likes(drinker,beer), Serves(bar,beer).
+Banned(drinker) :- Frequents(drinker,bar), not Can_go(drinker,bar).
+Only_like(drinker) :- Frequents(drinker,_), not Banned(drinker).
+?- Only_like(drinker).
+/
+
+%Bars that serve all beers that bob likes
+
+Bob_likes(beer) :- Likes('Bob',beer).
+Banned(bar) :- Serves(bar,_), Bob_likes(beer), not Serves(bar, beer).
+Serves_all(bar) :- Serves(bar,_), not Banned(bar).
+?- Serves_all(bar).
+/
+
+%Bars that serve only beers that bob likes
+
+Bob_likes(beer) :- Likes('Bob',beer).
+Banned(bar) :- Serves(bar,beer), not Bob_likes(beer).
+Serves_only(bar) :- Serves(bar,_), not Banned(bar).
+?- Serves_only(bar).
+/
+
+%Bars that serve beers that no one likes
+
+Lame_bar(bar) :- Serves(bar,beer), not Likes(_,beer).
+?- Lame_bar(bar).
+/
+
+%Drinker-Bar touples, such that the drinker does not frequent the bar
+%and the bar does not serve beers s/he likes
+
+Good_tuple(drinker,bar) :- Likes(drinker,beer), Serves(bar,beer).
+Bad_tuple(drinker,bar) :- Likes(drinker,_), Serves(bar,_), not Frequents(drinker,bar), not Good_tuple(drinker,bar).
+?- Bad_tuple(drinker,bar).
+/
+
+%%%%%%%%%%%%%%%%%%
+% Negated inequalities
+%%%%%%%%%%%%%%%%%%
+
+Some_bar(x) :- not x <> 'IrishPub'.
+?- Some_bar(x).
+/
+
+Some_bars(x) :- Serves(x,_), not x > 'IrishPub'.
+?- Some_bars(x).
+/
+
+%%%%%%%%%%%%%%%%%%
+% Constant in negation
+%%%%%%%%%%%%%%%%%%
+
+%Drinkers that don't like Heiniken
+
+No_heiniken(drinker) :- Likes(drinker,_), not Likes(drinker,'Heiniken').
+?- No_heiniken(drinker).
+/
+
+%Drinkers that don't like Budweiser
+
+No_heiniken(drinker) :- Likes(drinker,_), beer = 'Budweiser', not Likes(drinker,beer).
+?- No_heiniken(drinker).
+/
+
+%%%%%%%%%%%%%%%%%%
+% Not defined var in negation (not allowed)
+%%%%%%%%%%%%%%%%%%
+
+Beer(x) :- Likes(_,x), not Serves(y,z).
+?- Beer(x).
+/
+

test/sql/beer.sql

+DROP TABLE IF EXISTS Likes CASCADE;
+DROP TABLE IF EXISTS Serves CASCADE;
+DROP TABLE IF EXISTS Frequents CASCADE;
+
+CREATE TABLE Likes (
+    Drinker TEXT NOT NULL,
+    Beer TEXT NOT NULL
+);
+
+CREATE TABLE Serves (
+    Bar TEXT NOT NULL,
+    Beer TEXT NOT NULL
+);
+
+CREATE TABLE Frequents (
+    Drinker TEXT NOT NULL,
+    Bar TEXT NOT NULL
+);
+
+
+INSERT INTO Likes(Drinker,Beer) VALUES('Bob','Budweiser');
+INSERT INTO Likes(Drinker,Beer) VALUES('Bob','Heiniken');
+INSERT INTO Likes(Drinker,Beer) VALUES('Joe','Heiniken');
+INSERT INTO Likes(Drinker,Beer) VALUES('Jane','Labatt Blue');
+INSERT INTO Likes(Drinker,Beer) VALUES('Jane','Molsen');
+INSERT INTO Likes(Drinker,Beer) VALUES('Suzie','Miller');
+
+INSERT INTO Serves(Bar,Beer) VALUES('IrishPub','Budweiser');
+INSERT INTO Serves(Bar,Beer) VALUES('IrishPub','Heiniken');
+INSERT INTO Serves(Bar,Beer) VALUES('IrishPub','Leffe');
+INSERT INTO Serves(Bar,Beer) VALUES('TheBar','Budweiser');
+INSERT INTO Serves(Bar,Beer) VALUES('TheBar','Miller');
+INSERT INTO Serves(Bar,Beer) VALUES('DrinkPlace','Heiniken');
+
+INSERT INTO Frequents(Drinker,Bar) VALUES('Bob','IrishPub');
+INSERT INTO Frequents(Drinker,Bar) VALUES('Bob','TheBar');
+INSERT INTO Frequents(Drinker,Bar) VALUES('Joe','DrinkPlace');
+INSERT INTO Frequents(Drinker,Bar) VALUES('Jane','IrishPub');
+INSERT INTO Frequents(Drinker,Bar) VALUES('Suzie','TheBar');
+INSERT INTO Frequents(Drinker,Bar) VALUES('Suzie','DrinkPlace');
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.