Project Milestone 2: Adding a Spatial Datatype

Okay, code time! In this assignment we shall modify redbase to accept a simple spatial datatype - a rectangle. To get an idea of what spatial data is and where is it used, please read through the tutorial if you haven’t already.

At a high level, the following steps take place after the redbase executable is run:

  1. redbase.cc shows a prompt and takes in a string as an input from the user.
  2. The string goes through a lexical analysis (also called ‘lexing’ or ‘tokenization’) phase that scans and generates a sequence of ‘tokens’. The types of tokens are defined in the parser specification in parse.y. Note that these files do not contain the C code for lexing and parsing. Since several software systems use such lexing and parsing stages, tools like GNU Flex and Bison are used to generate the actual code from the language specifications present in the scan.l and parse.y files. You can find the actual code in scan.cpp and parse.cpp files, but do not modify these files. They are automatically generated by Flex and Bison, and will be overwritten on each build.
  3. The sequence of tokens generated in the lexing stage is input into a parser, that generates a ‘query tree’. A query tree is composed of different types of ‘nodes’ defined in the nodes.cc file. Each type of SQL statement is mapped to a distinct type of node in the query tree.
  4. The query tree is then traversed and each node is then ‘interpreted’ by the interp function in interp.cc and relevant methods of the Storage Management/Indexing/Record Management layers are called using objects of their respective Manager classes.

Task Assigned

You need to add a simple spatial datatype ‘MBR’(a Minimum Bounding Rectangle) to the system and modify the RQL to accept the new type. An MBR should be a set of 4 integer values representing [top_left_x, top_left_y, bottom_right_x, bottom_right_y].

You can start with adding a datatype to redbase.h, then modify the lexer and parser specifications to recognise this new datatype by adding a new type of token (expected lines to change in scan.l = ~2, in parse.y = ~10). You will then need to work your way downwards through the system and make sure that data of the new type can be inserted and retrieved using the RQL INSERT and SELECT statements. A set of sample queries is shown below:

CREATE TABLE DATA (id i, location m); // Note the new datatype MBR denoted by 'm'
INSERT INTO DATA VALUES (1, [1, 2, 3, 4]); // The 4 input values grouped in [] represent a single MBR
SELECT * FROM DATA;

You can find additional help in in the Parser.HowTo file given in the source directory. However, please note that the given list of files is not exhaustive, and there may be additional files you may have to modify to make the system work. Please use piazza for any questions/discussions.

Deliverables

Please submit a snapshot of your code with a README file containing the instructions to run your code, packaged into a single .tar.gz file with the name firstname_lastname.tar.gz. (30 points)

Due date: 31st October, 11:59 pm

How to submit: The submissions will be through iLearn.
Please upload the report on iLearn > CS 236 > Assignments > Project milestone 2.