cayleygraph / cayleygraph/cayley

ForAll / Universal Quantifiers

Open
#209 4 comments 1 reaction 0 assignees View on GitHub
good first issue query languages
Dominant language
Go
Stars
15.1k
Forks
1.2k
PR merge metrics
No merged PRs in 30d

Description

We have a Not iterator now. It'd be possible to add a shorthand macro in Gremlin to emulate the [Universal Quantifier](http://en.wikipedia.org/wiki/Universal_quantification), ForAll.

All queries currently work on existence. That is, each stage depends on "there exists some path X to node Y". Using negation you can achieve "for all paths from X, (rest of query holds)".

The key insight being that
`(X holds for (ForAll A)) == (X holds for A) AND (X holds for (Not (Not A))) == (X holds for (A AND (Not (Not A))))`

In today's parlance, this is:
var a = g.M()....
`g.V().And(a).And(g.V().Except(g.V().Except(a)))...`

It's a hack, but one that holds mathematically. Currently can be implemented as a macro on the query level, and is actually really hard to optimize further. (Suggestions, of course, are welcome)

Contributor guide

Open the contributing guide

Research direction

Start with the existing Not iterator and the query-level Gremlin macro described here. Compare the proposed ForAll behavior with the supplied And/Except/Not expression; done means a supported universal-quantifier shorthand with equivalent results, while optimization remains unresolved.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.