Well the most useful way I've found of classifying stuff is by analogy with formal grammars. If you view the kind of paths you can query as the set of words in

Well the most useful way I've found of classifying stuff is by analogy with formal grammars. If you view the kind of paths you can query as the set of words in a language then you get something like: Basic (non-recursive) SQL: Finite paths Recursive SQL / Transitive closure (with negation): Regular paths However the hierarchy of languages doesn't end there. And some graph databases allow you to add arbitrary grammar rules, which make it possible to add some complex rules like: - If condition X,Y and Z is satisfied then person A and B are the same person - Equality is transitive - If two people are equal then each property of one is also a property of the other. The part that makes this tricky is that figuring out two people are equal can cause other people to now suddenly satisfy the condition for equality. You could also construct some examples by creating conditions which aren't "regular" (e.g. person A and B have an ancestor which is the same number of generations back for both of them).