Browse Prior Art Database

Applying Graph Traversal Queries Over Plain Objects

IP.com Disclosure Number: IPCOM000244587D
Publication Date: 2015-Dec-23
Document File: 4 page(s) / 79K

Publishing Venue

The IP.com Prior Art Database

Abstract

Object Oriented Programming is one of the most popular paradigms in programming languages. In these languages, the data entities are represented by objects that have attributes and methods. Attributes can hold values of primitive or of complex types, or can reference other objects. The objects together with attributes that reference them, form, in essence, a graph structure (i.e., vertices represent entities and edges represent references between them). Searching for specific data within this graph can be a tedious task in terms of programming - it requires specifying graph traversal logic in a general purpose language, which lacks graph traversal paradigms. Executing this logic can be slow (in running time) due to sub-optimal algorithms applied by a programmer. Recently query languages have begun to be embedded into programming languages to alleviate this task (see for example LINQ). However these query languages do not treat the objects as a graph so they do not allow traversal queries. Traversal queries make it easier to represent paths between objects and also to support traversals of paths of variable sizes.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 37% of the total text.

Page 01 of 4

Applying Graph Traversal Queries Over Plain Objects

Object Oriented Programming is one of the most popular paradigms in programming languages. In these languages, the data entities are represented by objects that have attributes and methods. Attributes can hold values of primitive or of complex types, or can reference other objects. The objects together with attributes that reference them, form, in essence, a graph structure (i.e., vertices represent entities and edges represent references between them).

Searching for specific data within this graph can be a tedious task in terms of programming - it requires specifying graph traversal logic in a general purpose language, which lacks graph traversal paradigms. Executing this logic can be slow (in running time) due to sub-optimal algorithms applied by a programmer.

Recently query languages have begun to be embedded into programming languages to alleviate this task (see for example LINQ). However these query languages do not treat the objects as a graph so they do not allow traversal queries. Traversal queries make it easier to represent paths between objects and also to support traversals of paths of variable sizes.

In recent years, graph traversal query languages have been developed (see for example Gremlin https://github.com/tinkerpop/gremlin/wiki). These languages allow formulating a path traversal in a concise and readable manner. The path traversal queries are then processed and optimized by compiler or language runtime to be executed as fast as possible. These languages have originally been designed to be executed in Graph Databases which are generally very large distributed systems which store data in a distributed fashion over multiple machines in a cluster . Gremlin for example is quickly becoming a dominant language for querying graph databases and many standards have been developed to support it. Our patent deals with applying such graph traversal queries not over graph databases but over plain objects of a programming language, in memory (for example Plain Old Java* Objects (POJOs)).

Note that IBM has taken a significant interest in Titan DB which is a graph database that supports Gremlin queries. It is therefore IBM's interest to promote Gremlin even further and get programmers to be acquainted with Gremlin by using it as an in-language query language --- i.e., by allowing programmers to issue Gremlin queries over their plain objects (not just over a database).

Prior Art:

US Patent US20140025691 "Method and apparatus for dynamic filtering of an object graph in a content repository" describes using XPATH query language for performing queries on objects in a content repository. Our patent proposes to use a graph traversal query language for queries on objects of a programming language, in memory.

US patent US8782619 "Extending programming language semantics while maintaining

standard syntax through aliasing" describes a method to extend an existing programming language w...