Instantly share code, notes, and snippets.

# JerryNixon/graph.puzzle.md

Last active January 31, 2022 23:28
Show Gist options
• Save JerryNixon/c25183c65444a236a2e4a3690220091e to your computer and use it in GitHub Desktop.
Triple constrained Edges in a Graph

## Scenario

1. Every Store (wants) every Product
2. Every Warehouse (Has) every Product
3. Stores (Must_Use) certain Warehouses for certain Products.

## Problem

1. A graph Edge only references two Nodes: from & to
2. How can we constrain an Edge to a third Node (Product)

## Solution

1. Add ProductId to Product Node
2. Add ProductId to (Must_Use) Edge

## Considerations

What if there are thousands of Stores, Hundreds of Warehouses, and Hundreds of Thousands of Products? The number of (Must_Use) Edge rows would be like # of Stores x # of Warehouses x # of Products. This could make the edge have millions of rows. With performance as a consideration, is this the only way? Answer: Yes, I think it is.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 begin transaction create table warehouse (id int, name varchar(50)) as node; insert warehouse values (1, 'southeast'), (2, 'southwest'), (3, 'northeast'), (4, 'northwest'); create table store (id int, name varchar(50)) as node insert store values (1, 'north'), (2, 'south'), (3, 'east'), (4, 'west') create table product (id int, name varchar(50)) as node; insert into product values (1, 'shrimp'), (2, 'apples'), (3, 'noodles'); -- all warehouses have all products create table has as edge; insert into has (\$from_id, \$to_id) select warehouse.\$node_id, product.\$node_id from product, warehouse -- all stores want all products create table wants as edge; insert into wants (\$from_id, \$to_id) select store.\$node_id, product.\$node_id from product, store -- move to variables just for ease declare @store1 varchar(500) = (select \$node_id from store where id = 1) declare @store2 varchar(500) = (select \$node_id from store where id = 2) declare @store3 varchar(500) = (select \$node_id from store where id = 3) declare @warehouse1 varchar(500) = (select \$node_id from warehouse where id = 1) declare @warehouse2 varchar(500) = (select \$node_id from warehouse where id = 2) declare @warehouse3 varchar(500) = (select \$node_id from warehouse where id = 3) -- limited must use create table must_use (ProductId int) as edge; -- product 1 insert into must_use (\$from_id, \$to_id, ProductId) select @store1, @warehouse1, 1 insert into must_use (\$from_id, \$to_id, ProductId) select @store2, @warehouse1, 1 insert into must_use (\$from_id, \$to_id, ProductId) select @store3, @warehouse1, 1 -- product 2 insert into must_use (\$from_id, \$to_id, ProductId) select @store1, @warehouse2, 2 insert into must_use (\$from_id, \$to_id, ProductId) select @store2, @warehouse2, 2 insert into must_use (\$from_id, \$to_id, ProductId) select @store3, @warehouse1, 2 -- product 3 insert into must_use (\$from_id, \$to_id, ProductId) select @store1, @warehouse3, 3 insert into must_use (\$from_id, \$to_id, ProductId) select @store2, @warehouse3, 3 insert into must_use (\$from_id, \$to_id, ProductId) select @store3, @warehouse1, 3 -- ?? Where can All stores get Product2? select store.Name as Store , warehouse.Name as Warehouse , product.Name as Product from store , must_use , warehouse , has , product , wants where match(store -(must_use)-> warehouse -(has)-> product <-(wants)- store) and must_use.ProductId = product.Id order by 1, 3 rollback

### JerryNixon commented Jan 31, 2022

The results show us that only the `East` store can get `Noodles` from the `Southeast` Warehouse. The other Stores get `Noodles` from the `Northeast` Warehouse. This is because of the third constraint defined in the `Must_Use` Edge, leveraged in the `must_use.ProductId = product.Id` predicate.