FGA Indexes and Cyclical Behavior

example1-tuples.sql

INSERT INTO tuples VALUES ('document', '1', 'viewer', 'editor', 'document', '1');

example1-view.sql

CREATE VIEW myindex AS WITH MUTUALLY RECURSIVE
     document_editor(
      subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT
     ) AS (
      SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id
      FROM tuples
      WHERE object_type='document' AND relation='editor' AND subject_type IN ('user') AND subject_relation=''
      
      UNION
      
      SELECT r.subject_type, r.subject_id, r.subject_relation, 'editor', s.object_type, s.object_id
      FROM document_viewer r, tuples s
      WHERE s.subject_type = 'document' AND s.subject_relation = 'viewer' AND
			  s.relation = 'editor' AND s.object_type = 'document' AND
			  s.subject_type = r.object_type AND s.subject_id = r.object_id AND
			  s.subject_relation = r.relation),
     document_viewer(
      subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT
     ) AS (
      SELECT subject_type, subject_id, subject_relation, 'viewer', object_type,object_id FROM document_editor
     )
	SELECT * FROM document_editor UNION ALL SELECT * FROM document_viewer;

example3-tuples.sql

INSERT INTO tuples VALUES
  ('document', '1', 'viewer', 'editor', 'document', '1'), -- document:1#editor@document:1#viewer
  ('document', '1', 'editor', 'viewer', 'document', '1'); -- document:1#viewer@document:1#editor
  

example3-view.sql

CREATE VIEW fga_index AS WITH MUTUALLY RECURSIVE
		document_editor(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='editor' AND subject_type IN ('user') AND subject_relation='' UNION SELECT r.subject_type, r.subject_id, r.subject_relation, 'editor', s.object_type, s.object_id FROM document_viewer r, tuples s WHERE s.subject_type = 'document' AND s.subject_relation = 'viewer' AND
			  s.relation = 'editor' AND s.object_type = 'document' AND
			  s.subject_type = r.object_type AND s.subject_id = r.object_id AND
			  s.subject_relation = r.relation),document_viewer(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (WITH operand_0 AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='viewer' AND subject_type IN ('user') AND subject_relation='' UNION SELECT r.subject_type, r.subject_id, r.subject_relation, 'viewer', s.object_type, s.object_id FROM document_editor r, tuples s WHERE s.subject_type = 'document' AND s.subject_relation = 'editor' AND
			  s.relation = 'viewer' AND s.object_type = 'document' AND
			  s.subject_type = r.object_type AND s.subject_id = r.object_id AND
			  s.subject_relation = r.relation), operand_1 AS (SELECT subject_type, subject_id, subject_relation, 'viewer', object_type,object_id FROM document_editor)SELECT subject_type, subject_id, subject_relation, relation, object_type, object_id FROM operand_0 WHERE EXISTS (SELECT FROM operand_1))

	SELECT * FROM document_editor UNION ALL SELECT * FROM document_viewer;

example4-tuples.sql

INSERT INTO tuples VALUES
  ('user', 'jon', '', 'allowed', 'document', '1'),         -- document:1#allowed@user:jon
  ('document', '1', 'viewer', 'viewer', 'document', '1'); -- document:1#viewer@document:1#viewer

example4-view.sql

CREATE VIEW fga_index AS WITH MUTUALLY RECURSIVE
		document_allowed(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='allowed' AND subject_type IN ('user') AND subject_relation=''),document_viewer(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (WITH operand_0 AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='viewer' AND subject_type IN ('user') AND subject_relation='' UNION SELECT r.subject_type, r.subject_id, r.subject_relation, 'viewer', s.object_type, s.object_id FROM document_viewer r, tuples s WHERE s.subject_type = 'document' AND s.subject_relation = 'viewer' AND
			  s.relation = 'viewer' AND s.object_type = 'document' AND
			  s.subject_type = r.object_type AND s.subject_id = r.object_id AND
			  s.subject_relation = r.relation), operand_1 AS (SELECT subject_type, subject_id, subject_relation, 'viewer', object_type,object_id FROM document_allowed)SELECT subject_type, subject_id, subject_relation, relation, object_type, object_id FROM operand_0 WHERE EXISTS (SELECT FROM operand_1))

	SELECT * FROM document_allowed UNION ALL SELECT * FROM document_viewer;

example5-tuples.sql

INSERT INTO tuples VALUES ('document', '1', 'viewer', 'viewer', 'document', '1'); -- document:1#viewer@document:1#viewer

example5-view.sql

CREATE VIEW fga_index AS WITH MUTUALLY RECURSIVE
		document_viewer(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='viewer' AND subject_type IN ('user') AND subject_relation='' UNION SELECT r.subject_type, r.subject_id, r.subject_relation, 'viewer', s.object_type, s.object_id FROM document_viewer r, tuples s WHERE s.subject_type = 'document' AND s.subject_relation = 'viewer' AND
			  s.relation = 'viewer' AND s.object_type = 'document' AND
			  s.subject_type = r.object_type AND s.subject_id = r.object_id AND
			  s.subject_relation = r.relation)

	SELECT * FROM document_viewer;

example6-tuples.sql

INSERT INTO tuples VALUES ('document', '1', 'viewer', 'viewer', 'document', '1');

example6-view.sql

CREATE VIEW fga_index AS WITH MUTUALLY RECURSIVE
		document_restricted(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='restricted' AND subject_type IN ('user') AND subject_relation=''),document_viewer(subject_type TEXT, subject_id TEXT, subject_relation TEXT, relation TEXT, object_type TEXT, object_id TEXT) AS (WITH base AS (SELECT subject_type, subject_id, subject_relation, relation, object_type,object_id FROM tuples WHERE object_type='document' AND relation='viewer' AND subject_type IN ('user') AND subject_relation='' UNION SELECT r.subject_type, r.subject_id, r.subject_relation, 'viewer', s.object_type, s.object_id FROM document_viewer r, tuples s WHERE s.subject_type = 'document' AND s.subject_relation = 'viewer' AND
			  s.relation = 'viewer' AND s.object_type = 'document' AND
			  s.subject_type = r.object_type AND s.subject_id = r.object_id AND
			  s.subject_relation = r.relation), subtract AS (SELECT subject_type, subject_id, subject_relation, 'viewer', object_type,object_id FROM document_restricted) SELECT subject_type, subject_id, subject_relation, relation, object_type, object_id FROM base b WHERE NOT EXISTS (SELECT FROM subtract s WHERE b.subject_type=s.subject_type AND b.subject_id=s.subject_id AND b.object_type=s.object_type AND b.object_id=s.object_id))

	SELECT * FROM document_restricted UNION ALL SELECT * FROM document_viewer;