When designing an application, you usually start with the business processes involved. Then, you extract the data models involved and map out the respective components/services. It's quite a simplified explanation but, you get what I mean!
As part of this planning, we use conceptual data structures to represent data models. Once we start the implementation, we then translate these data structures into actual database tables. Ever wondered how that's done? Then you're at the right place!
In this post, we'll talk about how to represent some of the common data structures in an SQL database.
What data structures are we working on?
For the purpose of this post, we'll cover the ff. data structures:
- Linked Lists. A list of items where each item can be connected to one or both of the items directly beside them.
- Graphs. Consists of nodes that can be connected to one or more other nodes.
- Trees. Similar to graphs but without any loops.
- Stacks. A list of items and follows the last-in-first-out principle.
- Queues. A list of items and follows the last-in-first-out principle.
Let's simplify first!
We can go ahead and define the SQL representation for the data structures mentioned above, but, we can still simplify this!
In fact, some of the characteristics mentioned above are more tied to how these structures behave and not on how they store data. After realizing this, I further grouped the data structures into 2 categories:
- Linear Structures. These are the data structures that have "edges" or linear connections between their nodes. I placed Linked Lists, Graphs and, Trees under this category.
- Ranked Structures. These are the data structures that are similar to flat lists and where the order of the items is important. I placed Stacks and Queues under this category.
Now that we have these categories, we don't really need to represent each individual data structure in SQL. We just need to represent these 2 categories instead!
Time to represent!
It's time for me to show you how I will represent the above categories in SQL. Let's go!
Linear Structures
In terms of representing linear structures in SQL, we just need to take note of 2 things:
- Each node can have 1 or more edges
- Each edge can only go in 1 direction (from Node A to Node B). If we want to represent a reverse edge, we should create a different record for it.
Here's the ERD for Linear Structures:
In the above diagram, we used a many-to-many pattern where we defined 2 tables:
- Node. This represents each node in the linear structure.
- Edge. This represents each edge. For the direction, it's always represented as from NodeA to NodeB.
Additionally, each node can have 0 or more edges.
Ranked Structures
In terms of representing ranked structures, we just need to take note of 2 things:
- We need to represent lists
- Each list should contain one or more items with reference to an item's rank
Here's the ERD for Ranked Structures:
In the above diagram, we defined 3 tables:
- Item. This represents each item that can be part of a list.
- ItemList. This represents a list.
- ItemRank. This maps out which items belong to which list. Additionally, each mapping will also indicate the rank of an item in a particular list.
We made this diagram more flexible so that we can put a single item in multiple lists. Additionally, each ItemRank record has 2 primary keys: ItemListId and Rank. This means that in each list, we don't want items to share a particular rank.
Also, there are other approaches to doing this. If you happen to know one, I'd love to hear from you so, share your thoughts in the comments below!
Summary
In this post, we went through how to represent some of the common data structures in an SQL database using the ff. steps:
- What? Identify the characteristics of the data structure.
- Simplify! Shift your focus to how the data structure stores data.
- Represent! Use the simplified information to create a set of SQL tables to represent the data structure.
I know there are tons of other ways to represent these common data structures in SQL. If you know one, feel free to share them in the comments!
Hey, you! Follow me on Twitter!
