1.
This report presents the design and implementation of a Mini SQL Engine — a software system that
simulates the core functionalities of a relational database management system (RDBMS) using
fundamental data structures. The engine enables users to execute SQL-like queries, including
SELECT with WHERE clause filtering, on structured datasets stored in memory.
The project is architected as a multi-stage processing pipeline encompassing tokenization, parsing,
execution, and result formatting. Particular emphasis is placed on visualizing each processing stage
to demystify internal database operations. The system further supports dynamic data import via
CSV and JSON formats, broadening its practical applicability.
Through this project, foundational data structures — arrays, stacks, and linked lists — are applied in
a real-world context, providing students with actionable insight into how industrial-grade database
systems operate at their core.
2. Introduction
Database management systems (DBMS) are the backbone of virtually every modern application,
yet their internal mechanics remain opaque to most learners. Concepts such as query parsing, row
scanning, and result projection are often taught in abstraction, without a tangible demonstration of
how they work step by step.
The Mini SQL Engine addresses this gap by providing an interactive, transparent simulation of
database query processing. Designed as an educational tool, it allows students to observe the
journey of a SQL query from plain text through tokenization, parsing, and execution, down to the
final result set.
By grounding this simulation in core data structures — arrays for token management, stacks for
parse state tracking, and linked lists for dynamic row storage — the project reinforces the
connection between theoretical computer science and practical systems engineering.
Project Title Mini SQL Engine
Domain Data Structures & Database Systems
Technologies Programming Language of Choice (C / Java / Python / JavaScript)
Team Size [Number of Students]
Duration [Project Duration]
Complexity O(n) — Linear time execution
3. Objectives
The following primary objectives guided the development of the Mini SQL Engine:
• Implement a functional, simplified SQL query execution engine capable of processing
SELECT and WHERE statements.
• Apply and demonstrate the practical utility of core data structures — arrays, stacks, and
linked lists — within a real-world system.
• Visualize query execution stage by stage, from tokenization through result generation, to
enhance conceptual understanding.
• Support dynamic data ingestion through CSV and JSON file imports, enabling flexible and
realistic dataset management.
• Provide an error-resilient system that detects syntactically invalid queries and produces
meaningful diagnostic feedback.
• Develop the project as a reusable educational tool that aids instruction in both data
structures and database internals.
4. Scope & Limitations
4.1 Scope
The Mini SQL Engine is scoped as an educational demonstration tool and is suitable for:
• Classroom instruction on data structures and their real-world applications.
• Self-directed learning for students seeking to understand DBMS internals.
• Academic projects and demonstrations in undergraduate CS/IT programs.
4.2 Limitations
The current version intentionally constrains its functionality to maintain simplicity and focus on
educational goals:
• Supports only SELECT and WHERE SQL constructs; INSERT, UPDATE, and DELETE are
not implemented.
• Does not support JOIN operations across multiple tables.
• Row retrieval is performed via linear search (O(n)); no index-based optimization is
implemented.
• Data is stored in-memory; no persistent on-disk storage is provided.
5. System Architecture
The Mini SQL Engine is designed around a pipeline-based architecture, where each stage performs
a discrete transformation on the input query before passing it to the next. This design promotes
separation of concerns and makes each stage independently testable and visualizable.
1 2 3 4 5
Query Input Tokenizer Parser Execution Engine Result Output
Each stage is described below:
• Query Input: The user enters a raw SQL-like string through the interface.
• Tokenizer (Lexer): The raw string is decomposed into discrete tokens — keywords,
identifiers, operators, and literals.
• Parser: Tokens are validated against expected SQL grammar and assembled into a
structured query representation.
• Execution Engine: The engine traverses the target table, applies WHERE conditions row by
row, and collects matching records.
• Result Output: Matching rows are projected onto the requested columns and rendered in a
formatted table.
6. Data Structures Used
Three foundational data structures underpin the Mini SQL Engine. Each is applied in a context that
closely mirrors its usage in production DBMS implementations.
6.1 Arrays
Arrays provide O(1) indexed access and are used throughout the engine for:
• Token storage: The lexer deposits all tokens into an array for sequential access by the
parser.
• Table management: Column definitions and row data for in-memory tables are stored as
arrays.
• Result accumulation: Rows matching the WHERE condition are appended to a result array.
6.2 Linked Lists
Singly linked lists enable dynamic, non-contiguous memory allocation and are used for:
• Row representation: Each table row is stored as a node in a linked list, allowing the table to
grow without pre-allocation.
• Flexible data insertion: New records from CSV/JSON imports are appended as linked list
nodes at O(1) cost.
6.3 Stack
A stack (LIFO structure) is used for:
• Parse state tracking: The parser uses a stack to validate nested query constructs and track
processing stages.
• Execution visualization: The stack state is displayed to users during step-by-step execution
mode, illustrating how parsing progresses.
7. Key Features
Feature Description Data Structure Used
SQL Execution Executes SELECT * / SELECT column with Arrays, Linked List
optional WHERE clause
Multi-Table Support Predefined tables: Students, Products, Arrays
Employees; user-switchable
CSV / JSON Import Dynamically loads external datasets and creates Linked List
in-memory tables
WHERE Filtering Supports =, >, <, >=, <=, != operators on any Arrays
column
Column Projection Returns only requested columns, reducing output Arrays
Feature Description Data Structure Used
verbosity
Execution Displays tokenization, parsing, and execution Stack, Arrays
Visualization stages in real time
Row Scan Highlights each row as it is scanned and Linked List
Simulation evaluated
Step-by-Step Mode Allows debugger-style execution with pause Stack
between each row scan
Performance Reports rows scanned, rows matched, execution Arrays
Metrics time, and complexity
Error Handling Detects malformed queries and provides Arrays
descriptive error messages
8. System Working
This section walks through the end-to-end execution of a representative query to illustrate the
system's behavior at each pipeline stage.
8.1 Sample Query
SELECT name, age FROM students WHERE age > 20
8.2 Stage-by-Stage Walkthrough
Stage 1 — Tokenization
The lexer scans the raw query string character by character, grouping characters into meaningful
tokens:
Token[0] = KEYWORD : SELECT
Token[1] = IDENTIFIER: name
Token[2] = COMMA : ,
Token[3] = IDENTIFIER: age
Token[4] = KEYWORD : FROM
Token[5] = IDENTIFIER: students
Token[6] = KEYWORD : WHERE
Token[7] = IDENTIFIER: age
Token[8] = OPERATOR : >
Token[9] = LITERAL : 20
Stage 2 — Parsing
The parser validates the token sequence against the expected SQL grammar and extracts the
query components into a structured representation:
• Action: SELECT
• Columns: ["name", "age"]
• Table: "students"
• Condition: age > 20
Stage 3 — Execution
The execution engine traverses the linked list of rows in the students table. For each row, the
WHERE condition (age > 20) is evaluated. Matching rows are projected onto the requested
columns and appended to the result set.
Stage 4 — Result Output
The result set is rendered as a formatted table displaying only the name and age columns for all
rows where the age condition was satisfied.
9. Algorithm
The following algorithm describes the complete query execution flow:
ALGORITHM: ExecuteQuery(queryString)
1. Read queryString from user input
2. tokens ← Tokenize(queryString)
3. queryObject ← Parse(tokens)
4. IF queryObject is invalid:
Display error message → STOP
5. table ← GetTable([Link])
6. results ← empty array
7. current ← [Link] // Start of linked list
8. WHILE current != NULL:
IF WhereCondition(current, [Link]):
Append Project(current, [Link]) to results
current ← [Link]
9. Display results as formatted table
10. Report: rows scanned, rows matched, execution time
10. Time & Space Complexity
Operation Time Complexity Space Complexity
Tokenization O(q) — q = query length O(t) — t = token count
Parsing O(t) — t = token count O(1)
Row Scanning (WHERE) O(n) — n = row count O(k) — k = matched rows
Column Projection O(k × c) — c = columns O(k × c)
Overall Execution O(n) O(n) worst case
11. Advantages
• Educational transparency: every stage of query processing is explicitly visible, making
abstract DBMS concepts tangible.
• Practical data structure application: arrays, stacks, and linked lists are used in roles that
mirror their use in production systems.
• Dynamic data support: CSV and JSON import allows the engine to operate on real-world
datasets, not just hardcoded test data.
• Interactivity: step-by-step execution mode enables learners to pause, inspect, and reason
about each processing stage.
• Error resilience: meaningful diagnostic messages guide users toward correct query syntax.
• Lightweight: the engine requires no external database server, making it immediately
accessible in any development environment.
12. Limitations
• No DML support: INSERT, UPDATE, and DELETE operations are not implemented in the
current version.
• No JOIN support: multi-table queries requiring JOIN semantics are outside the current
scope.
• Linear search only: all row retrieval uses O(n) linear traversal; no hash indexes or B-tree
structures are implemented.
• No persistence: all data is stored in-memory and is lost when the session ends.
• Limited SQL grammar: advanced SQL features such as aggregate functions (COUNT,
SUM), GROUP BY, and ORDER BY are not supported.
13. Future Enhancements
The following enhancements are planned for subsequent versions of the Mini SQL Engine:
1. Implement DML operations — INSERT, UPDATE, and DELETE — to complete basic CRUD
functionality.
2. Introduce hash-based indexing on primary key columns to reduce lookup complexity from
O(n) to O(1) average case.
3. Add support for JOIN operations (INNER, LEFT, RIGHT) to enable multi-table queries.
4. Implement aggregate functions: COUNT, SUM, AVG, MIN, MAX, along with GROUP BY
and HAVING clauses.
5. Provide persistent file-based storage, allowing tables to be saved and reloaded across
sessions.
6. Develop an enhanced GUI with a query editor, syntax highlighting, and animated data
structure visualizations.
7. Add support for ORDER BY, DISTINCT, and LIMIT clauses to improve result control.
14. Conclusion
The Mini SQL Engine successfully demonstrates how a relational database management system
processes SQL queries internally, using only foundational data structures. By faithfully simulating
the tokenization, parsing, and execution pipeline, the project transforms abstract computer science
concepts into observable, interactive behavior.
The application of arrays for token and result management, linked lists for dynamic row storage,
and stacks for parse state visualization reflects the genuine design choices made in production
DBMS implementations — scaled appropriately for an educational context.
The project achieves its dual mandate: functional correctness in executing SQL-like queries, and
pedagogical value in making those mechanics visible. It serves as a solid foundation for future
enhancements, including indexing, persistence, and advanced SQL features, and stands as a
practical demonstration of the power of data structures in real-world software systems.
15. References
The following resources were consulted in the design, development, and documentation of this
project:
Textbooks
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3rd ed.). MIT Press.
• Ramakrishnan, R., & Gehrke, J. (2002). Database Management Systems (3rd ed.).
McGraw-Hill.
• Weiss, M. A. (2014). Data Structures and Algorithm Analysis in C++ (4th ed.). Pearson.
Online Resources
• W3Schools SQL Tutorial — [Link]
• GeeksforGeeks — Data Structures — [Link]
• SQLite Internals Documentation — [Link]
• MDN Web Docs — JavaScript Reference — [Link]
Academic References
• Selinger, P. G., et al. (1979). Access Path Selection in a Relational Database Management
System. ACM SIGMOD.
• Codd, E. F. (1970). A Relational Model of Data for Large Shared Data Banks.
Communications of the ACM, 13(6), 377–387.