Skip to content

Instantly share code, notes, and snippets.

@JerryNixon
Last active January 31, 2022 23:28
Show Gist options
  • Save JerryNixon/c25183c65444a236a2e4a3690220091e to your computer and use it in GitHub Desktop.
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.

image

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
Copy link
Author

image

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment