Design SQL

Medium

Asked by:

2.5K views

Topics:

Database Problems

You are asked to design a simplified SQL engine. The engine should be able to create tables, insert rows, delete rows, and select rows based on simple conditions.

Implement the SQL class:

SQL(): Initializes the SQL engine. All tables are initially empty.
void createTable(string tableName, vector<string> columns): Creates a new table named tableName with the given columns. All columns store integer values.
void insertRow(string tableName, vector<string> row): Inserts a new row into the specified tableName. The values are provided as a vector of strings. The number of values will match the number of columns, and the values are valid integer strings.
void deleteRows(string tableName, string whereColumn, string whereValue): Deletes all rows from tableName where the value in the whereColumn is equal to whereValue. You can assume whereColumn exists and whereValue is a valid integer string.
vector<vector<string>> selectRows(string tableName, vector<string> columns, string whereColumn, string whereValue): Selects and returns a list of rows from tableName. Only rows where the value in whereColumn is equal to whereValue should be included. The returned rows should only contain the columns specified in the columns vector, in the same order.

Example 1:

SQL sql = new SQL();
sql.createTable("Employees", {"employee_id", "name", "salary"});
sql.insertRow("Employees", {"1", "Alice", "100000"});
sql.insertRow("Employees", {"2", "Bob", "90000"});
sql.insertRow("Employees", {"3", "Charlie", "80000"});
sql.deleteRows("Employees", "employee_id", "3");
sql.selectRows("Employees", {"name", "salary"}, "salary", "100000"); 
// returns [["Alice", "100000"]]

sql.createTable("Projects", {"project_id", "project_name"});
sql.insertRow("Projects", {"101", "Alpha"});
sql.insertRow("Projects", {"102", "Beta"});
sql.deleteRows("Projects", "project_id", "101");
sql.selectRows("Projects", {"project_name"}, "project_name", "Beta"); 
// returns [["Beta"]]

Constraints:

The number of tables will be between 1 and 100.
The number of columns for any table will be between 1 and 100.
The total number of rows across all tables will not exceed 1000.
All string values for names and columns will be composed of lowercase English letters.
The integer values will be within a range that can be represented by a standard integer type.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data types will the columns in the tables be limited to (e.g., INTEGER, VARCHAR, BOOLEAN)? And what are the size limits for VARCHAR columns?
Can you provide more details on the syntax supported for the WHERE clause? Specifically, what comparison operators (e.g., =, >, <, LIKE) and logical operators (e.g., AND, OR, NOT) are supported?
How should the system handle errors such as invalid SQL syntax, non-existent tables or columns, or data type mismatches? Should I return an error code, throw an exception, or simply return an empty list?
Are there any constraints on the size or number of tables, or the number of rows in each table?
In the SELECT statement, do I need to support aggregate functions (e.g., COUNT, SUM, AVG, MIN, MAX) or GROUP BY clauses?

Brute Force Solution

Approach

The brute force method for designing SQL involves exploring every conceivable table structure and query construction. We essentially try out every single possible database design, evaluate it, and compare it against our requirements. It's like testing every lock to find the right key.

Here's how the algorithm would work step-by-step:

First, consider all possible tables you could create. This means thinking about every combination of columns and data types each table could have.
Next, for each possible table design, think about how the tables relate to each other. This includes all the different ways you can link the tables using keys.
For each combination of tables and relationships, imagine writing every possible query you could use to get the data you need.
Run each of these queries against the possible table setup.
Evaluate the results. See if they give you the information you want and check if the speed is acceptable.
Keep track of which database design and query gives the best result in the fastest time.
Finally, choose the best overall database design and query after evaluating all possibilities.

Code Implementation

class SQL:
    def __init__(self, names, columns):
        # Maps each table name to its column count, rows and next row id.
        self.column_counts = dict(zip(names, columns))
        self.rows = {name: {} for name in names}
        self.next_row_ids = {name: 1 for name in names}

    def insertRow(self, name, row):
        row_id = self.next_row_ids[name]
        self.rows[name][row_id] = row
        self.next_row_ids[name] = row_id + 1

    def deleteRow(self, name, rowId):
        # Row ids are never reused, so removing the entry is enough.
        self.rows[name].pop(rowId, None)

    def selectCell(self, name, rowId, columnId):
        return self.rows[name][rowId][columnId - 1]

Big(O) Analysis

Time Complexity

O(Exponential) – Let 'c' represent the number of possible columns, 't' the number of potential tables, 'r' different relationship configurations between tables, and 'q' the number of possible queries. The brute force method explores all combinations, so for each table structure (O(c^t)), it considers all relationships (O(r)), and then all possible queries (O(q)). Evaluating each query also has its own cost. Since we are exploring all possible designs, the number of designs grows exponentially with the number of options considered at each level. The total complexity is then approximated as c^t * r * q, which is an exponential time complexity. Specifically, it is O(c^t * r * q) which translates to O(Exponential).

Space Complexity

O(N^K) – The brute force approach necessitates storing a wide range of possible table designs, relationships, and queries. The number of possible table structures could grow exponentially with the number of columns or the complexity of data types, let's represent that by 'N'. Furthermore, storing various combinations of table relationships and queries results in substantial auxiliary space usage that grows exponentially based on the complexity of table schemas, represented by 'K'. Therefore, the auxiliary space complexity is approximately O(N^K) where N represents the possible table structures and K the combinations of schemas, relationships, and queries.

Optimal Solution

Approach

Designing a database effectively involves understanding the relationships between different pieces of information. The optimal approach centers around breaking down complex data into smaller, manageable parts and defining clear connections between them.

Here's how the algorithm would work step-by-step:

First, identify the key pieces of information you need to store, like customers, orders, and products.
Next, create separate tables for each of these pieces of information, ensuring each table has a unique identifier for each item (like a customer ID or order number).
Then, determine how these tables relate to each other. For example, a customer can have multiple orders, so you need a way to connect the customer table to the orders table.
Use special fields (foreign keys) in one table to point to the unique identifier in another table, creating a link between related information.
Carefully consider the type of information each field will hold (like numbers, text, or dates) and choose the most appropriate data type to ensure accuracy and efficiency.
Finally, organize the tables and relationships to minimize redundancy and ensure that information can be easily retrieved and updated.

Code Implementation

class SQLDesign:
    def __init__(self):
        pass

    def design_database(self):
        # Define tables as dictionaries.
        tables = {}

        # Create the customers table.
        tables['customers'] = {
            'customer_id': 'INT PRIMARY KEY',
            'customer_name': 'VARCHAR(255)',
            'customer_email': 'VARCHAR(255)'
        }

        # Create the orders table.
        tables['orders'] = {
            'order_id': 'INT PRIMARY KEY',
            'customer_id': 'INT',
            'order_date': 'DATE',
            'total_amount': 'DECIMAL(10, 2)'
        }

        # Establish foreign key relationship.
        # Orders table relates to customers table using customer_id.
        tables['orders']['customer_id'] = 'INT FOREIGN KEY REFERENCES customers(customer_id)'

        tables['products'] = {
            'product_id': 'INT PRIMARY KEY',
            'product_name': 'VARCHAR(255)',
            'product_description': 'TEXT',
            'product_price': 'DECIMAL(10, 2)'
        }

        tables['order_items'] = {
            'order_item_id': 'INT PRIMARY KEY',
            'order_id': 'INT',
            'product_id': 'INT',
            'quantity': 'INT',
            'item_price': 'DECIMAL(10, 2)'
        }

        # Establish foreign key relationships.
        # Order items relate to orders and products tables.
        tables['order_items']['order_id'] = 'INT FOREIGN KEY REFERENCES orders(order_id)'

        # Products need to be linked for item details
        tables['order_items']['product_id'] = 'INT FOREIGN KEY REFERENCES products(product_id)'

        # Returns the data model as a dictionary.
        return tables

Big(O) Analysis

Time Complexity

N/A – The provided solution describes a database design process and does not involve an algorithm with a specific runtime complexity. The steps outline data modeling principles such as identifying entities, defining relationships using primary and foreign keys, and normalizing data. These are design considerations rather than computational steps whose performance can be analyzed with Big O notation.

Space Complexity

O(1) – The database design outlined focuses on organizing data into tables and establishing relationships using foreign keys. The space complexity primarily relates to the database's storage requirements which are proportional to the size of the data itself, and thus not auxiliary space. The process of designing the database, identifying entities, relationships, and data types does not introduce auxiliary data structures that scale with the input size; it's a design process that happens before the database is populated. Therefore, the auxiliary space complexity of the design process itself is constant, O(1).

Edge Cases

Case	How to Handle
CREATE TABLE with duplicate column names	Reject the CREATE TABLE statement if duplicate column names are detected.
INSERT INTO a table that doesn't exist	Return an error indicating the table does not exist.
INSERT INTO with incorrect number of values (too few or too many)	Return an error if the number of provided values doesn't match the table schema.
SELECT * FROM non-existent table	Return an error indicating that the table does not exist.
WHERE clause with invalid column name	Return an error if the column specified in the WHERE clause does not exist in the table.
WHERE clause with mismatched data types for comparison	Return an error if data types used in the comparison within the WHERE clause are incompatible.
Large number of rows in a table causing memory issues	Consider implementing pagination or limiting the size of results returned by SELECT.
Complex WHERE clauses with nested AND/OR operators and precedence	Implement a proper parser to handle operator precedence and ensure correct evaluation of the WHERE clause conditions.

CREATE TABLE with duplicate column names

How to Handle:

Reject the CREATE TABLE statement if duplicate column names are detected.

INSERT INTO a table that doesn't exist

How to Handle:

Return an error indicating the table does not exist.

INSERT INTO with incorrect number of values (too few or too many)

How to Handle:

Return an error if the number of provided values doesn't match the table schema.

SELECT * FROM non-existent table

How to Handle:

Return an error indicating that the table does not exist.

WHERE clause with invalid column name

How to Handle:

Return an error if the column specified in the WHERE clause does not exist in the table.

WHERE clause with mismatched data types for comparison

How to Handle:

Return an error if data types used in the comparison within the WHERE clause are incompatible.

Large number of rows in a table causing memory issues

How to Handle:

Consider implementing pagination or limiting the size of results returned by SELECT.

Complex WHERE clauses with nested AND/OR operators and precedence

How to Handle:

Implement a proper parser to handle operator precedence and ensure correct evaluation of the WHERE clause conditions.