Correct, turing completeness is not the lower bound for non-guaranteed termination. It is however possible to have some forms of recursion without sacrificing guaranteed termination. Neo4j traversals, memorizing visited paths, relationships or nodes are an example (Note, it would be nice to have an option to memorize visited (Node, RelationshipType, Direction)). This limited form of recursion is useful as a query language. Doing so of course eliminates correct statements.
When memorizing nodes, the statement john (FRIEND_OF, OUTGOING) pete (FRIEND_OF, OUTGOING) john can no longer be true, but we could memorize relationships instead of nodes. This makes the former statement possible, but makes it impossible to return the statement john (FRIEND_OF, OUTGOING) pete (FRIEND_OF, OUTGOING) john (FRIEND_OF, OUTGOING) pete, unless john has more than one outgoing FRIEND relationship with pete (Memorizing (Node, RelationshipType, Direction) would make that statement impossible even in the presence of more than one FRIEND relationship from john to pete). While repeated paths in the graph are in principle true statements of the graph grammar, in many practical programming tasks we are not interested in such statements and in fact like to see those eliminated. Niels > From: okramma...@gmail.com > Date: Thu, 1 Sep 2011 08:17:27 -0600 > To: user@lists.neo4j.org > Subject: Re: [Neo4j] Hyperedges in Neo4j > > Hey, > > > I think a traversal should in principal be performed with a query language > > that is not turing complete so we can guarantee termination. > > Turning completeness is not the lower bound for non-guaranteed termination. > You can't guarantee completion in a regular language when your "String" (data > structure) is a graph. E.g. > > a* > > The only languages guaranteed to complete are Star-free languages. That is, > those that don't allow for recursion. > > See ya, > Marko. > > http://markorodriguez.com > _______________________________________________ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user _______________________________________________ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
