During this activity, students should be able to:
This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.
This is an optional activity that is offered exclusively to those students that have an average of 85.0 or more in their First and Second Record grades of the Programming Languages course. If you meet this requirement, then this activity can replace the course’s final exam. If, for any reason, you do not complete it, then you must take the final exam with the rest of your classmates.
The activity must be developed individually.
Using Clojure, write an internal Domain-Specific Language (DSL) that implements a subset of E. F. Codd’s Relational Algebra. This DSL will allow querying a simple database that consists of several CSV (Comma-Separated Values) files.
The rel_algebra.tgz tarball contains the files you’ll need to use in order to program the DSL:
tests.clj: Unit tests for the DSL. Make sure that your code passes all these tests.
rectangle.clj: Code example that demonstrates how to write a new record type that overrides Java’s Object.toString() method and redefines the way the REPL prints its instances.
courses.csvenrollments.csvpizzas.csvstudents1.csvstudents2.csv: CSV files that contain tabular data that will be used to create relations by the DSL.
Your code may only use the following Clojure namespaces, any other libraries are off limits:
clojure.core
clojure.string
clojure.test
You must place all your code and the unit tests in one file called rel_algebra.clj. The next sections describe all the operations that the DSL must provide.
(relation file-name)
This factory function creates a new relation object, taking the data from a table contained in a CSV file. The relation object must be an instance of a record (created with defrecord) or type (created with deftype). The parameter file-name must be a keyword naming a file with a .csv extension contained in the current directory.
TIP: Use the slurp function to read the full contents of a file.
In the CSV file, the first row contains the unique names of the relation attributes; the following rows contain the data. If an individual data item in the CSV file is comprised of a sequence of one or more decimal digits, that item must be converted and stored in memory as an integer number. Otherwise, data items are stored as strings.
Examples:
user=> (relation :students1) +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (def p (relation :pizzas)) #'user/p user=> p +-----------+--------+ | flavor | size | +-----------+--------+ | Hawaiian | Medium | | Pepperoni | Large | | Supreme | Small | +-----------+--------+
Note that the REPL displays the relation as the table produced by the str function (the file rectangle.clj demonstrates how to do this).
(str relation)
Converts relation to its string representation. You need to override Java’s Object.toString() method in order to extend the behavior of the str function (the file rectangle.clj demonstrates how to do this).
NOTE: All unit tests assume that this function works as expected, so make sure to get this one working right from the very beginning.
Example:
user=> (def s1 (relation :students1)) #'user/s1 user=> (str s1) "+-----+------------------+-----+\n| id | name | age |\n+-----+------------------+-----+\n| 199 | Gwen Stacy | 18 |\n| 286 | Natalia Romanova | 25 |\n| 417 | Tony Stark | 45 |\n| 430 | Peggy Carter | 91 |\n| 447 | Peter Parker | 18 |\n| 505 | Pepper Potts | 32 |\n+-----+------------------+-----+" user=> (println (str s1)) +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ nil
Note that the width of each column is the width of its widest item (including attribute names). Also, all items have at least one blank space at their left and right hand side. Items that are integer values are right justified, all other items are left justified. The minus (-), vertical bar (|), and plus (+) characters are used to draw the table borders as shown in the examples.
(union relation-a relation-b)Returns a new relation object that contains all the rows in relation-a and relation-b. Mathematically, the union of two relations a and b is defined as:
a ∪ b = { t | t ∈ a ∨ t ∈ b }
For a union operation to be valid, the following conditions must hold:
Example:
user=> (def s1 (relation :students1)) #'user/s1 user=> s1 +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (def s2 (relation :students2)) #'user/s2 user=> s2 +-----+------------------+------+ | id | name | age | +-----+------------------+------+ | 286 | Natalia Romanova | 25 | | 430 | Peggy Carter | 91 | | 505 | Pepper Potts | 32 | | 528 | Steve Rogers | 93 | | 559 | Jane Foster | 29 | | 598 | MaryJane Watson | 18 | | 666 | Damien Thorn | 66 | | 824 | Bruce Banner | 42 | | 993 | Diana Prince | 3217 | +-----+------------------+------+ user=> (union s1 s2) +-----+------------------+------+ | id | name | age | +-----+------------------+------+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | | 528 | Steve Rogers | 93 | | 559 | Jane Foster | 29 | | 598 | MaryJane Watson | 18 | | 666 | Damien Thorn | 66 | | 824 | Bruce Banner | 42 | | 993 | Diana Prince | 3217 | +-----+------------------+------+
(difference relation-a relation-b)Returns a new relation object that contains the rows in relation-a that are not in relation-b. Mathematically, the difference between two relations a and b is defined as:
a – b = { t | t ∈ a ∧ t ∉ b }
For a difference operation to be valid, both relations must be union-compatible (have the exact same attributes and in the same order).
Example:
user=> (def s1 (relation :students1)) #'user/s1 user=> s1 +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (def s2 (relation :students2)) #'user/s2 user=> s2 +-----+------------------+------+ | id | name | age | +-----+------------------+------+ | 286 | Natalia Romanova | 25 | | 430 | Peggy Carter | 91 | | 505 | Pepper Potts | 32 | | 528 | Steve Rogers | 93 | | 559 | Jane Foster | 29 | | 598 | MaryJane Watson | 18 | | 666 | Damien Thorn | 66 | | 824 | Bruce Banner | 42 | | 993 | Diana Prince | 3217 | +-----+------------------+------+ user=> (difference s1 s2) +-----+--------------+-----+ | id | name | age | +-----+--------------+-----+ | 199 | Gwen Stacy | 18 | | 417 | Tony Stark | 45 | | 447 | Peter Parker | 18 | +-----+--------------+-----+
(intersection relation-a relation-b)Returns a new relation object that contains the rows in relation-a that are also in relation-b. Mathematically, the intersection between two relations a and b is defined as:
a ∩ b = { t | t ∈ a ∧ t ∈ b }
For an intersection operation to be valid, both relations must be union-compatible (have the exact same attributes and in the same order).
Example:
user=> (def s1 (relation :students1)) #'user/s1 user=> s1 +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (def s2 (relation :students2)) #'user/s2 user=> s2 +-----+------------------+------+ | id | name | age | +-----+------------------+------+ | 286 | Natalia Romanova | 25 | | 430 | Peggy Carter | 91 | | 505 | Pepper Potts | 32 | | 528 | Steve Rogers | 93 | | 559 | Jane Foster | 29 | | 598 | MaryJane Watson | 18 | | 666 | Damien Thorn | 66 | | 824 | Bruce Banner | 42 | | 993 | Diana Prince | 3217 | +-----+------------------+------+ user=> (intersection s1 s2) +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 286 | Natalia Romanova | 25 | | 430 | Peggy Carter | 91 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+
(product relation-a relation-b)Returns a new relation object that contains the Cartesian product of relation-a times relation-b. Mathematically, the Cartesian product of two relations a and b is defined as:
a × b = { (s, t) | s ∈ a ∧ t ∈ b }
For a Cartesian product operation to be valid, there must be no common attributes between both relations.
Example:
user=> (def s1 (relation :students1)) #'user/s1 user=> s1 +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (def p (relation :pizzas)) #'user/p user=> p +-----------+--------+ | flavor | size | +-----------+--------+ | Hawaiian | Medium | | Pepperoni | Large | | Supreme | Small | +-----------+--------+ user=> (product s1 p) +-----+------------------+-----+-----------+--------+ | id | name | age | flavor | size | +-----+------------------+-----+-----------+--------+ | 199 | Gwen Stacy | 18 | Hawaiian | Medium | | 199 | Gwen Stacy | 18 | Pepperoni | Large | | 199 | Gwen Stacy | 18 | Supreme | Small | | 286 | Natalia Romanova | 25 | Hawaiian | Medium | | 286 | Natalia Romanova | 25 | Pepperoni | Large | | 286 | Natalia Romanova | 25 | Supreme | Small | | 417 | Tony Stark | 45 | Hawaiian | Medium | | 417 | Tony Stark | 45 | Pepperoni | Large | | 417 | Tony Stark | 45 | Supreme | Small | | 430 | Peggy Carter | 91 | Hawaiian | Medium | | 430 | Peggy Carter | 91 | Pepperoni | Large | | 430 | Peggy Carter | 91 | Supreme | Small | | 447 | Peter Parker | 18 | Hawaiian | Medium | | 447 | Peter Parker | 18 | Pepperoni | Large | | 447 | Peter Parker | 18 | Supreme | Small | | 505 | Pepper Potts | 32 | Hawaiian | Medium | | 505 | Pepper Potts | 32 | Pepperoni | Large | | 505 | Pepper Potts | 32 | Supreme | Small | +-----+------------------+-----+-----------+--------+
(project attribute-vector relation)Returns a new relation object based on relation but only with the columns specified in attribute-vector.
Attribute names must be unique keywords in attribute-vector and should be present in relation. The resulting relation should have its columns in the same order as attribute-vector. Also, duplicate rows should automatically be eliminated.
Example:
user=> (def s1 (relation :students1)) #'user/s1 user=> s1 +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (project [:name :id] s1) +------------------+-----+ | name | id | +------------------+-----+ | Gwen Stacy | 199 | | Natalia Romanova | 286 | | Tony Stark | 417 | | Peggy Carter | 430 | | Peter Parker | 447 | | Pepper Potts | 505 | +------------------+-----+
(rename attribute-vector relation)Returns a new relation object which has the same rows as relation but with all its columns renamed using the names contained in attribute-vector.
The attribute names must be unique keywords in attribute-vector. The number of attributes in attribute-vector must be the same as the number of columns in relation.
Example:
user=> (def c (relation :courses)) #'user/c user=> c +--------+----------------------------------+--------+------+ | code | name | time | room | +--------+----------------------------------+--------+------+ | TC2025 | Advanced Programming | Mo1600 | 5204 | | TC2006 | Programming Languages | We1900 | 6307 | | TC2026 | Web Applications Development | Tu1900 | 4207 | | TC3049 | Software Design and Architecture | Th1600 | 4310 | | TC3048 | Compiler Design | Fr1900 | 4202 | +--------+----------------------------------+--------+------+ user=> (rename [:a :b :c :d] c) +--------+----------------------------------+--------+------+ | a | b | c | d | +--------+----------------------------------+--------+------+ | TC2025 | Advanced Programming | Mo1600 | 5204 | | TC2006 | Programming Languages | We1900 | 6307 | | TC2026 | Web Applications Development | Tu1900 | 4207 | | TC3049 | Software Design and Architecture | Th1600 | 4310 | | TC3048 | Compiler Design | Fr1900 | 4202 | +--------+----------------------------------+--------+------+
(select expression relation)This operation has to be implemented as a macro. It returns a new relation object containing all the rows in relation that meet the condition established in expression, which can be any Clojure expression. Any keyword used as part of expression must refer to an attribute in relation.
Examples:
user=> (def s1 (relation :students1)) #'user/s1 user=> s1 +-----+------------------+-----+ | id | name | age | +-----+------------------+-----+ | 199 | Gwen Stacy | 18 | | 286 | Natalia Romanova | 25 | | 417 | Tony Stark | 45 | | 430 | Peggy Carter | 91 | | 447 | Peter Parker | 18 | | 505 | Pepper Potts | 32 | +-----+------------------+-----+ user=> (select (= :age 18) s1) +-----+--------------+-----+ | id | name | age | +-----+--------------+-----+ | 199 | Gwen Stacy | 18 | | 447 | Peter Parker | 18 | +-----+--------------+-----+ user=> (def c (relation :courses)) #'user/c user=> c +--------+----------------------------------+--------+------+ | code | name | time | room | +--------+----------------------------------+--------+------+ | TC2025 | Advanced Programming | Mo1600 | 5204 | | TC2006 | Programming Languages | We1900 | 6307 | | TC2026 | Web Applications Development | Tu1900 | 4207 | | TC3049 | Software Design and Architecture | Th1600 | 4310 | | TC3048 | Compiler Design | Fr1900 | 4202 | +--------+----------------------------------+--------+------+ user=> (select (or (= :code "TC2025") (and (zero? (rem :room 7)) (= "We" (subs :time 0 2)))) c) +--------+-----------------------+--------+------+ | code | name | time | room | +--------+-----------------------+--------+------+ | TC2025 | Advanced Programming | Mo1600 | 5204 | | TC2006 | Programming Languages | We1900 | 6307 | +--------+-----------------------+--------+------+
Deliver a single file called rel_algebra.clj containing your solutions and the unit tests. Please provide the following information:
IMPORTANT: The program source file must include at the top the author’s personal information (name and student id) within comments. For example:
;---------------------------------------------------------- ; Activity: Project: Relational Algebra DSL ; Date: May 4, 2016. ; Author: ; A01166611 Pepper Pots ;----------------------------------------------------------
Due date is Wednesday, May 4, at 4:00 p.m.