# The Translation from SQL to Relational Algebra Open Access

## Li, Yicong (Spring 2018)

Permanent URL: https://etd.library.emory.edu/concern/etds/vx021f13x?locale=en
Published

## Abstract

SQL (Structural Query Language) and Relational Algebra are two important languages to manipulate relational database. SQL is an international standard language used to express queries on data stored in a database. Relational Algebra is a Mathematical language with operations on sets. SQL queries are first translated to an equivalent expression in Relational Algebra in query processing. The thesis explores the translation from SQL to Relational Algebra to gain a deeper understanding in database systems. The thesis begins with an introduction to the problem (including motivation to working on the translation), the related background knowledge to handle the translation, and follows with the project design. It then discusses the evaluation of the result, reflects on my learning experience from the project, and makes suggestion about further improvement.

CHAPTER 1 – Introduction ........................................................................................................... 1

1.1 Motivation

........................................................................................................... 1

1.2 Problem Description

........................................................................................................... 2

1.3 Related Work

........................................................................................................... 3

CHAPTER 2 –Background

........................................................................................................... 5

2.1 Relational Database

........................................................................................................... 5

2.2 Relational Algebra

........................................................................................................... 6

2.3SQL

........................................................................................................... 8

2.4 Parsing

......................................................................................................... 10

2.4.1 Lexical Analysis

......................................................................................................... 10

2.4.2 Regular Expression

......................................................................................................... 11

CHAPTER 3 – Project Description

......................................................................................................... 14

3.1 Introduction

......................................................................................................... 14

3.2 The Lexical Analyzer of the Project

......................................................................................................... 14

3.3 Parsing the SELECT Clause

......................................................................................................... 16

3.4 Parsing the FROM Clause

......................................................................................................... 18

3.5 Checking and Filling the Attribute List

......................................................................................................... 20

3.6 Parsing the WHERE Clause

......................................................................................................... 20

3.7 Converting to Relational Algebra

......................................................................................................... 29

CHAPTER 4 – Test and Evaluation

......................................................................................................... 31

4.1 Sample Outputs

......................................................................................................... 31

4.2 Limitations

......................................................................................................... 36

CHAPTER 5 – Project Evaluation and Future Work

......................................................................................................... 37

5.1 Project Goal and Assessment ........................................................................................................ 37

5.2 Improvement

........................................................................................................ 38