Adding relationship to existing nodes with Cypher

In Neo4j 2.0 you can create schema indexes for your labels and the properties you use for lookup:

CREATE INDEX ON :User(username)
CREATE INDEX ON :Role(name)

To create relationships you might use:

MATCH (u:User {username:'admin'}), (r:Role {name:'ROLE_WEB_USER'})
CREATE (u)-[:HAS_ROLE]->(r)

The MATCH will use an index if possible. If there is no index, it will lookup up all nodes carrying the label and see if the property matches.

N.B. the syntax above will only work with Neo4j 2.0.0-RC1 and above.

Update as of 4/2020:
The new Cypher syntax is as follows. as 'CREATE INDEX ON' has been deprecated is..

CREATE INDEX FOR (n:Label) ON (n.property)