(** val negb : bool -> bool **)

let negb = function true -> false | false -> true

(** val fst : ('a1 * 'a2) -> 'a1 **)

let fst = function x, _ -> x

(** val snd : ('a1 * 'a2) -> 'a2 **)

let snd = function _, y -> y

(** val app : 'a1 list -> 'a1 list -> 'a1 list **)

let rec app l m = match l with [] -> m | a :: l1 -> a :: app l1 m

(** val map : ('a1 -> 'a2) -> 'a1 list -> 'a2 list **)

let rec map f = function [] -> [] | a :: l0 -> f a :: map f l0

(** val firstn : int -> 'a1 list -> 'a1 list **)

let rec firstn n l =
  (fun fO fS n -> if n = 0 then fO () else fS (n - 1))
    (fun _ -> [])
    (fun n0 -> match l with [] -> [] | a :: l0 -> a :: firstn n0 l0)
    n

(** val flat_map : ('a1 -> 'a2 list) -> 'a1 list -> 'a2 list **)

let rec flat_map f = function [] -> [] | x :: l0 -> app (f x) (flat_map f l0)

(** val existsb : ('a1 -> bool) -> 'a1 list -> bool **)

let rec existsb f = function [] -> false | a :: l0 -> f a || existsb f l0

(** val forallb : ('a1 -> bool) -> 'a1 list -> bool **)

let rec forallb f = function [] -> true | a :: l0 -> f a && forallb f l0

(** val filter : ('a1 -> bool) -> 'a1 list -> 'a1 list **)

let rec filter f = function
  | [] -> []
  | x :: l0 -> if f x then x :: filter f l0 else filter f l0

(** val find : ('a1 -> bool) -> 'a1 list -> 'a1 option **)

let rec find f = function
  | [] -> None
  | x :: tl -> if f x then Some x else find f tl

(** val eqb : char list -> char list -> bool **)

let rec eqb s1 s2 =
  match s1 with
  | [] -> ( match s2 with [] -> true | _ :: _ -> false)
  | c1 :: s1' -> (
      match s2 with
      | [] -> false
      | c2 :: s2' -> if c1 = c2 then eqb s1' s2' else false)

(** val append : char list -> char list -> char list **)

let rec append s1 s2 = match s1 with [] -> s2 | c :: s1' -> c :: append s1' s2

type attr_name = char list
type domain_name = char list
type schema = (attr_name * domain_name) list

(** val has_attr : attr_name -> schema -> bool **)

let has_attr a s = existsb (fun p -> eqb a (fst p)) s

(** val attr_names : schema -> attr_name list **)

let attr_names s = map fst s

(** val filter_schema : attr_name list -> schema -> schema **)

let filter_schema attrs s = filter (fun p -> existsb (eqb (fst p)) attrs) s

(** val merge_schema : schema -> schema -> schema **)

let merge_schema s1 s2 =
  app s1 (filter (fun p -> negb (has_attr (fst p) s1)) s2)

(** val remove_attrs : attr_name list -> schema -> schema **)

let remove_attrs attrs s =
  filter (fun p -> negb (existsb (eqb (fst p)) attrs)) s

(** val rename_in_schema : (attr_name * attr_name) list -> schema -> schema **)

let rename_in_schema renames s =
  map
    (fun p ->
      let a = fst p in
      let d = snd p in
      match find (fun r -> eqb a (fst r)) renames with
      | Some p0 ->
          let _, a' = p0 in
          (a', d)
      | None -> (a, d))
    s

type value (* AXIOM TO BE REALIZED *)

(** val value_eqb : value -> value -> bool **)

let value_eqb = failwith "AXIOM TO BE REALIZED (Sakura.Relation.value_eqb)"

type tuple = (attr_name * value) list

(** val tuple_lookup : attr_name -> tuple -> value option **)

let rec tuple_lookup a = function
  | [] -> None
  | p :: rest ->
      let a', v = p in
      if eqb a a' then Some v else tuple_lookup a rest

(** val project_tuple : attr_name list -> tuple -> tuple **)

let project_tuple attrs t = filter (fun p -> existsb (eqb (fst p)) attrs) t

(** val rename_tuple : (attr_name * attr_name) list -> tuple -> tuple **)

let rename_tuple renames t =
  map
    (fun p ->
      let a = fst p in
      let v = snd p in
      match find (fun r -> eqb a (fst r)) renames with
      | Some p0 ->
          let _, a' = p0 in
          (a', v)
      | None -> (a, v))
    t

(** val merge_tuples : tuple -> tuple -> tuple **)

let merge_tuples t1 t2 =
  app t1 (filter (fun p -> negb (existsb (eqb (fst p)) (map fst t1))) t2)

(** val tuples_agree_on : attr_name list -> tuple -> tuple -> bool **)

let tuples_agree_on attrs t1 t2 =
  forallb
    (fun a ->
      match tuple_lookup a t1 with
      | Some v1 -> (
          match tuple_lookup a t2 with
          | Some v2 -> value_eqb v1 v2
          | None -> false)
      | None -> ( match tuple_lookup a t2 with Some _ -> false | None -> true))
    attrs

type relation = {
  rel_name : char list;
  rel_schema : schema;
  rel_tuples : tuple list;
}

type database = (char list * relation) list

(** val db_lookup : char list -> database -> relation option **)

let rec db_lookup name = function
  | [] -> None
  | p :: rest ->
      let n, r = p in
      if eqb name n then Some r else db_lookup name rest

type literal = LitInt of int | LitStr of char list | LitBool of bool

type query =
  | Base of char list
  | Const of (attr_name * literal) list
  | Select of query * query
  | Join of attr_name list * query * query
  | Cartesian of query * query
  | Project of attr_name list * query
  | Rename of (attr_name * attr_name) list * query
  | Union of query * query
  | Diff of query * query
  | Take of int * query

(** val predicted_schema : database -> query -> schema option **)

let rec predicted_schema db = function
  | Base name -> (
      match db_lookup name db with Some r -> Some r.rel_schema | None -> None)
  | Const pairs ->
      Some
        (map
           (fun p -> (fst p, [ 'a'; 'b'; 's'; 't'; 'r'; 'a'; 'c'; 't' ]))
           pairs)
  | Select (_, source) -> predicted_schema db source
  | Join (attrs, q1, q2) -> (
      match predicted_schema db q1 with
      | Some s1 -> (
          match predicted_schema db q2 with
          | Some s2 ->
              Some
                (merge_schema s1
                   (remove_attrs (attr_names s1) (remove_attrs attrs s2)))
          | None -> None)
      | None -> None)
  | Cartesian (q1, q2) -> (
      match predicted_schema db q1 with
      | Some s1 -> (
          match predicted_schema db q2 with
          | Some s2 -> Some (merge_schema s1 s2)
          | None -> None)
      | None -> None)
  | Project (attrs, q') -> (
      match predicted_schema db q' with
      | Some s -> Some (filter_schema attrs s)
      | None -> None)
  | Rename (renames, q') -> (
      match predicted_schema db q' with
      | Some s -> Some (rename_in_schema renames s)
      | None -> None)
  | Union (q1, _) -> predicted_schema db q1
  | Diff (q1, _) -> predicted_schema db q1
  | Take (_, q') -> predicted_schema db q'

(** val literal_to_value : literal -> value **)

let literal_to_value =
  failwith "AXIOM TO BE REALIZED (Sakura.Drl.literal_to_value)"

(** val eval_const : (attr_name * literal) list -> relation **)

let eval_const pairs =
  let tuple0 = map (fun p -> (fst p, literal_to_value (snd p))) pairs in
  let sch =
    map (fun p -> (fst p, [ 'a'; 'b'; 's'; 't'; 'r'; 'a'; 'c'; 't' ])) pairs
  in
  {
    rel_name = [ 'c'; 'o'; 'n'; 's'; 't' ];
    rel_schema = sch;
    rel_tuples = tuple0 :: [];
  }

(** val semijoin : relation -> relation -> relation **)

let semijoin filter_rel source =
  let common =
    filter
      (fun a -> has_attr a filter_rel.rel_schema)
      (attr_names source.rel_schema)
  in
  let matches =
   fun t ->
    existsb (fun ft -> tuples_agree_on common t ft) filter_rel.rel_tuples
  in
  {
    rel_name = source.rel_name;
    rel_schema = source.rel_schema;
    rel_tuples = filter matches source.rel_tuples;
  }

(** val equijoin : attr_name list -> relation -> relation -> relation **)

let equijoin attrs left right =
  let joined =
    flat_map
      (fun lt ->
        flat_map
          (fun rt ->
            if tuples_agree_on attrs lt rt then merge_tuples lt rt :: [] else [])
          right.rel_tuples)
      left.rel_tuples
  in
  let new_schema =
    merge_schema left.rel_schema
      (remove_attrs
         (attr_names left.rel_schema)
         (remove_attrs attrs right.rel_schema))
  in
  {
    rel_name =
      append
        [ 'j'; 'o'; 'i'; 'n'; '_' ]
        (append left.rel_name (append ('_' :: []) right.rel_name));
    rel_schema = new_schema;
    rel_tuples = joined;
  }

(** val cartesian : relation -> relation -> relation **)

let cartesian left right =
  let joined =
    flat_map
      (fun lt -> map (fun rt -> merge_tuples lt rt) right.rel_tuples)
      left.rel_tuples
  in
  {
    rel_name =
      append
        [ 'c'; 'a'; 'r'; 't'; '_' ]
        (append left.rel_name (append ('_' :: []) right.rel_name));
    rel_schema = merge_schema left.rel_schema right.rel_schema;
    rel_tuples = joined;
  }

(** val project : attr_name list -> relation -> relation **)

let project attrs r =
  {
    rel_name = append [ 'p'; 'r'; 'o'; 'j'; '_' ] r.rel_name;
    rel_schema = filter_schema attrs r.rel_schema;
    rel_tuples = map (project_tuple attrs) r.rel_tuples;
  }

(** val rename : (attr_name * attr_name) list -> relation -> relation **)

let rename renames r =
  {
    rel_name = append [ 'r'; 'e'; 'n'; 'a'; 'm'; 'e'; '_' ] r.rel_name;
    rel_schema = rename_in_schema renames r.rel_schema;
    rel_tuples = map (rename_tuple renames) r.rel_tuples;
  }

(** val rel_union : relation -> relation -> relation **)

let rel_union r1 r2 =
  {
    rel_name =
      append
        [ 'u'; 'n'; 'i'; 'o'; 'n'; '_' ]
        (append r1.rel_name (append ('_' :: []) r2.rel_name));
    rel_schema = r1.rel_schema;
    rel_tuples = app r1.rel_tuples r2.rel_tuples;
  }

(** val rel_diff : relation -> relation -> relation **)

let rel_diff r1 r2 =
  let in_r2 =
   fun t ->
    existsb
      (fun t2 -> tuples_agree_on (attr_names r1.rel_schema) t t2)
      r2.rel_tuples
  in
  {
    rel_name =
      append
        [ 'd'; 'i'; 'f'; 'f'; '_' ]
        (append r1.rel_name (append ('_' :: []) r2.rel_name));
    rel_schema = r1.rel_schema;
    rel_tuples = filter (fun t -> negb (in_r2 t)) r1.rel_tuples;
  }

(** val take : int -> relation -> relation **)

let take n r =
  {
    rel_name = append [ 't'; 'a'; 'k'; 'e'; '_' ] r.rel_name;
    rel_schema = r.rel_schema;
    rel_tuples = firstn n r.rel_tuples;
  }

(** val eval : database -> query -> relation option **)

let rec eval db = function
  | Base name -> db_lookup name db
  | Const pairs -> Some (eval_const pairs)
  | Select (filter_q, source_q) -> (
      match eval db filter_q with
      | Some filter_rel -> (
          match eval db source_q with
          | Some source_rel -> Some (semijoin filter_rel source_rel)
          | None -> None)
      | None -> None)
  | Join (attrs, q1, q2) -> (
      match eval db q1 with
      | Some r1 -> (
          match eval db q2 with
          | Some r2 -> Some (equijoin attrs r1 r2)
          | None -> None)
      | None -> None)
  | Cartesian (q1, q2) -> (
      match eval db q1 with
      | Some r1 -> (
          match eval db q2 with
          | Some r2 -> Some (cartesian r1 r2)
          | None -> None)
      | None -> None)
  | Project (attrs, q') -> (
      match eval db q' with Some r -> Some (project attrs r) | None -> None)
  | Rename (renames, q') -> (
      match eval db q' with Some r -> Some (rename renames r) | None -> None)
  | Union (q1, q2) -> (
      match eval db q1 with
      | Some r1 -> (
          match eval db q2 with
          | Some r2 -> Some (rel_union r1 r2)
          | None -> None)
      | None -> None)
  | Diff (q1, q2) -> (
      match eval db q1 with
      | Some r1 -> (
          match eval db q2 with
          | Some r2 -> Some (rel_diff r1 r2)
          | None -> None)
      | None -> None)
  | Take (n, q') -> (
      match eval db q' with Some r -> Some (take n r) | None -> None)