{"id":2655,"date":"2015-09-22T00:31:26","date_gmt":"2015-09-22T00:31:26","guid":{"rendered":"http:\/\/www.garysieling.com\/blog\/?p=2655"},"modified":"2015-09-22T00:31:26","modified_gmt":"2015-09-22T00:31:26","slug":"handling-circular-data-structures-in-postgres","status":"publish","type":"post","link":"https:\/\/www.garysieling.com\/blog\/handling-circular-data-structures-in-postgres\/","title":{"rendered":"Handling Circular Data Structures in Postgres"},"content":{"rendered":"

Let’s say we’re setting up a data structure for security, with group membership:<\/p>\n

\ncreate table groups (\n  id int unique,\n  name varchar unique,\n  member_groups int[]\n);\n<\/pre>\n
\n\ninsert into groups values (1, 'admins', '{}');\n\n-- automatically include any admins as users\ninsert into groups values (2, 'users', '{1}'); \n\n-- grant admins access to write\ninsert into groups values (3, 'writers', '{1}'); \n\n-- grant writers access to read\ninsert into groups values (4, 'readers', '{3}'); \n<\/pre>\n
Now, we want to flatten this structure to find all transitive memberships. To do this, we take each group’s children, find their children, and concatenate the result recursively.<\/p>\n
Note that the column order in each part of the recursive sql must be the same, as well as in the column definition on the first line.<\/p>\n
\nWITH RECURSIVE all_groups(id, member_groups) AS (\n    select\n      id,\n      member_groups\n    from groups\n  UNION ALL\n    SELECT groups.id,\n           all_groups.member_groups || groups.member_groups\n    FROM all_groups\n    JOIN groups\n      ON all_groups.id = ANY (groups.member_groups)\n  )\nSELECT id, uniq(flatMap(member_groups))\nFROM all_groups\nGROUP BY id;\n<\/pre>\n
Note that here, I’m using some custom functions I’ve introduced<\/a>, to match some functionality of the Scala collections API.<\/p>\n
And this is what we get, as expected:<\/p>\n
\n4,{1,3}\n1,\n3,{1}\n2,{1}\n<\/pre>\n
Lets say someone adds a circular reference to this array:<\/p>\n
\ninsert into groups values (5, 'cycle1', '{3}', '{3, 7}');\ninsert into groups values (6, 'cycle2', '{3}', '{5}');\ninsert into groups values (7, 'cycle3', '{3}', '{6}');\n<\/pre>\n
We can easily fix this, by adding an additional array to track what we’ve seen already in the recursion:<\/p>\n
\n\nWITH RECURSIVE all_groups(found, id, member_groups) AS (\n    select\n      array[id] found,\n      id,\n      member_groups\n    from groups\n  UNION ALL\n    SELECT array[groups.id] || all_groups.found found,\n          groups.id,\n          all_groups.member_groups || groups.member_groups\n    FROM all_groups\n    JOIN groups\n      ON all_groups.id = ANY (groups.member_groups)\n      AND NOT (groups.id = ANY (found))\n  )\nSELECT id, uniq(flatMap(member_groups))\nFROM all_groups\nGROUP BY id;\n<\/pre>\n
And we’re done! Since a cycle just indicates an equivalence class of groups, they should all get the same group members, and we can detect them by seeing that they contain their own IDs:<\/p>\n
\n8,{5,8}\n4,{1,3}\n1,\n5,{5,8}\n3,{1}\n9,{5,8}\n6,{5,8}\n2,{1}\n7,{5,6,8}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Let’s say we’re setting up a data structure for security, with group membership: create table groups ( id int unique, name varchar unique, member_groups int[] ); insert into groups values (1, ‘admins’, ‘{}’); — automatically include any admins as users insert into groups values (2, ‘users’, ‘{1}’); — grant admins access to write insert into … <\/p>\n
Continue reading “Handling Circular Data Structures in Postgres”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[4],"tags":[437,523],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/posts\/2655"}],"collection":[{"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/comments?post=2655"}],"version-history":[{"count":0,"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/posts\/2655\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/media?parent=2655"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/categories?post=2655"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.garysieling.com\/blog\/wp-json\/wp\/v2\/tags?post=2655"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}