Relational Algebra Implementation

In asssignments 1 and 2 you implemented Relational Algebra. In this assignment, you will use Relational Algebra to implement some queries.

As in the earlier assignments, you will start with code that I provide (in this archive), which provides unit tests. You will add your code from assignment 2, and then implement queries using the functions declared in RelationalAlgebra.h.

What's in the archive

Tests

test.cpp contains eight functions that execute relational algebra queries, and then check the results, test_q0 through test_q7. test_q0 is an example, discussed below. You need to fill in implementations for test_q1 through test_q7.

These tests depend on the following tables:
user( user_id primary key, username, birth_date) message( message_id primary key, send_date, text) routing( from_user_id references user, to_user_id references user, message_id, primary key(from_user_id, to_user_id, message_id)

• This database tracks messages sent among users. A message is sent from one user to one or more other users.
• The user table contains a set of users. user_id and username are unique. Each user has a birth_date.
• The message table records the messages: the text of the message, and it's send_date. message_id is the primary key.
• The routing table provides information on the sender and recipient of each message: from_user_id and to_user_id. If a message m, from user u has three recipients, a, b, c, then the routing table has three rows, one for each recipient:
  (u, a, m) (u, b, m) (u, c, m)

These tables are populated by the files in the db directory: user.csv, routing.csv, message.csv.

Your task is to fill in the query implementations, and the results are tested for correctness. Predicates that you are likely to need are already present in test.cpp. You are free to use them or write your own.

Your code should look something like test_q0(), which is provided as an example.
static void test_q0() { Table *q0 = diff( project(user, ColumnNames{"username"}), project( join( rename( select(routing, q0_predicate), NameMap({{"from_user_id", "user_id"}})), user), ColumnNames{"username"})); // print_table("q0", q0); Table *control0 = Database::new_table("control0", ColumnNames{"username"}); add(control0, {"Intaglio"}); add(control0, {"Unguiferous"}); assert(table_eq(control0, q0)); }

The query implemented here is: What are the names of users who have not sent a message to themselves? The implementation finds all users, and then removes those who have sent messages to themselves. The implementation works as follows, proceeding from the most nested part outward:

• The select identifies routing rows in with from_user_id = to_user_id, (the condition is tested by q0_predicate).
• from_user_id is renamed to user_id, to prepare for the join. The resulting table has columns (user_id, to_user_id, message_id).
• The (user_id, to_user_id, message_id) table is joined with user, joining on (user_id). The output from the join describes users who have sent themselves email.
• The join feeds into a project on (username), to get (just) the names of users who have sent email to themselves.
• The first project gives us the usernames of all users.
• We now have usernames of all users, and usernames of users who have sent messages to themselves. Subtracting the latter from the former using diff yields the usernames of users who have not sent messages to themselves.

Debugging

Note that test.cpp has a print_table function, which can be useful during debugging. There is a commented-out call to print_table in test_q0, so you can see how to use the function. This could be useful in checking intermediate relational algebra expressions, e.g.
print_table("After rename", rename( select(routing, q0_predicate), NameMap({{"from_user_id", "user_id"}})) );

Utilities

Makefile

Building the code

• Row.h
• Row.cpp
• Table.h
• Table.cpp
• RelationalAlgebra.h
• RelationalAlgebra.cpp

Run make: jao@mintyzack ~/teaching/tufts/115/a4/a4 $ make g++ -std=c++11 -Wall -Wno-unused-function -c ColumnNames.cpp -o ColumnNames.o g++ -std=c++11 -Wall -Wno-unused-function -c Database.cpp -o Database.o g++ -std=c++11 -Wall -Wno-unused-function -c RelationalAlgebra.cpp -o RelationalAlgebra.o g++ -std=c++11 -Wall -Wno-unused-function -c Row.cpp -o Row.o g++ -std=c++11 -Wall -Wno-unused-function -c RowCompare.cpp -o RowCompare.o g++ -std=c++11 -Wall -Wno-unused-function -c Table.cpp -o Table.o g++ -std=c++11 -Wall -Wno-unused-function -c main.cpp -o main.o g++ -std=c++11 -Wall -Wno-unused-function -c test.cpp -o test.o g++ -std=c++11 -Wall -Wno-unused-function -c unittest.cpp -o unittest.o g++ -std=c++11 -Wall -Wno-unused-function ColumnNames.o Database.o RelationalAlgebra.o Row.o RowCompare.o Table.o main.o test.o unittest.o -o a4

Running the code

test_q0 passes because test.cpp implements the query correctly. The others fail because IMPLEMENT_ME() returns an empty table which, in each case, is the wrong answer. When you successfully implement queries 1 through 7 you will see all tests pass.

As usual, use valgrind frequently to make sure that you aren't running into memory corruption issues, or introducing memory leaks. (Assuming your Assignment 2 code had no leaks, you should be able to avoid memory leaks easily. You should not have to allocate or free any memory to complete this assignment.)