jpmmcneill / dbt-graph-theory Goto Github PK

A dbt package designed to help SQL based analysis of graphs

License: Apache License 2.0

Shell 100.00%

dbt-graph-theory's Introduction

Hi there 👋

I'm James (he/him), from Dublin in Ireland. I studied Theoretical Physics in Trinity College Dublin. I am interested in Applied Math and Game theory - particularly in relation to Ecology. I'd love to do a PhD in this area at some point, if the stars align 😄.

I currently work in a Quant Research department for a trading company.

I have worked at:

CRH, Mostly Investor relations
Conjura, Analytics, Product Lead & Engineering Manager

There are some open source items that I have worked / am working on:

A Universal Semantic Layer (still private, slow WIP with a friend of mine)
DBT (I've used it a lot, have a love/hate relationship with it, am a package maintainer, and have been invovled with the duckdb adapter)
PuffinDB (mostly giving product guidance)
Pypulation, a python library for population dynamics (it's too basic to be useful right now)

And a few ideas I have for the future:

A SQL supporting data lake powered by single table design on dynamoDB (not designed to be useful)
Opinionated SQL linter for building sensible sql pipelines
DuckDB extension for FMRI data

Get in touch with my linkedin or email (jpmmcneill AT gmail.com)

dbt-graph-theory's People

Contributors

Stargazers

Watchers

Forkers

bparbhurestore

dbt-graph-theory's Issues

Graph based join reduction

Consider the sets [A,B,C] and [A',B',C'] being joined.

Let's say that there is some complicating data in the underlying join condition, meaning that some

flowchart LR
  A---A'
  B---A'
  B---B'
  C---B'
  C---C'

intuitively, this could correspond to:

flowchart LR
  A---A'
  B---B'
  C---C'

Namely, we should investigate a graph based approach to reducing join duplication on both sides (and implicitly assuming that a 1-1 relationship should be constructed).

A more tangible example is:

flowchart LR
  A---A'
  B---A'
  B---B'

which could be reduced to:

flowchart LR
  A---A'
  B---B'

connect subgraphs readme

include data type examples

DuckDB support

https://github.com/jwills/dbt-duckdb

Dijkstra's algorithm for graph

Take two nodes as input, or maybe rank

Graph is connected generic test

A connected graph is one where the entire set is a subgraph (from the perspective of the subgraph_identifier macro).

This generic test could invoke the subgraph identifier, and then check whether there was only one subgraph id per graph id.

This needs to be a model level test, and the columns could be inputs to the macro.

CircleCI

With CircleCI, integration tests on other DBs (not just postgres) could be set up.

This would incur some costs - so probably just PRs to main would suffice.

Subgraph identifier better readme structure

Use mermaid in readme to illustrate what is happening for some examples.

Kahn's algorithm macro

To generate topologically sorted graph

This would potentially make an ordering for a given graph

CI/CD

Set up framework for running integration tests both locally and on PR.

Connect subgraphs macro

Macro that enforces all subgraphs in an original table to be connected.

Optional node rank

more adapter support!!!

this package should at least support all of the dbt supported adapters

DuckDB CI

Euler classification macro

Eulerian paths and Eulerian circuits

Bellman Ford macro

Compute the shortest path between all vertices of a graph

Identify subgraphs macro

Macro that identifies subgraphs, with an optional graph level for multiple graphs in the same table

Breadth first search

https://en.wikipedia.org/wiki/Breadth-first_search

I think the key part of this is that if a recursive CTE is used, we want to terminate the the recursion early. This means that we need to figure out how to terminate a recursive query early (which is easily possibly using a subquery, but some DBs will not support this).

Possibly, using a Nested Set Model is an approach to fix this.