eValhalla Setup

[Previous in this series: eValhalla Kick Off, Next: eValhalla User Management]

The first step in eValhalla after the official kick off is to setup a development environment with all the selected technologies. That's the goal for this iteration. I'll quickly go through the process of gathering the needed libraries and implement a simple login form that ties everything together.

Technologies

Here are the technologies for this project:

1. Scala programming language - I had a dilemma. Java has a much larger user base and therefore should have been the language of choice for a tutorial/promotional material on HGDB and JSON storage with it. However, this is actually a serious project to go live eventually and I needed an excuse to code up something more serious with Scala, and Scala has enough accumulated merits, so Scala it is. However, I will show some Java code as well,  just in the form of examples, equivalent to the main code.
2. HyperGraphDB with mJson storage - that's a big part of my motivation to document this development. I think HGDB-mJson are a really neat pair and more people should use them to develop webapps. 
3. Restlet framework REST - this is one of very few implementations of JSR 311, that is sort of lightweight and has some other extras when you need them. 
4. jQuery - That's a no brainer.
5. AngularJS - Another risky choice, since I haven't used this before. I've used KnockoutJS and Require.js, both great frameworks and well-thought out. I've done some ad hoc customization of HTML tags, tried various template engines, AngularJS promises to give me all of those in a single library. So let's give it a shot.

Getting and Running the Code

Before we go any further, I urge you to get, build and run the code. Besides Java and Scala, I encourage you to get a Git client (Git is now supported on Windows as well), and you need the Scala Build Tool (SBT). Then, on a command console, issue the following commands:

1. git clone https://github.com/publicvaluegroup/evalhalla.git
2. cd evalhalla
3. git checkout phase1
4. sbt
5. run

Note the 3d step of checking out the  phase1 Git tag - every blog entry is going to be a separate development phase so you can always get the state of the project at a particular blog entry.  If you don't have Git, you can download an archive from:

https://github.com/publicvaluegroup/evalhalla/zipball/phase1

All of the above commands will take a while to execute the first time, especially if you don't have SBT yet. But at the end you should see the something like this on your console:

[info] Running evalhalla.Start 
No config file provided, using defaults at root /home/borislav/evalhalla
checkpoint kbytes:0
checkpoint minutes:0
Oct 18, 2012 12:01:01 AM org.restlet.engine.connector.ClientConnectionHelper start
INFO: Starting the internal [HTTP/1.1] client
Oct 18, 2012 12:01:01 AM org.restlet.engine.connector.ServerConnectionHelper start
INFO: Starting the internal [HTTP/1.1] server on port 8182
Started with DB /home/borislav/evalhalla/db

and you should have a running local server accessible at http://localhost:8182. Hit that URL, type in a username and a password and hit login.

Architectural Overview

The architecture is made up of a minimal set of REST services that essentially offer user login and access-controlled data manipulation to a JavaScript client-side application. The key will be to come up with an access policy that deals gracefully with a schema free database.

The data itself consists of JSON objects stored as a hypergraph using HGDB-mJson. From the client side we can create new objects and store them. We can then query for them or delete them. So it's a bit like the old client-server model from the 90s. HyperGraphDB supports strongly typed data, but we won't be taking advantage of that. Instead, each top-level JSON object will have a special property called entity that will contain the type of the database entity as a string. This way, when we search for all users for example, we'll be searching for all JSON objects with property entity="user".

There are many reasons to go for REST+AJAX rather than, say, servlets. I hardly feel the need to justify it  - it's stateless, you don't have to deal with dispatching, you just design an API, more responsive, we're in 2013 soon after all. The use of JSR 311 allows us to switch server implementations easily. It's pretty well-designed: you annotate your classes and methods with the URI paths they must be invoked for. Then a method's parameters can be bound either to portions of a URI, or to HTTP query parameters or form fields etc.

I'm not sure yet what the REST services will be exactly, but the idea is to keep them very generic so the core could be just plugged for another webapp and writing future applications could be entirely done in JavaScript.

Project Layout

The root folder contains the SBT build file build.sbt, a project folder with some plugin configurations for SBT and a src folder that contains all the code following Maven naming conventions which SBT adopts. The src/main/html and src/main/javascript folders contain the web application. When you run the server with all default options, that's where it serves up the files from. This way, you can modify them and just refresh the page.  Then src/main/scala contains our program and src/main/java some code for Java programmers to look at and copy & paste. The main point of the Java code is really to help people that want to use all those cool libraries but prefer to code in Java instead.

To load the project in Eclipse,  use SBT to generate project files for you. Here's how:

1. cd evalhalla
2. sbt
3. eclipse
4. exit

Then you'll have a .project and a .classpath file in the current directory, so you can go to your Eclipse and just do "Import Project". Make sure you've run the code before though, in order to force SBT to download all dependencies.

Code Overview

Ok, let's take a look at the code now, all under src/main. First, look at html/index.html, which gets loaded as the default page. It contains just a login form and the interesting part is the function eValhallaController($scope, $http). This function is invoked by AngularJS due to the ng-controller attribute in the body tag. It provides the data model of the HTML underneath and also a login button event handler, all through the $scope parameter. The properties are associated with HTML element via ng-model and buttons to functions with ng-click. An independent tutorial on AngularJS, one of few since it's pretty new, can be found here.

The doLogin posts to /rest/user/login. That's bound to the evalhalla.user.UserService.authenticate method (see user package). The binding is done through the standard JSR 311 Java annotations, which also work in Scala. I've actually done an equivalent version of this class in Java at  java/evalhalla/UserServiceJava. A REST service is essentially a class where some of the public methods represent HTTP endpoints. An instance of such a class must be completely stateless, a JSR 311 implementation is free to create fresh instances for each request. The annotations work by deconstructing an incoming request's URI into relative paths at the class level and then at the method level. So we have the @Path("/user") annotation (or @Path("/user1") for the Java version so they don't conflict).  Note the @Consumes and @Produces annotations at the class level that basically say that all methods in that REST service accept JSON content submitted and return back JSON results. Note further how the authenticate method takes a single Json parameter and returns a Json value. Now, this is mjson.Json and JSR 311 doesn't know about it, but we can tell it to convert to/from in/output stream. This is done in the java/evalhalla/JsonEntityProvider.java class (which I haven't ported to Scala yet). This entity provider and the REST services themselves are plugged into the framework at startup, so before examining the implementation of authenticate, let's look at the startup code.

The Start.scala file contains the main program and the JSR 311 eValhalla application implementation class. The application implementation is only required to provide all REST services as a set of classes that the JSR 311 framework introspects for annotations and for the interfaces they implement. So the entity converter mentioned above, together with both the Scala and Java version of the user service are listed there. The main program itself contains some boilerplate code to initialize the Restlet framework and asks it to serve up some files from the html and javascript folders and it also attaches the JSR 311 REST application under the 'rest' relative path.

An important line in main is evalhalla.init(). This initializes the evalhalla package object defined in scala/evalhalla/package.scala. This is where we put all application global variables and utility methods. This is where we initialized the HyperGraphDB instance. Let's take a closer look. First, configuration is optionally provided as a JSON formatted file, the only possible argument to the main program. All properties of that JSON are optional and have sensible defaults. With respect to deployment configuration, there are two important locations: the database location and the web resources location. The database location, specified with dbLocation, is by default taken to be db under the working directory, from where the application is run. So for example if you've followed the above instructions to run the application from the SBT command prompt for the first time, you'd have a brand new HyperGraphDB instance created under your EVALHALLA_HOME/db. The web resources served up (html, javascript, css, images) are configured with siteLocation the default being src/main so you can modify source and refresh. So here is how the database is created. You should be able to easily follow Scala code even if you're a mainly Java programmer.

    val hgconfig = new HGConfiguration()
    hgconfig.getTypeConfiguration().addSchema(new JsonTypeSchema())
    graph = HGEnvironment.get(config.at("dbLocation").asString(), hgconfig)
    registerIndexers
    db = new HyperNodeJson(graph)

Note that we are adding a JsonTypeSchema to the configuration before opening the database. This is important for the mJson storage implementation that we are mostly going to rely on. Then we create the graph database, create indices (for now just an empty stub) and last but not least create an mJson storage view on the graph database - a HyperNodeJson instance. Please take a moment to go through the wiki page on HGDB-mJson. The graph and db variables above are global variables that we will be accessing from everywhere in our application. 

Some other points of interest here are the utility methods:

  def ok():Json = Json.`object`("ok", True);

  def ko(error:String = "Error occured") = Json.`object`("ok", False, "error", error);

Those are global as well and offer some standard result values from REST services that the client side may rely on. Whenever everything went well on the server, it returns an ok() object that has a boolean true ok property. If something went wrong, the ok boolean of the JSON returned by a REST call is false and the error property provides an error message. Any other relevant data, success or failure, is embedded with those ok or ko objects. 

Lastly, it is common to wrap pieces of code in transactions. After all, we are developing a database backed applications and we want to take full advantage of the ACID capabilities of HyperGraphDB. Scala makes this particularly easy because it supports closures. So we have yet another global utility method that takes a closure and runs it as a HGDB transaction:

  def transact[T](code:Unit => T) = {

    try{

    graph.getTransactionManager().transact(new java.util.concurrent.Callable[T]() {

      def call:T = {

        return code()

      }

    });

    }

    catch { case e:scala.runtime.NonLocalReturnControl[T] => e.value}

  }

This will always create a new transaction. Because BerkeleyDB JE, which is the storage engine by default as of HyperGraphDB 1.2, doesn't supported nested transaction, one must make sure the transact is not called within another transaction. So when we are in a situation where we want to have a transaction and we'd happily be embedded in some top-level one, we can call another global utility function: ensureTx, which behaves like transact except it won't create a new transaction if one is already in effect.

Ok, armed with all these preliminaries, we are now able to examine the authenticate method:

    @POST

    @Path("/login")

    def authenticate(data:Json):Json = {

        return evalhalla.transact(Unit => {

            var result:Json = ok();

            var profile = db.retrieve(jobj("entity", "user", 

                        "email", data.at("email").asString().toLowerCase()))

            if (profile == null) { // automatically register user for now         

              val newuser = data.`with`(jobj("entity", "user"));

              db.addTopLevel(newuser);

            }

            else if (!profile.is("password", data.at("password")))

                result = ko("Invalid user or password mismatch.");

            result;   

        });

    }

The @POST annotation means that this endpoint will be matched only for an HTTP post method. First we do a lookup for the user profile. We do this by pattern matching. We create a Json object that first identifies that we are looking for an object of type user by setting the entity property to "user". Then we provide another property, the user's email which we know is supposed to be unique so we can treat it as a primary key. However, note that neither HyperGraphDB nor its Json storage implementation provides some notion of a primary other than HyperGraphDB atom handles. The HyperNodeJson.retrieve method returns only the first object matching the pattern. If you want an array of all objects matching the pattern use HyperNodeJson.getAll. Note the 'jobj' method call in there: this is a rename in the import section of the Json.object factory method. It is necessary because in Scala object is a keyword. Another way to use a keyword as a method name in Scala beside import rename, on can wrap it in backquotes ` as is done with data.`with` above which is basically an append operation, merging the properties of one Json object into another. The db.addTopLevel is explained in the HGDB-mJson wiki. Also, you may want to refer to the mJson API Javadoc. One last point though about the structure of the authenticate method: there are no local returns. The result variable contains the result and it is written as the last expression of the function and therefore returned as the result. I like local returns actually (i.e. return statement in the middle of the method following if conditions or within loops or whatever), but the way Scala implements them is by throwing a RuntimeException. However, this exception gets caught inside the HyperGraphDB transaction which has a catch all clause and treats exceptions as a true error conditions rather then some control flow mechanism.  This can be fixed inside HyperGraphDB, but avoiding local returns is not such a bad coding practice anyway.

Final Comments

Scala is new to me so take my Scala coding style with a grain of salt. Same goes with AngularJS. I use Eclipse and the Scala IDE plugin from update site  http://download.scala-ide.org/releases-29/stable/site (http://scala-ide.org/download/nightly.html#scala_ide_helium_nightly_for_eclipse_42_juno for Eclipse 4.2). Some of the initial Scala code is translated from equivalent Java code from other projects. If you haven't worked with Scala, I would recommend giving it a try. Especially if, like me, you came to Java from a richer industrial language like C++ and had to give up a lot of expressiveness.

I'll resist the temptation to make this into an in-depth tutorial of everything used to create the project. I'll say more about whatever felt not that obvious and give pointers, but mostly I'm assuming that the reader is browsing the relevant docs alongside reading the code presented here. This blog is mainly a guide.

In the next phase, we'll do the proverbial user registration and put in place some security mechanisms.

eValhalla Kick Off

[Next in this series eValhalla Setup]

As promised in this previous blog post, I will now write a tutorial on using the mJson-HGDB backend for implementing REST APIs and web apps. This will be more extensive than originally hinted at. I got involved in a side project to implement a web site where people can post information about failed government projects. This should be pretty straightforward so a perfect candidate for a tutorial. I decided to use that opportunity to document the whole development in the form of blog series, so this will include potentially useful information for people not familiar with some of the web 2.0 libraries such as jQuery and AngularJS which I plan to use. All the code will be available in GitHub. I am actually a Mercurial user, something turned me off from Git when I looked at it before (perhaps just its obnoxious author), but I decided to use this little project as an opportunity to pick up a few new technologies. The others will be Scala (instead of Java) and AngularJS (instead of Knockoutjs).

About eValhalla

Valhalla - the hall of Odin into which the souls of heroes slain in battle and others who have died bravely are received.

The aim is to provide a forum for people involved in (mainly software) projects within government agencies to report anonymously on those projects' failures. Anybody can create a login, without providing much personal information and be guaranteed that whatever information is provided remains confidential if they so choose. Then they can describe projects they have insider information about and that can be of interest to the general public. Those projects could be anything from small scale, internal-use only, local government, to larger-scale publicly visible nation-level government projects.

I won't go into a "mission statement" type of description here. You can see it as a "wiki leaks" type transparency effort, except we'd be dealing with information that is in the public domain, but that so far hasn't had an appropriate outlet. Or you can see it as a fun place to let people vent their frustrations about mis-management, abuses, bad decisions, incompetence etc. Or you can see it as a means to learn from experience in one particular type of software organization: government IT departments. And those are a unique breed. What's unique? Well, the hope is that such an online outlet will make that apparent.

Requirements Laundry List

Here is the list of requirements, verbatim as sent to me by the project initiator:

• enter project title
• enter project description
• enter project narrative
• enter location
• tag with failure types
• tag with subject area/industry sector
• tag with technologies
• enter contact info
• enter project size
• enter project time frame (year)
• enter project budget
• enter outcome (predefined)
• add lessons learned
• add pic to project
• ability to comment on project
• my projects dashboard (ability to add, edit, delete)
• projects can be saved as draft and made public later
• option to be anonymous when adding specific projects
• ability to create profile (username, userpic, email, organization, location)
• ability to edit and delete profile
• administrator ability to feature projects on main page
• search for projects based on above criteria and tags
• administrator ability to review projects prior to them being published

Nevermind that the initiator in question is currently pursuing a Ph.D. in requirements engineering. Those are a good enough start. We'll have to implement classic user management and then we have our core domain entity: a failed project, essentially a story decorated with various properties and tags, commented on. As usualy, we'd expect requirements to change as development progresses, new ideas will popup, old ideas will die and force refactorings etc. Nevermind, I will maintain a log of those development activities and if you are following, do not expect anything described to be set in stone.

Architecture

Naturally, the back-end database will be HyperGraphDB with its support of plain JSON-as-a-graph storage as described here. We will also make use of two popular JavaScript libraries: jQuery and AngularJS as well as whatever related plugins come in handy.

Most of the application logic will reside on the client-side. In fact, we will be implementing as much business logic in JavaScript as security concerns allow us. The server will consist entirely of REST services based on the JSR 311 standard so they can be easily run on any of the server software supporting that standard. To make this a more or less self-contained tutorial, I will be describing most of those technologies and standards along the way, at least to the extent that they are being used in our implementation. That is, I will describe as much as needed to help you understand the code. However, you need familiarity with Java and JavaScript  in order to follow.

The data model will be schema-less, yet our JSON will be structured and we will document whenever certain properties are expected to be present and we will follow conventions helps us navigate the data model more easily.

Final Words

So stay tuned. The plan is to start by setting up a development environment, then implement the user management part, then submission of new projects (my project dashboard), online interactions, search, administrative features to manage users, the home page etc.

On Testing

More than decade ago, I spend a year doing quality assurance at a big and successful smart card company. It was one of the more intellectually stimulating jobs I've had in the software industry and I ended up developing a scripting language, sadly long lost, to do test automation. Doing testing right can be much harder than writing the software being tested. Especially when you're after 100% quality as is the case with software burned on the chips of millions of smart cards that would have to be thrown away in case of a serious bug discovered post-production. Companies aiming at this level of quality get ISO 900x certified to show off to clients. To get certified, they have to show a QA process that guarantees, to an acceptable degree of confidence, that products delivered work, that the organization is solid, knowledge is preserved etc. etc. The interesting part that I'd like to share with you is the specific software QA approach. It did involve an obscene amount of both documentation and software artifacts that had to be produced in a very rigid formal setting, but the philosophy behind spec-ing out the tests was sound, practical and better than anything I've seen since. 

Dijkstra famously said that testing can only prove the presence of errors, never the absence of errors. True that. To have 100% guarantee that a program works, one would need to produce a mathematical proof of its correctness. Perhaps not sufficient...as Knuth not less famously noted, when sending a program to a colleague, that the program must be used with caution because he only proved it correct, but never tested it. In either case, ultimately the goal is to gain confidence in the quality of a piece of software. We do that by presenting a strong, very, very convincing argument that the program works. 

When discussing testing methodology people generally talk about automated vs. manual testing, test-driven development where test cases are developed before the code or "classic" testing where they are done after development, but rarely do I see people mindful of how tests should be specified. The term test itself is used rather ambiguously to mean the action of testing, or the specification or the process or the development phase. And in some contexts a test means a test case which refers to an input data set, or it refers to an automated program (e.g. a jUnit test case). So let's agree that, whether you code it up or do it manually, a test case consists of a sequence of steps taken to interact with the software being tested and verify the output with the goal of ensuring that said software behaves as expected. So how do you go about deciding what this sequence of steps should be? In other words, how do you gather test requirements? 

Think of it in dialectical terms - you're trying to convince a skeptic that a program works correctly. First you'd have to agree what it means for that program to work correctly. Well, they say, it must match the requirements. So you start by reading all requirements and translating that last statement ("it must match the requirements" ) for each one of them into a corresponding set of test criteria. Naturally, the more detailed the requirements are, the easier that process is. In an agile setting, you might be translating user stories into test criteria. Let's have a simple running example:

Requirement:

Login form should include a captcha protection

Test Criteria:

• C1 - the login form should display a string as an image that's hard to recognize by a program.
• C2 - the login form should include an input field that must match the string in the captcha image for login to succeed. 

Notice how the test criteria explicitly state under what conditions one can say that a program works. One can list more criteria with further detail, stating what happens if the captcha doesn't match. What happens after n number of repeats etc. Also, this should make it clear that test criteria are not actual tests. They are not something that can be executed (manually or automatically). In fact, they are to a test program what requirements are to the software being QA-ed. And as with conventional requirements, the more clear you are on your test criteria, the better chance you have in developing adequate tests. 

The crucial point is that when you write a test case, you want to make sure that it is with a well-defined purpose, that it serves as a demonstration that an actual test criterion has been met. And this is what's missing in 90% of testing efforts (well, to be sure this is just anecdotal evidence). People write or perform tests simply for the sake of trying out things. Tests accumulate and if you have a lot of them, it makes it look like you're in good shape. But that's not necessarily the case because tests can only prove the presence of errors, not their absence. To convince your dialectical opponent of the absence of errors, given the agreed upon list of criteria, you'd have to show how your tests prove that the criteria have been met. In other words, you want to ensure that all your test criteria have been covered by appropriate test cases - for each test criterion there is at least one test case that, when successful, shows that this criterion is satisfied. A convenient way to do that is to create a matrix where you list all your criteria in the rows and all your test cases in the columns and checkmark a given cell whenever the test case covers the corresponding criterion, where "covers" means that if the test case succeeds one can be confident that the criterion is met. This implies that the test case itself will have to include all necessary verification steps. Continuing with our simple example, suppose you've developed a few test cases:

• T1 - test succesful login
• T2 - test failed login for all 3 fields, bad user, bad password, bad captcha
• T3 - test captcha quality by running image recognition algos on captcha

	T1	T2	T3	T4	T5	...	...
C1			X
C2	X	X
...

A given test case may cover a certain aspect of the program, but you'd put a checkmark only if it actually verifies the criteria in question. For instance T3 would be loading a login page, but it won't be testing actual login. Similarly, T1 and T2 can observe the captcha, but they won't evaluate its quality. It may appear a bit laborious as an approach. In the aforementioned company, this was all documented ad nauseam. Criteria were classified as "normal", "abnormal", "stress" and what not, reflecting different types of expected behaviors and possible execution contexts. Now, I did warn you - this was a QA process aimed at living up to ISO standards. And it did. But think about the information this matrix provides you. It is a full, detailed spec of your software. It is a full inventory of your test suite. It tells what part of the program is being tested by what test. It shows you immediately if some criteria are not being covered by a test, or not covered enough. If shows you immediately if some criteria are being covered too much, i.e. if some tests are superfluous. When tests fail, it tells you exactly what behaviors of the software are not functioning properly. Recall that one of the main problems with automated testing is the explosion of code that needs to be written to achieve descent coverage. This matrix can go a long way to controlling that code explosion by keeping each test case with a relatively unique purpose. Most importantly, the matrix presents a pretty good argument for the program's correctness - you can see at a glance both how correctness has been defined (the list of criteria) and how it is demonstrated (the list of tests cross-referenced with criteria).

Reading about testing even from big industry names, I have been frequently disappointed at the lack of systematic approach to test requirements. In practice it's even worse. Developers, testers, business people in general have no idea what they are doing when testing. This includes agile teams where tests are sometimes supposed to constitute the specification of the program. That's plain wrong, first because it's code and code is way too low-level to be understood by all stakeholders, hence it can't be a specification that can be agreed upon by different parties. Second, because usually the same people write both the tests and the program tested, the same bugs sneak in both places and never get discovered, the same possibly wrong understanding of the desired behavior is found in both places. So expressing the quality argument (i.e. with the imaginary dialectical adversary) simply in the form of test cases can't cut it. 

That said, I wouldn't advocate following the approach outlined above verbatim and in full detail. But I would recommend having the mental picture of that Criteria x Tests matrix as guide to what you're doing. And if you're building a regression test suite, and especially if some of the tests are manual, it might be worth your while spelling it out in the corporate wiki somewhere.

Cheers,

Boris

JSON Storage in HyperGraphDB

JSON (http://json.org) came about as a convenient, better-than-XML data format that one could directly work from in JavaScript.  About a year ago, I got a bit disappointed by the JSON libraries out there. JSON is so simple, yet all of them so complicated, so verbose. Most of it comes from the culture of strong typing in Java and from the presumed use of JSON on the server as an intermediate representation to be mapped to Java beans, where the application domain is usually modeled. But JSON is powerful enough on its own if you are willing to trade off type safety for flexibility. So I wrote mJson (for "minimal" Json), a single source file library for working with JSON from Java. For a description see the blog posts:

• http://sharegov.blogspot.com/2011/06/json-library.html
• http://sharegov.blogspot.com/2011/11/mjson-11-released.html

Using this library, I've been able to avoid creating the usual plethora of Java classes to work with my domain in several applications. Coding with it is pretty neat. One can pretty much view JSON as a general minimalistic, highly flexible modeling tool, a bit like s-expressions or any general enough abstract data structure (another example are first-order logic terms). 

Now, there's a persistence layer for those JSON entities based on HyperGraphDB. Unlike "document-oriented" databases, the representation in HyperGraphDB is really graph-like with all the expected consequences. It is described in the HyperGraphDB Json Wiki Page, pretty stable, convenient and fun to work with. 

If time permits, I will write a few posts in the form of a tutorial to show how to quickly build database backed JSON REST services with mJson and HyperGraphDB. If you have a suggestion of an application domain to cover, please share it in a comment!

In the meantime, I invite you to give it a try! 

Regards,

Boris

HyperGraphDB 1.2 Beta now available

Kobrix Software is pleased to announce the release of HyperGraphDB version 1.2.

HyperGraphDB is a general purpose, free open-source data storage mechanism. Geared toward modern applications with complex and evolving domain models, it is suitable for semantic web, artificial intelligence, social networking or regular object-oriented business applications.

This release contains numerous bug fixes and improvements over the previous 1.1 release. A fairly complete list of changes can be found at the Changes for HyperGraphDB, Release 1.2 wiki page.

1. Introduction of a new HyperNode interface together with several implementations, including subgraphs and access to remote database peers. The ideas behind are documented in the blog post HyperNodes Are Contexts.
2. Introduction of a new interface HGTypeSchema and generalized mappings between arbitrary URIs and HyperGraphDB types.
3. Implementation of storage based on the BerkeleyDB Java Edition (many thanks to Alain Picard and Sebastian Graf!). This version of BerkeleyDB doesn't require native libraries, which makes it easier to deploy and, in addition, performs better for smaller datasets (under 2-3 million atoms).
4. Implementation of parametarized pre-compiled queries for improved query performance. This is documented in the Variables in HyperGraphDB Queries blog post.

HyperGraphDB is a Java based product built on top of the Berkeley DB storage library.

Key Features of HyperGraphDB include:

• Powerful data modeling and knowledge representation.
• Graph-oriented storage.
• N-ary, higher order relationships (edges) between graph nodes.
• Graph traversals and relational-style queries.
• Customizable indexing.
• Customizable storage management.
• Extensible, dynamic DB schema through custom typing.
• Out of the box Java OO database.
• Fully transactional and multi-threaded, MVCC/STM.
• P2P framework for data distribution.

In addition, the project includes several practical domain specific components for semantic web, reasoning and natural language processing. For more information, documentation and downloads, please visit the HyperGraphDB Home Page.

Variables in HyperGraphDB Queries

Introduction
A feature that has been requested on a few occasions is the ability to parametarize HyperGraphDB queries with variables, sort of like the JDBC PreparedStatement allows. That feature has now been implemented with the introduction of named variables. Named variables can be used in place of a regular condition parameters and can contain arbitrary values, whatever is expected by the condition. The benefits are twofold: increase performance by avoiding to recompile queries where only a few condition parameters change and a cleaner code with less query duplication. The performance increase of precompiled queries is quite tangible and shouldn't be neglected. Nearly all predefined query conditions support variables, except for the TypePlusCondition which is expanded into a type disjunction during query compilation and therefore cannot be easily precompiled into a parametarized form. It must also be noted that some optimizations made during the compilation phase, in particular related to index usage, can't be performed when a condition is parametarized. A simple example of this limitation is a parameterized TypeCondition - indices are defined per type, so if the type is not known during query analysis, no index will be used.

The API
The API is designed to fit the existing query condition expressions. A variable is created by calling the hg.var method and the result of that method passed as a condition parameter. For example:

HGQuery<HGHandle> q = hg.make(HGHandle.class, graph).compile(
    hg.and(hg.type(typeHandle),hg.incident(hg.var("targetOfInterest"))));

This will create a query that looks for links of specific type and that point to a given atom, parameterized by the variable "targetOfInterest". Before running the query, one must set a value of the variable:

q.var("targetOfInterest", targetHandle);
q.execute();

It is also possible to specify an initial value of a variable as the second of the hg.var method:

q = hg.make(HGHandle.class, graph).compile(
    hg.and(hg.type(typeHandle),hg.incident(hg.var("targetOfInterest", initialTarget))));
q.execute();

Note the new hg.make static method: it takes the result type and the graph instance and returns a query object that doesn't have a condition attached to it yet. To attach a condition, one must call the HGQuery.compile method immediately after make. This version of make establishes a variable context attached to the newly constructed query. All query conditions constructed after the call to make and before the call to compile will implicitly assume variables belong to that context. That is why to avoid surpises you should call compile right after make.

Once a query is thus created, one can execute it many times by assigning new values to the variables through the hg.var method as shown above.

The Implementation

The requirement of calling HGQuery.compile right of the make method comes from the fact that the existing API constructs conditions in a static environment. The condition is fully constructed before it is passed to the compile method. So to make a variable context available during the condition construction process (the evaluation of the query condition expression), we do something relatively unorthodox here and attach that context (essentially a name/value map) as a thread local variable in the make method. The alternative would have been creating a traversal of the condition expression that collects all variables used within them. Either that traversal process would have to know about all condition types, or the HGQueryCondition would have had to be enhanced with some extra interface for "composite conditions" and "variable used within a condition". I didn't like either possibility. Having a two step process of calling hg.make(...).compile(....) seems clean and concise enough.

Variables are implemented through a couple of new interfaces: org.hypergraphdb.util.Ref, org.hypergraphdb.util.Var. When a condition is created with a constant value (instead of a variable), the org.hypergraphdb.util.Constant implementation of the Ref interface is used. All conditions now contain Ref<T> private member variable where before they contained a member variable of type T.  I won't say more about those reference abstractions, except one should avoid using them, unless one is implementing a custom condition...they are considered internal.

On a side note, this idea of creating a reference abstraction essentially implements the age-old strategy of introducing another level of indirection in order to solve a design problem. I've used this concept in many places now, including for things like caching and dealing with complex scopes in bean containers (Spring), so I spend some time trying to create a more general library around this. Originally I intended to create this library as a separate project and make use of it in HyperGraphDB. But I didn't come up with something satisfactory enough, so instead I created the couple of interfaces mentioned above. However, eventually those interfaces and classes may be replaced by a separate library and ultimately removed from the HyperGraphDB codebase.

HyperNodes Are Contexts

There are a couple of different items on HyperGraphDB's road map that, upon a little reflection, seem to converge on a single abstraction. The abstraction I would call hypernode following the hypernode model as described by the paper A Graph-Based Data Model and its Ramifications though it remains to be seen how much of that original model applies in the HyperGraphDB context. The items are the following: (1) local proxies to remote database instances; (2) RAM-only atoms; (3) nested graphs. This blog is about laying the design space of how those features should be dealt with. Let's examine each of these future features in order.

[1] Local DB Proxies

It would be nice to be able to access a db instance on some remote machine as if it were a local db. Only local databases can be currently opened and there is a good portion of the API and the way it is used that could work all the same when the data is remote. One could imagine opening remote graphs like this:

HyperGraph remoteGraph = HGEnvironment.get("peer:RemotePeerName");

and then work with it as if it was on the local hard-drive. This almost makes sense. Most API objects dealing with database access and management, such as the HyperGraph instance itself, the index manager, type system, the low-level store could be manipulated remotely with the exact same semantics. However, this would be a real stretch of their original intent. For example, access to low-level storage is meant to support type implementations, in particular predefined types. Would you want a type implementation at machine A to manage storage on machine B? Similarly for the index manager or the event manager - would you want machine A to manage indexing at machine B? A lot of the methods of the HyperGraph class itself are overloaded methods whose sole purpose is simplifying some API calls by delegating to a "full version" of a method. In other words, going that route, we would have to make the whole API be RPC-ed, an ugly solution with a heavy workload and potentially an overkill. Incidentally, I'm curious if there's an instrumentation Java tool that would load a class-library, but transform dynamically every object as a local proxy to a remote instance. Anybody know of such a tool? Should be doable and perhaps useful for many projects... I only found this paper, which is pretty new and by the looks of the complexities and limitations involved, no wonder it hasn't been done before. Bottom line: remote access to database instance should be carefully crafted as a separate abstraction that focuses on what's important, an abstraction that is working at the atom level - CRUD operations, queries and traversals. A couple of design problems here:

(a) What would the interface to a remote instance look like?

(b) How to deal with atom serialization and differences in type systems? The latter problem is addressed to some extent in the current P2P framework.

(c) Does the client of a remote instance need a local database? The easy answer to that is "no, it shouldn't", but that might mean a much harder implementation!

[2] RAM-Only Atoms

In certain applications, it would be useful to work with a hypergraph structure that is not necessarily or entirely persisted on disk. For example, when HyperGraphDB is used as a convenient representation to apply some algorithms to, or when some data is transient and attached to a particular user session in a server-side environment. Or if one wants a client to a HGDB "server" as in the local db proxy described above. Hence it would be convenient to add atoms to the graph without storing them on disk. Such atoms will participate in the graph structure as full-fledged citizens - they would be indexed and queried in the normal way, except that they would only reside in the cache. For an implementation standpoint, the difficulty will be in merging a unified and coherent view of disk and RAM data. If RAM atoms are to be truly RAM only, databases indices cannot be used to index them. Hence, RAM-only indices must be maintained and dynamically intersected with disk indices during querying. Moreover, it would only make sense to be able to perform queries restricted to atoms in main memory.

[3] Nested Graphs/Subgraphs

This is what the hypernode model is more or less about. A hypernode is a node in a graph that is itself a graph, composed of atomic nodes and possibly other hypernodes. The generalization is roughly analogous to the generalization of standard graph edges to hyperedges. Thus we have graphs nested within graphs, recursively. A very natural application of the original hypernode model is nested object structures. Within HyperGraphDB, however, we already get nested value structures from the primitive storage graph and we are mostly interested in scoping.

As a side note, scoping and visibility are terms used in programming language theory and are sometimes confused because scoping usually determines the visibility of identifiers. A scope in programming is essentially the context within which things like variables, values and general expressions live (and have meaning/validity). When speaking about knowledge representation, the scoping problem is referred to as the "context problem" - how do you represent contextual knowledge? It is not unusual for the AI community to hijack such terms and basically strip them of their deeper meaning in order to claim a handle on a problem that is otherwise much more difficult, or simply sound sexier in a rather silly way. Contextuality and context-dependent reference resolution is at the core of all of computing (and hence knowledge representation), but that's the subject of another topic, perhaps a whole book that I might write if I become knowledgeable enough and if I happen to stumble upon more interesting insights. It is much deeper, I believe, than scopes and their nesting. Incidentally, another example of such an abused term is the word semantic as in the "semantic web" or "semantic relations" or "semantic search" or what have you. There's nothing semantic about those things, only actual computer programs are semantic in any meaningful sense of the word, and not the representation they work on.

Nevertheless, speaking of "context" when one means "scope" seems common so I'll use that term, albeit with great reluctance. To represent contextual information in HyperGraphDB, we need some means to state that a certain set of atoms "belongs to" a certain context. A given atom A can live in several different contexts at a time. One way to do that is to manage that set explicitly and say that a context is a set of atoms. Thus a context is a special entity in the database, an explicitly stored, potentially very large set of atoms. If that special entity is an atom in itself, then we have a nested graph, a hypernode. Another way would be to create an atom C that represents a context (i.e. a hypernode) and then link every member A of that context to C with a special purpose ContextLink. I think this is what they do in OpenCog's atomspace now. The two approaches have different implications. In the former, all atoms belonging to a context are readily available as an ordered set that can efficiently participate in queries, but given an atom there's no easy way to find all contexts it belongs to (clearly, we should allow for more than one). In the latter approach, getting all atoms in a context requires an extra hop from the ContextLink to the atom target, but then retrieving the contexts an atom belongs to is not much harder. In addition, if we maintain a TargetToTargetIndexer on ContextLinks, we avoid that extra hop of going from the context C to the ContextLink to the enclosed atom A. The choice between the two alternatives is not obvious. Going the ContextLink route has the clear advantage of building on top of what already exists. On the other hand, nested graphs seems something fundamental enough and close enough to a storage abstraction to deserve native support while a representation through "semantic" ContextLink should be perhaps left to application specific notions of contextuality, more complex or more ad hoc, regardless.

Note that if we had direct support for unordered links in HyperGraphDB, i.e. hyperedges as defined in mathematical hypergraphs, a nested graph context could simply be a hyperedge. Now that the HGLink interface is firmly established as a tuple, it will be hard to add such unordered set links from an API standpoint. However, support for unordered hypergraphs can be achieved through hypernodes-as-sets-of-atoms with their own interface. On this view, a hypernode can be seen either as an unordered link or as a nested graph. To be seen as an unordered link, however, implies that we'd have to maintain incidence sets to include both standard HGLinks and hypernodes. This in turn means we may run into trouble with the semantics of link querying: does hg.link(A) for example include only HGLinks pointing to A or hypernodes as well? If only links, then we'd have to filter out the hypernodes, thus degrading performance of existing queries. If hypernodes as well, existing queries that expect only links could break a runtime typecast. Issues to keep in mind...

Finally, note that this whole analysis takes atoms within nested graphs to be first and foremost members of the whole graph. The universe of atoms remains global and an atom remains visible from the global HyperGraph regardless of what nested graphs it belongs to. Hence a nested graph is more like a materialized subgraph. The alternative where each nested graph lives in its own key-value space would make it very hard to share atoms between nested graphs. So this limits the scoping function of nested graphs because a given HGHandle will always refer to the same entity regardless of what nested graph it belongs. To implement full-blown scoping, we'd need a HGHandle to refer to different things in different contexts. Do we want that capability? Should we reserve it for a higher-level where we are resolving actual symbolic names (like type names for example) rather than "low-level" handles? Perhaps it wouldn't be that hard to contextualize handles, with an extra performance cost of course: a hypernode would simply have a more involved 'get' and 'put' operations where the handle is potentially translated to another handle (maybe in another context) in a chain of reference resolutions ultimately bottoming out in the global handle space? But that issue is orthogonal to the ability to represent nested graphs.

Commonality

So what's common between those three features above? All of them are about a viewing a graph, or a portion thereof, that is not necessarily identical to the database stored on disk, yet it is a hypergraph in its own right and one wants to be able to operate within the context that it represents. There must be a common abstraction in there. Since the name HyperGraph is already taken by the database instance itself, I'd propose to use HyperNode. A HyperNode would strip down the essential operations of a the HyperGraph class, which would implement the HyperNode interface. This HyperNode interface will replace HyperGraph as the entry point to a graph, be it for querying, traversals or CRUD operations in many places.

So what API should a HyperNode offer? Here's a proposal:

• get, add, define, replace, remove atoms, but question is: only full versions of those methods or all overloaded versions?
• getIncidenceSet(atomHandle)
• getType(atomHandle)
• find(HGQuery)
• getLocation() - an abstract URI-like location identifying the HyperNode

Those are a bare minimum. Access to an index manager, event manager and cache are clearly outside of the scope of this abstraction. However, the question of transactions and the type system is a bit trickier. Being able to enclose operations within a transaction is usually important, but a remote peer might not want to support distributed transactions while local data (RAM or a nested graph) can be transacted upon from the main HyperGraph instance. As for access to the HGTypeSystem, it is mostly irrelevant except when you need it.

The semantics of HyperNode's operations seem intuitively well-defined: do whatever you'd do with a full HyperGraph except do it within that specific context. For example, an InMemoryHyperNode would add, get query etc. only the RAM-based atoms. Similarly a RemoteHyperNode would only operate on remote data. A NestedHyperNode is a bit harder to define: an add will modify the global database and mark the new atom as part of the nested graph, a query or a get will only return data that's marked as part of the nested graph; but what about a remove? should it just remove from the nest graph, or remove globally as well? or try to do the right thing as in "remove globally only if it's not connected to anything outside of its nested graph"?

Ok, enough. A brain dump of sorts, in need of comments to point out potential problems and/or encouragement that this is going on the right track :)

Cheers,

Boris