(** 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)

type attr_name = char list

type relation = { rel_name : char list; rel_finite : bool }

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_finite : database -> query -> bool option **)

let rec predicted_finite db = function
| Base name ->
  (match db_lookup name db with
   | Some r -> Some r.rel_finite
   | None -> None)
| Select (_, source) -> predicted_finite db source
| Join (_, q1, q2) ->
  (match predicted_finite db q1 with
   | Some f1 ->
     (match predicted_finite db q2 with
      | Some f2 -> Some ((&&) f1 f2)
      | None -> None)
   | None -> None)
| Cartesian (q1, q2) ->
  (match predicted_finite db q1 with
   | Some f1 ->
     (match predicted_finite db q2 with
      | Some f2 -> Some ((&&) f1 f2)
      | None -> None)
   | None -> None)
| Project (_, q0) -> predicted_finite db q0
| Rename (_, q0) -> predicted_finite db q0
| Union (q1, q2) ->
  (match predicted_finite db q1 with
   | Some f1 ->
     (match predicted_finite db q2 with
      | Some f2 -> Some ((&&) f1 f2)
      | None -> None)
   | None -> None)
| Diff (q1, _) -> predicted_finite db q1
| _ -> Some true