Fractals in FaunaDB

Refurbishing an old query language exercise

I’ve been working a lot with FaunaDB lately. I recently crossed a point where I was using it about as much as SQL-like languages for all other relational databases. FaunaDB is new enough that tutorials have been done to death (not counting tutorials that are just repeats of the TODO-list app). If you’re like me, these simple toy queries might not get you very far.

For this FaunaDB tutorial, I was inspired by Michael Malis’ presentation on SQL Fractals. Having previously used a variant of this to get better at BigQuery, I figured it would be interesting to try this out with this newfangled NoSQL database (I had also explored this earlier in Google BigQuery, which lacked the option of the RECURSIVE clause seen in many other query languages). While it’s true that there are plenty of libraries and tools one can use to speed up the execution of your serverless queries, not many can compensate for optimizing your actual queries.

FaunaDB Explained

FaunaDB is a cloud database that was created by a bunch of ex-Twitter engineers in an attempt to merge some of the better features of SQL and NoSQL databases. It’s a serverless, pay-as-you-go cloud DB designed with JAMstack (that’s JavaScript, APIs, and Markup) web apps in mind. You can manage your data using either the web interface or the command line. It’s fast and auto-scales in the cloud, and it’s one of the first commercial databases to use the Calvin model for ACID Compliance in partitioned database systems. More importantly, it’s able to handle the types of data relations one would find in a graph, temporal, relational, or document database (though you might not want to use it for storing bytestrings of images or videos just yet).

As of December, you can also test your FaunaDB applications locally using their official Docker container

The Fractals

Michael Malis’ SQL fractals made use of an SQL technique called recursive CTEs. Recursive CTEs provided a way to express iteration in the queries. With some work, he was able map fractals of two types into SQL queries:

  • Escape-time fractals: A class of fractals based on repeatedly evaluating a formula at every point in a grid. In the original SQL formulation, use one recursive CTE to iterate through every point in a grid. I then use a second recursive CTE to repeatedly evaluate a function over each point to test whether or not the point is part of the fractal.
  • Self-similar fractals: A class of fractals that can be described by what’s known as an ”L-system”:. An L-system encodes a fractal as an initial string and rules for modifying that string. It is then possible to decode the fractal from the string. I wrote a SQL query that takes an arbitrary L-system. It runs a few iterations of the L-system and then maps the resulting string back to the fractal. Mapping the L-system to the final fractal is a bit tedious, but not too hard.

Whether we can map fractals to a NoSQL database like FaunaDB ultimately depends on finding a replacement for this recursion functionality.

Local Setup (optional)

Run the following commands in your terminal to get an instance of FaunaDB running (this requires having Docker installed):

docker pull fauna/faunadb
docker run --name faunadb -p 8443:8443 -p 8084:8084 fauna/faunadb

We expose port 8443 for standard database interactions and 8084 for calls to the GraphQL API. As with other database images, you can use other Docker container options for data persistence and such. See the FaunaDB documentation for alternatives.

Sierpinski’s Triangle.

Michael Malis’ original version

The Sierpinski’s Triangle is a fractal that will be familiar to most people. It’s probably the first fractal you learned to make on your TI-84 calculator, and has been the subject of far too many “Illuminati Confirmed” memes (give it a rest people, that meme’s getting old).

Lambda(
  ["X", "Y", "Z"],
  Format("%s %s %s", Var("X"), Var("Y"), Var("Z"))
)

…which outputs

**                                                                                                                              
****                                                                                                                            
**  **                                                                                                                          
********                                                                                                                        
**      **                                                                                                                      
****    ****                                                                                                                    
**  **  **  **                                                                                                                  
****************                                                                                                                
**              **                                                                                                              
****            ****                                                                                                            
**  **          **  **                                                                                                          
********        ********                                                                                                        
**      **      **      **                                                                                                      
****    ****    ****    ****                                                                                                    
**  **  **  **  **  **  **  **                                                                                                  
********************************                                                                                                
**                              **                                                                                              
****                            ****                                                                                            
**  **                          **  **                                                                                          
********                        ********                                                                                        
**      **                      **      **                                                                                      
****    ****                    ****    ****                                                                                    
**  **  **  **                  **  **  **  **                                                                                  
****************                ****************                                                                                
**              **              **              **                                                                              
****            ****            ****            ****                                                                            
**  **          **  **          **  **          **  **                                                                          
********        ********        ********        ********                                                                        
**      **      **      **      **      **      **      **                                                                      
****    ****    ****    ****    ****    ****    ****    ****                                                                    
**  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **                                                                  
****************************************************************                                                                
**                                                              **                                                              
****                                                            ****                                                            
**  **                                                          **  **                                                          
********                                                        ********                                                        
**      **                                                      **      **                                                      
****    ****                                                    ****    ****                                                    
**  **  **  **                                                  **  **  **  **                                                  
****************                                                ****************                                                
**              **                                              **              **                                              
****            ****                                            ****            ****                                            
**  **          **  **                                          **  **          **  **                                          
********        ********                                        ********        ********                                        
**      **      **      **                                      **      **      **      **                                      
****    ****    ****    ****                                    ****    ****    ****    ****                                    
**  **  **  **  **  **  **  **                                  **  **  **  **  **  **  **  **                                  
********************************                                ********************************                                
**                              **                              **                              **                              
****                            ****                            ****                            ****                            
**  **                          **  **                          **  **                          **  **                          
********                        ********                        ********                        ********                        
**      **                      **      **                      **      **                      **      **                      
****    ****                    ****    ****                    ****    ****                    ****    ****                    
**  **  **  **                  **  **  **  **                  **  **  **  **                  **  **  **  **                  
****************                ****************                ****************                ****************                
**              **              **              **              **              **              **              **              
****            ****            ****            ****            ****            ****            ****            ****            
**  **          **  **          **  **          **  **          **  **          **  **          **  **          **  **          
********        ********        ********        ********        ********        ********        ********        ********        
**      **      **      **      **      **      **      **      **      **      **      **      **      **      **      **      
****    ****    ****    ****    ****    ****    ****    ****    ****    ****    ****    ****    ****    ****    ****    ****    
**  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  
********************************************************************************************************************************

Compare to the original below:

WITH points AS (
  SELECT ROW, col FROM generate_series(0, 63) a(ROW)
  CROSS JOIN generate_series(0, 63) b(col)
  ORDER BY ROW DESC, col ASC
), marked_points AS (
   SELECT ROW, col, (CASE WHEN ROW & col != 0
                  THEN ' '
                  ELSE '*'
                  END) AS marker
   FROM points
   ORDER BY ROW DESC, col ASC
), ROWS AS (
   SELECT ROW, string_agg(marker, '') AS row_text
   FROM marked_points
   GROUP BY row
   ORDER BY ROW DESC
) SELECT string_agg(row_text, E'\n') FROM ROWS;

Mandelbrot Set

Michael Malis’ original version

The Mandelbrot set is the set of complex numbers cc for which the function fc(z)=z2+cf_{c}(z)=z^{2}+c does not diverge when iterated from z=0z=0, i.e., for which the sequence fc(0)f_{c}(0), fc(fc(0))f_{c}(f_{c}(0)), etc., remains bounded in absolute value.

Map(
  [ 1, 2, 3, 4, 5 ],
  Lambda(
    "number",
    Add(1, Var("number"))
  )
)

…which outputs

** 

Compare to the original below:

WITH RECURSIVE points AS (
  SELECT r, c FROM generate_series(-2, 2, 0.05) a(r)
  CROSS JOIN generate_series(-2, 1, 0.05) b(c)
  ORDER BY r DESC, c ASC
), iterations AS (
   SELECT r, c, 0.0::float AS zr, 0.0::float AS zc, 0 AS iteration FROM points
   UNION ALL
   SELECT r, c, zr*zr - zc*zc + c AS zr, 2*zr*zc + r AS zc, iteration+1 AS iteration
   FROM iterations WHERE zr*zr + zc*zc < 4 AND iteration < 1000
), final_iteration AS (
  SELECT * FROM iterations WHERE iteration = 1000
), marked_points AS (
   SELECT r, c, (CASE WHEN EXISTS (SELECT 1 FROM final_iteration i WHERE p.r = i.r AND p.c = i.c)
                  THEN '**'
                  ELSE '  '
                  END) AS marker
   FROM points p
   ORDER BY r DESC, c ASC
), lines AS (
   SELECT r, string_agg(marker, '') AS r_text
   FROM marked_points
   GROUP BY r
   ORDER BY r DESC
) SELECT string_agg(r_text, E'\n') FROM lines;

Julia Set Fractal

Michael Malis’ original version

The Julia Set fractal.

Create(
  Collection("Moons"),
  {
    data: {
      name: "Luna",
      planetRef: Ref(Collection("Planets"), "267081091831038483")
    }
  }
)

…which outputs

** 

Compare to the original below:

WITH RECURSIVE points AS (
  SELECT ROW, col FROM generate_series(-2, 2, 0.05) a(ROW)
  CROSS JOIN generate_series(-2, 2, 0.05) b(col)
  ORDER BY ROW DESC, col ASC
), iterations AS (
   SELECT ROW, col, col::float AS zr, row::float AS zc, 0 AS iteration FROM points
   UNION ALL
   SELECT ROW, col, zr*zr - zc*zc + 1 - 1.61803398875 AS zr, 2*zr*zc AS zc, iteration+1 AS iteration
   FROM iterations WHERE zr*zr + zc*zc < 4 AND iteration < 1000
), final_iteration AS (
  SELECT * FROM iterations WHERE iteration = 1000
), marked_points AS (
   SELECT ROW, col, (CASE WHEN EXISTS (SELECT 1 FROM final_iteration i WHERE p.ROW = i.ROW AND p.col = i.col)
                  THEN '**'
                  ELSE '  '
                  END) AS marker
   FROM points p
   ORDER BY ROW DESC, col ASC
), ROWS AS (
   SELECT ROW, string_agg(marker, '') AS row_text
   FROM marked_points
   GROUP BY row
   ORDER BY ROW DESC
) SELECT string_agg(row_text, E'\n') FROM ROWS;

Hilbert Curve

Michael Malis’ original version

The Hilbert Curve is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891.

Map(
  Paginate(Documents(Collection('Moons'))),
  Lambda("moonRef", Get(Var("moonRef")))
)

…which outputs

** 

Compare to the original below:

WITH RECURSIVE iterations AS (
  SELECT 'A' AS PATH, 0 AS iteration
  UNION ALL
  SELECT replace(replace(replace(PATH, 'A', '-CF+AFA+FC-'), 'B', '+AF-BFB-FA+'), 'C', 'B'), iteration+1 AS iteration
  FROM iterations WHERE iteration < 3
), segments AS (
  SELECT 0 AS r1, 0 AS c1, 0 AS r2, 0 AS c2, 0 AS r3, 0 AS c3, 0 AS dr, 1 AS dc, (SELECT path FROM iterations ORDER BY iteration DESC LIMIT 1) AS path_left
  UNION ALL
  SELECT r3 AS r1, c3 AS c1, r3 + dr * movement AS r2, c3 + dc * movement AS c2, r3 + 2 * dr * movement AS r3, c3 + 2 * dc * movement AS c3, dr, dc, SUBSTRING(path_left FROM 2) AS path_left
  FROM (
    SELECT r1, c1, r2, c2, r3, c3,
      CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN -dc
           WHEN SUBSTRING(path_left FOR 1) = '+' THEN dc
           ELSE dr
      END AS dr,
      CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN dr
           WHEN SUBSTRING(path_left FOR 1) = '+' THEN -dr
           ELSE dc
           END AS dc,
           path_left,
      CASE WHEN SUBSTRING(path_left FOR 1) = 'F' THEN 1 ELSE 0 END AS movement
  FROM segments
  WHERE CHAR_LENGTH(path_left) > 0
  ) sub
), end_points AS (SELECT r1 AS r, c1 AS c FROM segments UNION SELECT r3, c3 FROM segments),
points AS (
  SELECT r, c FROM generate_series((SELECT MIN(r) FROM end_points), (SELECT MAX(r) FROM end_points)) a(r)
  CROSS JOIN generate_series((SELECT MIN(c) FROM end_points), (SELECT MAX(c) FROM end_points)) b(c)
), marked_points AS (
SELECT r, c, (CASE WHEN
    EXISTS (SELECT 1 FROM end_points e WHERE p.r = e.r AND p.c = e.c)
    THEN '*'

    WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dc != 0)
    THEN '-'

    WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dr != 0)
    THEN '|'

    ELSE ' '
    END
    ) AS marker
FROM points p
), lines AS (
   SELECT r, string_agg(marker, '') AS row_text
   FROM marked_points
   GROUP BY r
   ORDER BY r DESC
) SELECT string_agg(row_text, E'\n') FROM lines;

Dragon Curve

Michael Malis’ original version

The Dragon Curve

Create(
  Collection("Moons"),
  {
    data: {
      name: "Luna",
      planetRef: Ref(Collection("Planets"), "267081091831038483")
    }
  }
)

…which outputs

** 

Compare to the original below:

WITH RECURSIVE iterations AS (
  SELECT 'FX' AS PATH, 0 AS iteration
  UNION ALL
  SELECT replace(replace(replace(PATH, 'X', 'X+ZF+'), 'Y', '-FX-Y'), 'Z', 'Y'), iteration+1 AS iteration
  FROM iterations WHERE iteration < 8
), segments AS (
  SELECT 0 AS r1, 0 AS c1, 0 AS r2, 0 AS c2, 0 AS r3, 0 AS c3, 0 AS dr, 1 AS dc, (SELECT path FROM iterations ORDER BY iteration DESC LIMIT 1) AS path_left
  UNION ALL
  SELECT r3 AS r1, c3 AS c1, r3 + dr * movement AS r2, c3 + dc * movement AS c2, r3 + 2 * dr * movement AS r3, c3 + 2 * dc * movement AS c3, dr, dc, SUBSTRING(path_left FROM 2) AS path_left
  FROM (
    SELECT r1, c1, r2, c2, r3, c3,
      CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN -dc
           WHEN SUBSTRING(path_left FOR 1) = '+' THEN dc
           ELSE dr
      END AS dr,
      CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN dr
           WHEN SUBSTRING(path_left FOR 1) = '+' THEN -dr
           ELSE dc
           END AS dc,
           path_left,
      CASE WHEN SUBSTRING(path_left FOR 1) = 'F' THEN 1 ELSE 0 END AS movement
  FROM segments
  WHERE CHAR_LENGTH(path_left) > 0
  ) sub
), end_points AS (SELECT r1 AS r, c1 AS c FROM segments UNION SELECT r3, c3 FROM segments),
points AS (
  SELECT r, c FROM generate_series((SELECT MIN(r) FROM end_points), (SELECT MAX(r) FROM end_points)) a(r)
  CROSS JOIN generate_series((SELECT MIN(c) FROM end_points), (SELECT MAX(c) FROM end_points)) b(c)
), marked_points AS (
SELECT r, c, (CASE WHEN
    EXISTS (SELECT 1 FROM end_points e WHERE p.r = e.r AND p.c = e.c)
    THEN '*'

    WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dc != 0)
    THEN '-'

    WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dr != 0)
    THEN '|'

    ELSE ' '
    END
    ) AS marker
FROM points p
), lines AS (
   SELECT r, string_agg(marker, '') AS row_text
   FROM marked_points
   GROUP BY r
   ORDER BY r DESC
) SELECT string_agg(row_text, E'\n') FROM lines;

Board

This is a recursive string-based fractal

Create(
  Collection("Moons"),
  {
    data: {
      name: "Luna",
      planetRef: Ref(Collection("Planets"), "267081091831038483")
    }
  }
)

…which outputs

** 

Compare to the original below:

WITH RECURSIVE iterations AS (
  SELECT 'F+F+F+F' AS PATH, 0 AS iteration
  UNION ALL
  SELECT replace(replace(replace(PATH, 'F', 'FF+F+F+F+FF'), 'R', '+LF-RFR-FL+'), 'Z', 'R'), iteration+1 AS iteration
  FROM iterations WHERE iteration < 3
), segments AS (
  SELECT 0 AS r1, 0 AS c1, 0 AS r2, 0 AS c2, 0 AS r3, 0 AS c3, 0 AS dr, 1 AS dc, (SELECT path FROM iterations ORDER BY iteration DESC LIMIT 1) AS path_left
  UNION ALL
  SELECT r3 AS r1, c3 AS c1, r3 + dr * movement AS r2, c3 + dc * movement AS c2, r3 + 2 * dr * movement AS r3, c3 + 2 * dc * movement AS c3, dr, dc, SUBSTRING(path_left FROM 2) AS path_left
  FROM (
    SELECT r1, c1, r2, c2, r3, c3,
      CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN -dc
           WHEN SUBSTRING(path_left FOR 1) = '+' THEN dc
           ELSE dr
      END AS dr,
      CASE WHEN SUBSTRING(path_left FOR 1) = '-' THEN dr
           WHEN SUBSTRING(path_left FOR 1) = '+' THEN -dr
           ELSE dc
           END AS dc,
           path_left,
      CASE WHEN SUBSTRING(path_left FOR 1) = 'F' THEN 1 ELSE 0 END AS movement
  FROM segments
  WHERE CHAR_LENGTH(path_left) > 0
  ) sub
), end_points AS (SELECT r1 AS r, c1 AS c FROM segments UNION SELECT r3, c3 FROM segments),
points AS (
  SELECT r, c FROM generate_series((SELECT MIN(r) FROM end_points), (SELECT MAX(r) FROM end_points)) a(r)
  CROSS JOIN generate_series((SELECT MIN(c) FROM end_points), (SELECT MAX(c) FROM end_points)) b(c)
), marked_points AS (
SELECT r, c, (CASE WHEN
    EXISTS (SELECT 1 FROM end_points e WHERE p.r = e.r AND p.c = e.c)
    THEN '*'

    WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dc != 0)
    THEN '-'

    WHEN EXISTS (SELECT 1 FROM segments s WHERE p.r = s.r2 AND p.c = s.c2 AND dr != 0)
    THEN '|'

    ELSE ' '
    END
    ) AS marker
FROM points p
), lines AS (
   SELECT r, string_agg(marker, '') AS row_text
   FROM marked_points
   GROUP BY r
   ORDER BY r DESC
) SELECT string_agg(row_text, E'\n') FROM lines;

End Notes

As we can see, there are plenty of differences between SQL and NoSQL databases like FaunaDB. Hopefully by showing the full flexibility of the FQL language I can make it easier for other developers that want to use this type of database.

Maybe someday, as more types of tutorials come up for FaunaDB, this whole post will seem tame by comparison. What comes next? Who knows. Maybe I’ll test FaunaDB’s turing completeness by making an FQL version of Fabien’s implementation of a Turing Machine built with SQL queries.


Cited as:

@article{mcateer2021fracpost2,
    title = "Fractals in FaunaDB",
    author = "McAteer, Matthew",
    journal = "matthewmcateer.me",
    year = "2021",
    url = "https://matthewmcateer.me/blog/fractals-in-faunadb/"
}

If you notice mistakes and errors in this post, don’t hesitate to contact me at [contact at matthewmcateer dot me] and I would be very happy to correct them right away!

See you in the next post 😄

I write about AI, Biotech, and a bunch of other topics. Subscribe to get new posts by email!


This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

At least this isn't a full-screen popup

That'd be more annoying. Anyways, subscribe to my newsletter to get new posts by email! I write about AI, Biotech, and a bunch of other topics.


This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.