Write an interpreter that uses relational database operations to evaluate the queries in a Datalog Program. For this project, use only the schemes and facts to evaluate the queries. $($The evaluation of rules will be added in the next project.$)$

Example Input

Schemes: SK$($A$,$B$)$ Facts: SK$(\text{'}$a$\text{'},\text{'}$c$\text{'}).$ SK$(\text{'}$b$\text{'},\text{'}$c$\text{'}).$ SK$(\text{'}$b$\text{'},\text{'}$b$\text{'}).$ SK$(\text{'}$b$\text{'},\text{'}$c$\text{'}).$ Rules: Queries: SK$($X$,\text{'}$c$\text{'})?$ SK$(\text{'}$b$\text{'},\text{'}$c$\text{'})?$ SK$($X$,$X$)?$ SK$($X$,$Y$)?$ SK$(\text{'}$c$\text{'},\text{'}$c$\text{'})?$

Example Output

SK$($X$,\text{'}$c$\text{'})?$ Yes$(2)$ X$=\text{'}$a$\text{'}$ X$=\text{'}$b$\text{'}$ SK$(\text{'}$b$\text{'},\text{'}$c$\text{'})?$ Yes$(1)$ SK$($X$,$X$)?$ Yes$(1)$ X$=\text{'}$b$\text{'}$ SK$($X$,$Y$)?$ Yes$(3)$ X$=\text{'}$a$\text{'},$ Y$=\text{'}$c$\text{'}$ X$=\text{'}$b$\text{'},$ Y$=\text{'}$b$\text{'}$ X$=\text{'}$b$\text{'},$ Y$=\text{'}$c$\text{'}$ SK$(\text{'}$c$\text{'},\text{'}$c$\text{'})?$ No

The Database Classes

The solution for this project has two main parts, $(1)$ a simple relational database and $(2)$ an interpreter that uses the database to evaluate queries.

A relational database is a collection of relations. A relation has a name, a header, and a set of tuples. A header$$is a list of attribute names. A tuple is a list of attribute values. Relations are used as operands in relational operations such as select, project, and rename.

In this project a Datalog program is represented by a database. Each scheme in the program defines a relation in the database. Each fact in the program defines a tuple in a relation.

Write classes that implement a simple relational database. Your design must include at least the following classes: Database, Relation, Header, and Tuple. Provide functions in the Relation class for each of the relational operations $($select$,$ project, and rename$).$ Each of these functions operates on an existing relation and returns a new Relation $($the result of the operation$).$

The Relation class must use a set data type to hold the tuples in the relation.

Test your database classes before combining them with the query interpreter described in the next section.

Decouple the database classes from the Datalog classes. For example, don't have Tuples that contain Parameters.

Datalog Program Evaluation