Custom Traversals

Now that our users can follow one another, we can run some more interesting queries (aka traversals) on our data. For example, we may want to discover the followers of followers of a given user.

xget 'model/user/id/73/rel/followed_by/rel/followed_by'

And see what they are tweeting about.

xget 'model/user/id/73/rel/followed_by/rel/followed_by/rel/tweets'

Another example would be to find users with similar taste (i.e. users that follow the same people).

xget 'model/user/id/73/rel/follows/rel/followed_by'

The result of the above query may contain duplicates. For example, if users 73 and 75 follow the same three people, user 75 will appear in the result three times. If we are not interested in duplicates, there is an easy fix.

xget 'model/user/id/73/rel/follows/rel/followed_by/unique'

But there is another problem with this query - If the result is not empty, it will include user 73. This is not what we want! We want to find other users with similar taste.

At this point, you might be wondering … Is there a quick fix for our query? Is the API flexible enough to cover any crazy query I come up with? If the API is flexible enough, will I have to learn a gazillion commands in order to write my queries?

We asked ourselves the same questions, when we built the xnlogic framework. These questions led us to the following approach:

  • Use Ruby code, with “full access” to the underlying graph, to implement any query we want.
  • Expose the query to the API with a meaningful name.

This design allows us to make the query above accessible via the following API call:

xget 'model/user/id/73/to/similar_users'

Let’s see how this is done …

Introducing route traversals

Custom queries are defined using route traversals. The concept of route traversals is somewhat similar to actions - Actions expose instance methods to the API, while route traversals expose custom queries.

Just like with actions, defining route traversals is a two-step process:

  1. Define the query as a method in the Route module.
  2. Expose it to the API using a route_traversal declaration.

In order to define our similar_users traversal, we will need to add the following code to the User module in lib/my_app/parts/user.rb.

route_traversal :similar_users, return_parts: :User do
    self.similar_users.uniq
end

module Route

    def similar_users()
        self.follows.followed_by.except(self)
    end

end

There are a few things we should note about the code above:

  • We define the similar_users method inside the Route module.
  • When we declare a route traversal we specify
    • Its name (:similar_users).
    • Its return type, using the return_parts attribute.
    • Its body, as a block of code.
  • We applied the uniq filter in the route traversal’s body, and not in the instance method. This will become useful later in this section.

Before we start accessing our route traversal, let’s create some fake data, in order to make the results more interesting.

Create some fake data

Let’s create some fake users (using the API) by pasting the following code in the console.

xput '/model/user', {username: 'grover_kiehn', email: 'jee_smith@hotmail.com'}
xput '/model/user', {username: 'maxine.wehner', email: 'demarcus@yahoo.com'}
xput '/model/user', {username: 'carolina_marquardt', email: 'maida_parisian@gmail.com'}
xput '/model/user', {username: 'golden.kunde', email: 'valentina@hotmail.com'}
xput '/model/user', {username: 'belle', email: 'bonnie@gmail.com'}
xput '/model/user', {username: 'mateo_hirthe', email: 'hettie_schaden@hotmail.com'}
xput '/model/user', {username: 'elia_keler', email: 'effie@hotmail.com'}
xput '/model/user', {username: 'kaitlyn.corwin', email: 'elton@gmail.com'}
xput '/model/user', {username: 'grayson', email: 'derick_huels@hotmail.com'}
xput '/model/user', {username: 'loren', email: 'taya@hotmail.com'}
xput '/model/user', {username: 'winfield', email: 'haven@yahoo.com'}
xput '/model/user', {username: 'keira.hills', email: 'fern@gmail.com'}
xput '/model/user', {username: 'gregoria', email: 'caesar@hotmail.com'}
xput '/model/user', {username: 'anika', email: 'zelda.graham@gmail.com'}
xput '/model/user', {username: 'lenora', email: 'hugh.barton@yahoo.com'}
xput '/model/user', {username: 'oswald_schuster', email: 'jey_beatty@hotmail.com'}

Next, let’s create some random follow-relations between our users (using Ruby code) by pasting the following code in the IRB.

users = app.graph.v(MyApp::M::User).to_a
app.graph.transaction do
    users.each do |user|
        how_many = (rand * users.length).to_i
        users_to_follow = users.shuffle[0...how_many].reject {|u| u == user}
        user.add_follows(users_to_follow)
    end
end

Getting similar users via the API

We access route traversals by appending /to/TRAVERSAL_NAME to the URL path of a GET request. For example:

jruby-1.7.18 :033 > xget 'model/user/id/73/to/similar_users'
 # ...
Total: 16

We can get specific properties from the result.

jruby-1.7.18 :034 > xget 'model/user/id/73/to/similar_users/properties/username'

We can also chain our traversal. For example, let’s see what users who are similar to user 73 are tweeting about.

jruby-1.7.18 :035 > xget 'model/user/id/73/to/similar_users/rel/tweets/properties/text'

Recommending users to follow

Let’s see another, slightly more complicated, example of a route traversal - We would like to recommend a user other users he/she might be interested in following.

We will define the following method in the Route module.

def recommended_users_to_follow(limit)
    self.similar_users.follows.except(self).except(self.follows).most_frequent(0...limit)
end

Let’s mention a few things about the code:

  • We build our query gradually:
    • Start from users with similar taste, and see who they are following.
    • Filter out myself and whoever I am already following from the result.
    • Users that appear multiple times in the result, are followed by multiple users with similar taste to mine. Therefore, in the last step, we include the most frequent users.
  • Since our similar_users method keeps duplicates, users with “more similar taste to mine” will have more influence on the result of the recommendation results.

At this point, we can expose our recommendation method as an API traversal, by adding the following code to the User module.

route_traversal :should_follow, return_parts: :User do
    self.recommended_users_to_follow(10)
end

We can reload our code, and use our traversal in order to get recommended users to follow.

jruby-1.7.18 :036 > xget 'model/user/id/73/to/should_follow'

As before, we can chain the traversal and see who these recommended users are following, and what these users are tweeting about.

jruby-1.7.18 :037 > xget 'model/user/id/73/to/should_follow/rel/follows/unique/rel/tweets/property/text'

Although the query above is fairly long, it shouldn’t scare you. After all, if you consider a query to be too long, you can always expose it as a route traversal with a meaningful name.

Note: Recommendation engines are one of the highlights of graph databases. The database allows us to traverse a neighbourhood of the graph efficiently, and Ruby allows us to easily express the traversal.

Summary

  • We expose custom queries to the API using route_traversal declaration.
    This is similar to the way we exposed instance methods to the API using action declarations.
  • Queries must be defined inside the Route module.
  • Traversal are accessed via GET requests.
  • Traversal are accessed by appending /to/TRAVERSAL_NAME to the URL path.
  • Given the right tools, we can build an efficient recommendation engine with a couple of line of code.
« Actions
Running The Server »