O'Ryan Hedrick
That Bald Guy with a Server

That Bald Guy with a Server

The Beginning of a Database Engine in F#

O'Ryan Hedrick's photo
O'Ryan Hedrick
·Aug 7, 2022·

3 min read

Why?

I enjoy reading about data structures and I've caught a mild fascination with F#. Now I'm going to try and put together a tidy little database engine. F# has a focus on breaking things down into the smallest functions and chaining them together, which shares something with idiomatic PowerShell. It's another .NET language, which is convenient given I'm already a little familiar with .NET from PowerShell.

Requirements

  • Entire database loaded into memory
  • Serializable to XML or JSON files for persistance/backups
  • Does not rely on indices to determine adjacency
  • Built as a library so that I could build a CLI or a web server for it

I don't expect this to ever be a production database. It's just a learning project, so I don't expect to put enough data in it to worry about RAM. I'm not planning on storing media in it, and the number of nodes and edges isn't going to be very high. I do still want to be able to export the database to XML or JSON so that the database can be stopped and started without losing data, and can be initially populated from a file to make testing easier.

The adjacency thing is about making use of the graph database structure. If we don't need to search the entire set of nodes for indices everytime we follow an edge it'll go faster and mitigate the friend of a friend problem. Records will be nodes of the graph, relationships are edges of the graph. Traversing from one node to another will follow the edge and shouldn't require reading the entirety of the node or edge tables to find the next node or edge.

Development setup

  • VSCode. It conveniently handles a wide variety of languages, from PowerShell to F# to Latex.
  • Dotnet. I enjoy the fact that if I learn something in dotnet, I could potentially use it at work with PowerShell.
  • A somewhat broken HP Spectre. I got it from my bother-in-law because it didn't start. Turns out it works without the battery. Someday I'll try to fix it for real, but for now it's a decent laptop I got for free. The near 4k resolution can be a pain though; occasionally a program doesn't know how to handle it and everything is very tiny.

Initial Architecture

I've peeked at what little example code I can find for graphs in F#, and it looks like we start with a structure for nodes, a struture for edges, and then build a structure that holds one node and all edges that start from that node. This feels right, so I'll try and make that. Then I'll figure out how to tie it all together and do queries.

 
Share this