Importing SourceForge code into Apache for Jena

The Jena project now has the legal paperwork done for the vast majority of the codebase. It's now time to move the code from SourceForge, where's it's been for almost 10 years (the project was registered November 2001).

During that time, the SourceForge infrastructure has been excellent. We're not moving because of dissatisfaction but because we want to put the post-HP on a solid legal basis where the license and IP situation is well-understood and completely clear. We now have committers in 3 different organisations, and contributions from yet more - it's slowly getting more and more complicated.

The way Apache works is that software is granted to Apache, which grants Apache the right to re-license it. Any software you use from Apache is a license (with IP guarantees etc.) from Apache to you - not between you and the original contributor, so you can when use the software commercially and only need to check one Apache license.

Until now, we have had a setup where any contributions are simply incorporated with the license and conditions of the contributor. It so happens that all the licensed code in the codebase is the same BSD-type license but in using Jena you don't get a single license, you get one from every contributor. For some people who are going to depend on Jena for commercial use or long term big deployment, this matters. We've had a user crawl the codebase to check each of the licenses (as they should but it's just work). With Apache it's different - one license, well-understood legal situation.

Contributors grant software two ways - either a software grant document or when they upload code to a mailing list or to Jira. When you add something to Jira there's a tick box to say you are making the grant to Apache, otherwise while it may illustrate some issue, we can't use it in the codebase.

Apache use subversion so Jena needs to import the code base to svn.

Subversion or git or Mercurial ...

Aside: one question I've been asked is why not a DVCS like git or mercurial. Aapche use Subversion. As I understand it, there are legal matters to consider. Suppose A pushes code to B and B pushes to Apache. A has not necessarily granted the software to Apache - B could check but it's a new burden for B, and pushing to Apache is B's responsibility but B does not own A's contribution. Maybe this will change sometime but at the moment, DVCS works for direct contributor to user licensing (and the user "should" then check every license) but not the consolidation offered by Apache.

Process

Jena has three repositories, Jena in CVS, Jena in SVN and Joseki in CVS. There are active projects in all of them but theer is also a lot of history and legacy. We want to import everything as a record of ownerships, not just copy the latest working copy.

This is the process I have put together:

1. Grab the repositories

SourceForge offer rsync access for backup, with history (the tarballs are just the current state).

2. Convert CVS to SVN

We have a multi-project layout so cvs2svn needs some arguments.

#!/bin/bash
MODS="ARQ BRQL DataGenerator Eyeball EyeballAcceptance Scratch extras grddl gvs iri jena jena-perf jena2 modeljeb owlsyntax rdf-html sparql2sql
tutorial"

SVN=ASF-Jena-CVS   # Destination
CVS=../Jena-CVS    # Local rsync backup

for in $MODS
do
    echo "==== $m"
    #ARGS="--dry-run"
    ARGS="$ARGS --encoding=utf8 --encoding=iso-8859-1"
    # Create trunk/branshes/tag structure per project
    ARGS="$ARGS --trunk=$m/trunk --branches=$m/branches --tags=$m/tags"
    cvs2svn $ARGS --existing-svnrepos --svnrepos "$SVN" $CVS/$m
done

and much the same for Joseki except the modules list is just "Joseki1 Joseki3 Joseki3" and it is much faster.

Dry-run this first : it showed up two problems.

The "--encoding=utf8 --encoding=iso-8859-1" to to get the translation of some people's names right (non-ASCII characters).

A name clash in Joseki couldn't be resolved. Fortunately, it was with some old intermediate binaries so simply deleting from CVS (the joy of CVS using the filesystem layout) was simplest.

3. Dump the repositories

Use "svnadmin dump" and gzip the files. They are going to uploaded to an Apache machine and they are quite large - 3.1G to upload over from my home cable connection (1.5Mbit up).

4. Import to subversion

This step has been done by the Apache Infrastructure team as it requires svnadmin access to the respository. See INFRA-3628 for the details.

It's good to check it's going to do the right thing first. We now have the files for three repositories. We want the imported svn to look like:

   .../Import/Jena-CVS/...
   .../Import/Jena-SVN/...
   .../Import/Joseki-CVS/...

so we have a permanent record of the code state at the start of the Aapche svn. After import, active project can be "svn copy"ed out to give the working versions going forward.

To test it's going to work when the apache infrastrucure team so the actual import, I built a local repo in the same layout.

# ---- Create the layout in Apache repository
mkdir -p Layout/incubator/jena/Import/Joseki-CVS
mkdir -p Layout/incubator/jena/Import/Jena-CVS
mkdir -p Layout/incubator/jena/Import/Jena-SVN
svnadmin create ApacheRepo
svn import Layout/ file://$PWD/ApacheRepo -m "Set layout"
rm -rf Layout

then it's juts a matter of inserting the code in the right place:

# --- Imports
REPO=ApacheRepo

# Joseki-CVS
gzip -d < Imports/ASF-Joseki-CVS.svn.gz | \
     svnadmin load --parent-dir incubator/jena/Import/Joseki-CVS $REPO

# Jena-CVS
gzip -d < Imports/ASF-Jena-CVS.svn.gz | \
     svnadmin load --parent-dir incubator/jena/Import/Jena-CVS $REPO

# Jena-SVN
gzip -d < Imports/ASF-Jena-SVN.svn.gz | \
     svnadmin load --parent-dir incubator/jena/Import/Jena-SVN $REPO

The slow bits where csv2svn (it's not bad but it's not instant : an hour or so), the upload to Apache (a couple of hours) and the checking the "svnadmin load" (another couple of hours).

5. Extract working copies

We're keeping the imports unchanged as a record of the starting point at Apache (revision 1124118)

The whole process has been done now - Jena code at Apache

Updating RDF Lists with SPARQL

Something the SPARQL Working Group has been thinking about recently is updates to RDF lists.

RDF lists are hard to deal with because they are not first class objects in the RDF data model. Instead they are "encoded" in triples. The encoding using a cons cell like structure whereby each element of the list is a blank node (not necessary a blank node but it nearly always is).

RDF lists are correctly called "RDF collections" but as it's the list-nature (elements in order) that matters, I'll call them lists in this blog.

Turtle and SPARQL has syntax for lists, but it's only surface syntax, and there are really triples in the RDF graph:

@prefix :  .
:x :p (1 2 3) .

is the RDF:

:x    :p         _:b0 .
_:b0  rdf:first  1 .
_:b0  rdf:rest   _:b1 .
_:b1  rdf:first  2 .
_:b1  rdf:rest   _:b2 .
_:b2  rdf:first  3 .
_:b2  rdf:rest   rdf:nil

RDF toolkits help by presenting lists as progamming language lists. This also helps in keeping the lists well formed. In all those triples, there is one rdf:rest and one rdf:first per list element - but it's legal RDF to have several uses of the properties, or none, on one subject.

As an addition quirk, the empty list isn't any RDF triples, so looking for lists isn't just looking for rdf:rest properties.

@prefix :  .
:x :p () .

is the RDF:

:x :p rdf:nil .

Lists, Property Paths and Update

SPARQL 1.1 Query adds property paths, which make working with lists a bit easier, but it's not perfect. List elements do not necessarily come out in order.

{ :list rdf:rest*/rdf:next ?element }

But what about SPARQL 1.1 Update? How can we work with RDF lists? Here are some scripts for list operations. By using property paths they work on arbitrary length lists.

• Add an element to the start of a list
• Add an element to the end of a list
• Delete the element at the start of a list
• Delete an element to the end of a list
• Delete the whole list (version 1 - common case)
• Delete the whole list (version 2 - more general case)

All the scripts are self-contained - they include tests data.

They are examples - they aren't necessarily fully general, for example, if lists are badly formed or the property :p is also used to relate the subject to things that aren't lists. The last example shows a way to address that by finding and marking relavent points in the graph, doing some work and going back and tidying up. The graph updated is also being used as a scratch pad.

Add an element to the start of a list

PREFIX :    <http://example/> 
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 

INSERT DATA {
  :x0 :p () .
  :x1 :p (1) .
  :x2 :p (1 2) .
  :x3 :p (1 2 3) .
} ;

DELETE { ?x :p ?list }
INSERT { ?x :p [ rdf:first 0 ; 
                 rdf:rest ?list ]
       }
WHERE
{
  ?x :p ?list .
}

This one is relatively easy. Find the list start ?x :p ?list, which works whether the list is zero length or already has elements, delete the old triple that connected to the start of the list, put in a new cons cell (the [...]) at the start, and link to it.

Add an element to the end of a list

PREFIX :    <http://example/> 
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 

INSERT DATA {
  :x0 :p () .
  :x1 :p (1) .
  :x2 :p (1 2) .
  :x3 :p (1 2 3) .
} ;

# The order here is important.
# Must do list >= 1 first.

# List of length >= 1
DELETE { ?elt rdf:rest rdf:nil }
INSERT { ?elt rdf:rest [ rdf:first 98 ; rdf:rest rdf:nil ] }
WHERE
{
  ?x :p ?list .
  # List of length >= 1
  ?list rdf:rest+ ?elt .
  ?elt rdf:rest rdf:nil .
  # ?elt is last cons cell
} ;

# List of length = 0
DELETE { ?x :p rdf:nil . }
INSERT { ?x :p [ rdf:first 99 ; rdf:rest rdf:nil ] }
WHERE
{
   ?x :p rdf:nil .
}

This is a bit harder - there are two cases, lists of length 0 and lists of length one or more. The element before the insertion point needs changing and that can be a cons cell (list length >= 1) or the empty list (the triple pointing to it).

Do the lists of length one or more first, otherwise the adding to a list of length zero will be caught again by the adding to a list of length one.

For a list of length 1 or more: find the last element. The WHERE finds ?elt by finding all elements of the list rdf:rest+, and checking it's the last element by looking for ?elt rdf:rest rdf:nil.

Then delete the rdf:rest, and insert the new cons cell [ rdf:first 98 ; rdf:rest rdf:nil ].

For a list of length 0, the style is the same but the finding the triple to delete-insert to attch the cons cell is different.

Delete the element at the start of a list

PREFIX :      <http://example/> 
PREFIX rdf:   <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 

INSERT DATA {
  :x3 :p (1 2 3) .
  :x2 :p (1 2) .
  :x1 :p (1) .
  :x0 :p () .
} ;

DELETE { 
   ?x :p ?list .
   ?list rdf:first ?first ;
         rdf:rest  ?rest }
INSERT { ?x :p ?rest }
WHERE
{
  ?x :p ?list .
  ?list rdf:first ?first ;
        rdf:rest ?rest .
}

This can be done in one step - we are not interested in lists of length 0 because they have no element to delete. So find the pattern at the start of the list, delete it (note the WHERE pattern and DELETE template are the same), and insert the new triple that links the list directly to the previous rdf:rest.

Delete the element at the end of a list

PREFIX :     <http://example/> 
PREFIX rdf:  <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 

INSERT DATA {
  :x3 :p (1 2 3) .
  :x2 :p (1 2) .
  :x1 :p (1) .
  :x0 :p () .
} ;

# List of length 1
# Do before other lists.

DELETE { ?x :p ?elt .
         ?elt  rdf:first ?v .
         ?elt  rdf:rest  rdf:nil .
       }
INSERT { ?x :p rdf:nil . }
WHERE
{
  ?x :p ?elt .
  ?elt rdf:first ?v ;
       rdf:rest rdf:nil .
} ;

# List of length >= 2
DELETE { ?elt1 rdf:rest ?elt .
         ?elt  rdf:first ?v .
         ?elt  rdf:rest  rdf:nil .
       }
INSERT { ?elt1 rdf:rest rdf:nil }
WHERE
{
  ?x :p ?list .
  ?list rdf:rest* ?elt1 .

  # Second to end.
  ?elt1 rdf:rest ?elt .
  # End.
  ?elt rdf:first ?v ;
       rdf:rest rdf:nil .
}

The cases to consider are lists of exactly one and lists of two or more elements. It's the treatment of the element before the element we're deleteing that is different.

The style is the same though - find the place before the deleting, and the delete that cons cell.

For the list of length 2 or more, rdf:rest* is used which, is all elements including the ?list case of zero steps - then the structure beyond that is tested for being the end. There are 2 rdf:rest uses in the test for the end, hence list of length 2 or more.

Delete the whole list (common case)

PREFIX rdf:  <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 
PREFIX :     <http://example/> 

INSERT DATA {
:x0 :p () .
:x0 :q "abc" .

:x1 :p (1) .
:x1 :q "def" .

:x2 :p (1 2) .
:x2 :q "ghi" .
} ;

# Delete the cons cells.
DELETE
    { ?z rdf:first ?head ; rdf:rest ?tail . }
WHERE { 
      [] :p ?list .
      ?list rdf:rest* ?z .
      ?z rdf:first ?head ;
         rdf:rest ?tail .
      } ;

# Delete the triples that connect the lists.
DELETE WHERE { ?x :p ?z . }

This version is not fully general because it assume that :p is a link to the list and not also to any other RDF terms (non-lists) which we would want to keep.

The first DELETE finds and removes all cons cells. The second DELETE removes the triple with :p connecting the list to the subject.

Delete the whole list (general case)

PREFIX rdf:  <http://www.w3.org/1999/02/22-rdf-syntax-ns#> 
PREFIX :     <http://example/> 

INSERT DATA {
:x0 :p () .
:x0 :p "String 0" .
:x0 :p [] .

:x1 :p (1) .
:x1 :p "String 1" .
:x1 :p [] .

:x2 :p (1 2) .
:x2 :p "String 2" .
:x2 :p [] .

# A list not connected.
(1 2) .

# Not legal RDF.
# () .

} ;

INSERT { ?list :deleteMe true . }
WHERE {
   ?x :p ?list . 
   FILTER (?list = rdf:nil || EXISTS{?list rdf:rest ?z} )
} ;

# Delete the cons cells.
DELETE
    { ?z rdf:first ?head ; rdf:rest ?tail . }
WHERE { 
      [] :p ?list .
      ?list rdf:rest* ?z .
      ?z rdf:first ?head ;
         rdf:rest ?tail .
      } ;

# Delete the marked nodes
DELETE 
WHERE { ?x :p ?z . 
        ?z :deleteMe true . 
} ;

## ------
## Unconnected lists.

DELETE
    { ?z rdf:first ?head ; rdf:rest ?tail . }
WHERE { 
      ?list rdf:rest ?z2 .
      FILTER NOT EXISTS { ?s ?p ?list }
      ?list rdf:rest* ?z .
      ?z rdf:first ?head ;
         rdf:rest ?tail .
      } 

Deep breath.

This one is quite long.

The first step is to find and mark all the triples from a subject to a list via :p. We will need to delete at the end of the process but the property might also be used for non-lists and after the middle DELETE step all evidence of the lists is lost. The test:

    FILTER (?list = rdf:nil || EXISTS{?list rdf:rest ?z} )

catches both zero length lists and lists with elements.

Second step: delete all list elements, any subjects with properties rdf:first and rdf:rest.

Third step: remove the connecting triples and the markers.

Finally, we delete any lists where the start isn't connected to anything, which is the

    FILTER NOT EXISTS { ?s ?p ?list }

test.

License and Copyright

This page and the SPARQL 1.1 Update scripts are (c) Epimorphics Ltd and licensed under a Creative Commons Attribution 3.0 License.

Performance benchmarks for the TDB loader (version 2)

CAVEAT

There are "Lies, damned lies, and statistics" but worse are probably performance measurements done by someone else. The real test is what does it mean for any given application and is performance "fit for purpose". Database-related performance measurements are particular murky. The shape of the data matters, the usage made of the data matters, all in ways that can wildly affect whether a system is for for purpose.

Treat these figures with care - they are given to compare the TDB bulker (to version 0.8.7) loader and the new one (version 0.8.8 and later). Even then, the new bulk loader is new, so it is subject to tweaking and tuning but hopefully just to improve performance, not worsen it.

• BSBM – Berlin SPARQL Benchmark
• COINS – Combined Online Information System from the UK Treasury.
• LUBM – Lehigh University Benchmark.

See also

http://esw.w3.org/RdfStoreBenchmarking.

Summary

The new bulk loader is faster by x2 or more depending on the characteristics of the data. As loads can take hours, this saving is very useful. It produces smaller databases and the databases are as good as or better in terms of performance than the ones produced by the current bulk loader.

Setup

The tests were run on a small local server, not tuned or provisioned for database work, just a machine that happened to be easily accessible.

• 8GB RAM
• 4 core Intel i5 760 @2.8Ghz
• Ubuntu 10.10 - ext4 filing system
• Disk: WD 2 TB - SATA-300 7200 rpm and buffer Size 64 MB
• Java version Sun/Oracle JDK 1.6.0_22 64-Bit Server VM

BSBM

The BSBM published results from Nov 2009.

The figures here are produced using a modified version of the BSBM tools set used for version 2 of BSBM. The modifications are to run the tests on a local database, not over HTTP. The code is available from github. See also this article.

• Loader Performance for BSBM
• Database Sizes for BSBM
• Query Performance for BSBM

BSBM - Loader performance

BSBM dataset	Triples	Loader 1	Rate	Loader 2	Rate
50k	50,057	3s	18,011 TPS	7s	7,151 TPS
250k	250,030	8s	31,702 TPS	11s	22,730 TPS
1m	1,000,313	26s	38,956 TPS	27s	37,049 TPS
5m	5,000,339	121s	41,298 TPS	112s	44,646 TPS
25m	25,000,250	666s	37,561 TPS	586s	42,663 TPS
100m	100,000,112	8,584s	11,650 TPS	3,141s	31,837 TPS
200m	200,031,413	30,348s	6,591 TPS	8,309s	24,074 TPS
350m	350,550,000	83,232s	4,212 TPS	21,146s	16,578 TPS

BSBM - Database sizes

Database	Size/loader1	Size/loader2
50k	10MB	7.2MB
250k	49MB	35MB
1m	198MB	137MB
5m	996MB	680MB
25m	4.9GB	3.3GB
100m	20GB	13GB
200m	39GB	26GB
350m	67GB	45GB

BSBM - Query Performance

Numbers are "query mix per hour"; larger numbers are better. The BSBM performance engine was run with 100 warmups and 100 timing runs over local databases.

Loader used	50k	250k	1m	5m	25m	100m	200m	350m
Loader 1	102389.1	87527.4	58441.6	5854.7	1798.4	673.0	410.7	250.0
Loader 2	106920.1	86726.1	62240.7	11384.5	3477.9	797.1	425.8	259.2

What this does show is that for a narrow range of database sizes around 5m to 25m, the databases produced by loader2 are faster. This happens because the majority ogf the working set of databases due to loader1 didn't fit mostly in-memory but those produced by loader2 do.

COINS

COINS is the Combined Online Information System from the UK Treasury. It's a real-wolrd database that has been converted to RDF by my colleague, Ian - see Description of the conversion to RDF done by Ian for data.gov.uk.

General information about COINS.

COINS is all named graphs.

• Loader Performance for COINS
• Database Sizes for COINS

COINS - Loader Performance

COINS dataset	Quads	Loader 1	Rate	Loader 2	Rate
	417,792,897	26,425s	15,811 TPS	17,057s	24,494 TPS

COINS - Database sizes

Size/loader1	Size/loader2
152GB	77GB

LUBM

LUBM information

LUBM isn't a very representative benchmark for RDF and linked data applications - it is design more for testing inference. But there is some details of various systems published using this benchmark. To check the new loader on this data, I ran loads for a couple of the larger generated. These are the 1000 and 5000 datasets, with inference applied during data creation. The 5000 dataset, just under a billion triples, was only run through the new loader.

• Loader Performance for LUBM
• Database Sizes for LUBM

LUBM - Loader Performance

LUBM dataset	Triples	Loader 1	Rate	Loader 2	Rate
1000-inf	190,792,744	7,106s	26,849 TPS	3,965s	48,119 TPS
5000-inf	953,287,749	N/A	N/A	86,644s	11,002 TPS

LUBM - Database sizes

Database sizes:

Dataset	Size/loader1	Size/loader2
1000-inf	25GB	16GB
5000-inf	N/A	80GB

TDB bulk loader - version 2

This article could be subtitled called "Good I/O and Bad I/O". By arranging to use good I/O, the new TDB loader achieves faster loading rates despite writing more data to disk. "Good I/O" is file operations that occurs in a buffered and streaming fashion. "Bad I/O" is file operations that cause the disk to jump the heads about randomly or work in small units of disk transfer.

The new TDB loader "loader2" is a standalone program that bulk loads data into a new TDB database. It does not support incremental loading, and may destroy existing data. It has only been tested on Linux; it should run on Windows with Cygwin but what the performance will be is hard to tell.

Figures demonstrating the loader in action for various large datasets are in a separate blog entry. It is faster than the current loader for datasets over about 1 million triples and comes into it's own above 100 million triples.

Like the current bulk loader ("loader1"), loader2 can load triple and quad RDF formats, and from gzipped files. It runs fastest from N-triples or N-Quads because the parser is fastest, and low overhead, for these formats.

The loader is a shell script that coordinates the various phases. It's available in the TDB development code repository in bin/tdbloader2 and the current 0.8.8 snapshot build.

Loader2 is based on the observation that the speed of loader1 can drop sharply as the memory mapped files fill up RAM (the "can" is because it does not always happen; slightly weird). This fall off is more than one would expect simply by having to use some disk and sometimes the rate of loader1 becomes erratic. This could be due to the OS and the management of memory mapped files but the effect is that the secondary index creation can become rather slow. loader1 tends to do "bad I/O" - as the caches fill up, blocks are written back in what to the disk looks like a random order causing the disk heads to jump round.

Copying from the primary index to a secondary index involves a sort because TDB uses B+trees for it's triple and quad indexing. A B+Tree keeps its records in sorted order and each index is different orders.

Loader1 is much faster than simply loading all indexes at once because in that case there is some much RAM being used for caching of parts of all the indexes. Better is to do one index at a time, using the RAM for caching one index at a time.

Loader2 similarly has an data loading phase and an index creation phase.

The first phase is to build the node table and write out the data for index building. Loader2 takes the stream of triples and quads from the parser and writes out the RDF terms (IRI, Literal, blank node) into the internal node table. It also writes out text files of tuples of NodeId (the internal 64 bit number used to identify each RDF term. This is "good I/O" - the writes of the tuples files are buffered up and the files are written append-only. This phase is a Java program, which exits after the node table and working files have been written.

The next phase is to produce the indexes, including the primary index. Unlike loader1, loader2 does not write the primary index during node loading. Experimentation showed it was quicker to do it separately despite needing more I/O. This is slightly strange.

To build indexes, loader2 uses the B+Tree rebuidler and that requires the data in index-sorted order. Index rebuilding is a sort followed by B+tree building. The sort is done by Unix sort. Unix sort is very easy to use and it smoothly scales from a few lines to gigabytes of data. Having written the tuple data out as text files in the first phase (and fixed width hex numbers at that - quite wasteful) Unix sort can do a text sort on the files. Despite that meaning lots of I/O, it's good I/O and the sort program really knows how to best manage temporary files.

For each index, a Unix sort is done to get a temporary file of tuple data in the right sort order. The B+Tree rebuilder is called with this file as the stream of sorted data it needs to create an index.

There are still opportunities to tune the new loader and to see if the output of the sorts being piped directly into the rebuilder is better or worse than the two step approach using temporary file used at the moment. Using different disks for different temporary files should also help.

The index building phase is parallelisable. Because I/O and memory usage are the bottlenecks, not CPU cycles, the crossover point for this to become effective might be quite high.

To find out whether loader2 is better than loader1, I've run a number of tests. Load and query tests with the Berlin SPARQL Benchmark (2009 version), a load test on the RDF version of COINS (UK Treasury Combined Online Information System - about 420 million quads and it's real data) and a load test using the Lehigh University Benchmark with some inferencing. Details, figures and tables in the next article.

Repacking B+Trees

TDB uses B+trees for it's triple and quad indexing.

The indexes hold 3 or 4 NodeIds, where a NodeId is a fixed length 64 bit unique number for each RDF term in the database. Numbers, dates and times are encoded directly into the 64 bits where possible, otherwise the NodeId refers to the location in a separate NodeId to RDF term table like all other types,including IRIs.

The B+Trees have a number of leaf blocks, each of which holds only records (key, value pairs, except there's no "value" part in a triple index - just the key of S,P and O in various orders). TDB threads these blocks together so that a scan does not need to touch the rest of the tree - scans happen when you look up, say S?? for known subject and unknown property and object. The scan returns all the triples with a particular S. Counting all the triples only touches the leaves of the B+Tree, not the branches.

B+Trees provide performant indexing over a wide range of memory situations, ranging from very little caching of disk structures in memory, through to being able to cache substantial portions of the tree.

The TDB B+Trees have a number of block storage layers; an in-JVM block caching for use on 32 bit JVMs, memory mapped files, for 64 bit JVMs, and an in-memory RAM-disk for testing. The in-memory RAM disk is not efficient but it is a very good simulation of a disk - it really does copy the blocks used by a client when written to another area so there is no possibility of updating blocks through references held by the client after the block has been written to "disk".

However, one disadvantage can be that the index isn't very well packed. The B+Trees guarantee that each block is at least 50% full. In practice, the blocks are 60-70% full for indexes POS and OSP. But a worse case can arise happens when inserting into the SPO index because data typically arrives with all the triples for one subject, then all the triples for another subject, meaning the data is nearly sorted. While this makes the processing faster, it makes the resulting B+Tree about 50%-60% packed.

Packing density matters because it influences how much of the tree is cached in a fixed amount of computer memory. If it's 50% packed, then it's only 50% efficient in the cache.

There are various ways to improve on this (compress blocks, B#Trees, and many more besides - B-tree variations are very extensively studied data-structures).

I have been working on a B+Tree repacking programme that takes an existing B+Tree and produces a maximumally packed B+Trees. The database is then smaller on disk and the in-memory caches are more efficiently used. The trees produces are legal B+Trees, and have a packing density of close to 100%. Rebuilding indexes is fast and scales linearly.

The Algorithm

Normally, B+Trees grow at the root. A B+tree is the same depth everywhere in the tree and the tree only gets deeper if the root node of the tree is split and a new root is created pointing to down the two blocks formed by splitting the old root. This algorithm, building a tree from a stream of records, grows the tree from the leaves towards the root. While the algorithm is running there isn't a legal tree - it's only when the algorithm finishes, does a legal B+Tree emerge.

All the data of a B+tree resides in the leaves - the branches above tell you which leaf block to look in (this is the key difference between B-Trees and B+Trees). The first stage of repacking takes a stream of records (key and value) from the initial tree. This stream will be in sorted order because it's being read out of a B+Tree and for a TDB B+tree, it's a scan tracing the threading of the leaf blocks together. In other words, it's not memory intensive.

In the first stage, new leaf blocks are produces, one at a time. A block is filled completely, a new block allocated, the threading pointers completed and the full block written out. In addition, the block number and highest key in the block are emitted. The leaf block is not touched again.

The exception is the last two blocks of the leaf layer. A B+Tree must have blocks at least 50% full to be a legal tree. Although the TDB B+Tree code can cope with blocks that are smaller than the B+tree guarantee, it's neater to rebalance the last two blocks in the case the last block is below the minimum size. Because the second-to-last block is completely full, it's always possible to rebalance in just two blocks.

Phase two takes as input the stream of block number and highest key from the level below and builds branch nodes for the B+Tree pointing, by block number, to the blocks produced in the phase before. When a block is finished, the block can be written out and a block number and split key emitted. This split key isn't the highest key in the block - it's the highest key of the entire sub-tree at that point but this the key passed. A B+tree branch node has N block pointers and N-1 keys and the split key is the last key from making the full block, and is the Nth key from below.

Once again, the last two blocks are rebalanced to maintain then B+Tree invariant of all blocks being at least half full. For large trees, there are quite a few blocks, so the rebalance of just two of them is insignificant. For small trees, it not really worth repacking the tree - block caching at runtime hides any advantages there might be.

The second phase is repeated applied to the block number and split key stream from the layer below until a layer in the tree is only one block (it can't be zero blocks). This single block is the new root block. The third phase is to write out the B+Tree details to disk and put the root block somewhere where it can be found when the B+Tree is reopened.

Consequences

The repacking algorithm produces B+Trees that are the approaching half the size of the original trees. For a large dataset, that's several gigabytes.

The repacked trees perform a bit faster than trees formed by normal use except in one case where they are faster. If the tree is small, the majority fits in the RAM caches, then repacking means less RAM is used but the speed is much the same (in fact as few percent slower, hard to measure but less than 5%, presumably because there is a difference ratio of tree decent and in-block binary search being done by the CPU. This may be no more than a RAM cache hierarchy effect).

However, if the tree was large, and repacked now fits mostly in memory, the repacked trees are faster. As the indexes for an RDF dataset grows much large than the cacheable space, then this effect slowly declines. Some figures to show this are in preparation.

The biggest benefit however, is not directly the speed of access or the reduced disk space. It's the fact here is a fast and linear growth way to build a B+Tree from a stream of sorted records. It's much faster than simply using the regular insertion into the B+Tree.

This is part of the new bulk loader for TDB. It uses external sorting to produce the input to index creation using this B+Tree repacking algorithm. The new bulk loader can save hours on large data loads.

Migrating from the SPARQL Update submission language to the emerging SPARQL 1.1. Update standard

SPARQL 1.1 Update is work-in-progress by the SPARQL Working Group but the general design and language is reasonably stable. There is also the W3C submission SPARQL Update from July 2008. The language are similar in style but the details of the grammars differ. So how to migrate from the syntax used in the submission to the upcoming SPARQL recommendation for a SPARQL Update language?

One way is to provide both languages behind a common API, with the application indicating which language to use. This maximises compatibility because if the submission is the chosen language, the parser for the submission language will be used. But the application has to be changed to move between the languages and conversion of update scripts has to be done for each script, so probably it's a "big bang" change over. The two languages are very close - is it possible to have a single language that covers both languages? Then the application can mix usages and when an update request is printed it can be printed in the soon-to-be standard language, helping people see how the language has changed.

It turns out that most, but no all, the submission language can be incorporated into the grammar for the emerging standard. The cases not covered don't seem to be ones likely to be widely used although it would be good to know if they are.

• CREATE, CLEAR, LOAD, DROP are covered.
• INSERT DATA, DELETE DATA on the default graph covered or working on one a named graph is covered but not on more than one graph at once.
• An extra grammar rule for MODIFY is supported, again working on the default graph or one named graph. but with only a single, optional GRAPH <uri>.
• The old style INSERT { :s :p :o }, DELETE { :s :p :o }, that is, insert or delete some data using just the INSERT or DELETE keyword, without DATA, leads to ambiguity in the combined grammar. These forms are not supported in the combined language. In fact, these forms pre-date the DATA forms in the submission language.

The ability to work on only one named graph needs a little explanation. In the combined grammar, the INTO or FROM is used to set the WITH part of an update. There can be at most one WITH. In the submission,

INSERT INTO <g1> <g2> <g3> { ... } WHERE { ... }

is legal. In terms of language, this could be incorporated into the extended language but it introduces a capability not present in the upcoming working group language and it can't be written out again without repeating the operation, once for each named graph. Operating on a single named graph, or the default graph, is covered by the standard.

For old style INSERT or DELETE of data, conversion can be done by adding in the word DATA to the operation or adding WHERE {} to the update operation. Both these conversions yield something that is legal and the same under the submission language so the conversation can be done and retain the use of old software.

In summary: The accepted forms of the submission language are:

  INSERT [INTO <uri>] {...} WHERE {...}
  DELETE [FROM <uri>] {...} WHERE {...}
  INSERT DATA [INTO <uri>] {...}
  DELETE DATA [FROM <uri>] {...}

By using an extended grammar, the application can even mix syntax of the submission on SPARQL Update and SPARQL 1.1 Update in a single request or, indeed, single operation. When printed the output can be in the equivalent SPARQL 1.1 Syntax.

ARQ (currently, the development snapshot) includes a command line SPARQL 1.1 Update extended parser, "arq.uparse". arq.uparse reads the extended syntax and prints the equivalent strict SPARQL 1.1 Update form. It can be used to translate from the submission language to W3C standards language. More on practical details: jena-dev/message/45040.

Key points from the extended Grammar: The working group is not planning on including this published SPARQL 1.1 Update grammar.

UpdateUnit  :=  Prologue Update <EOF>

Update  :=  ( Update1 )+

# As for SPARQL 1.1 Update with addition of "ModifyOld"
Update1 :=  ( Load | Clear | Drop | Create |
              InsertData | DeleteData | DeleteWhere |
              Modify | ModifyOld )
            ( <SEMICOLON> )?

Load    :=  <LOAD> IRIref ( <INTO> ( <GRAPH> )? IRIref )?

Clear   :=  <CLEAR> ( <SILENT> )? GraphRefAll

Drop    :=  <DROP> ( <SILENT> )? GraphRefAll

Create  :=  <CREATE> ( <SILENT> )? GraphRef

InsertData  :=  <INSERT_DATA> OptionalIntoTarget QuadPattern

DeleteData  :=  <DELETE_DATA> OptionalFromTarget QuadData

DeleteWhere :=  <DELETE_WHERE> QuadPattern

Modify  :=  ( <WITH> IRIref )?
            ( DeleteClause ( InsertClause )? | InsertClause )
            ( UsingClause )*
            <WHERE> GroupGraphPattern

# The MODIFY form from the submission
ModifyOld   :=  <MODIFY> ( IRIref )?
                ( DeleteClause )?
                ( InsertClause )?
                <WHERE> GroupGraphPattern

DeleteClause    :=  <DELETE> OptionalFromTarget QuadPattern

InsertClause    :=  <INSERT> OptionalIntoTarget QuadPattern

# Optional INTO: wraps the QuadPattern with a GRAPH
OptionalIntoTarget  :=  ( ( <INTO> )? IRIref )?

# Optional FROM; wraps the QuadPattern with a GRAPH
OptionalFromTarget  :=  ( ( <FROM> )? IRIref )?

UsingClause :=  <USING> ( IRIref | <NAMED> IRIref )

Moving to Epimorphics

I'm moving to Epimorphics, starting there early next month. Epimorphics is now located in Portishead (as of last Tuesday).

As before, I will still be able to work on Jena, ARQ and TDB and I also get to continue participating in the W3C SPARQL working group, now as an Invited Expert. The working group is making good progress on it's chosen list of features, and now it's just a "small" matter of doing the core work and getting out the Last Call documents to the community.

More exciting times.

Ubuntu on a Samsung N210

I have Ubuntu 10.04 working on a Samsung N210, running Thunderbird, Firefox as well as all my Java development systems. It may not be a fast machine but it's very convenient. The process is now easy, easier than some older material (for 9.10 and very early 10.04) on the web might suggest.

When first turned on, the machine installed Windows 7 starter. I let this finish even though I didn't want it so I could install Ubuntu 10.04 along side Windows in case it didn't work. Once I was happy it would work, I repartitioned the disk (with gparted) to create a single partition, deleting Windows and the restore partition, then reinstalled.

First, build a USB drive with the install on. To get the machine to boot fro this I had to:

• As the machine boots, keep F2 pressed to go into the BIOS.
• Make sure the machine will boot from a USB pendrive.
• Reboot with USB and install Ubuntu Netbook Remix

You have to press F2 very early to get into the BIOS configuration screens. The boot through the BIOS is very fast so don't wait for machine to put the Samsung flash screen up.

You can reset the BIOS to not boot from USB if you want to at this stage, or later.

At this point the wireless does not work. Don't panic; plug in an Ethernet cable and update the system.

sudo apt-get update
sudo apt-get upgrade
sudo reboot

and now the wireless works. There's quite a lot of advice on the web about this but it now seems that there is no need for any custom software - looks like the main Ubuntu repositories have a working version of the system.

To get the function keys working I followed the advice in https://bugs.launchpad.net/ubuntu/+bug/574250.

The missing function keys are due to the fact that Samsung N150/N210/N220 are missing from the udev rules:

/lib/udev/rules.d/95-keymap.rules
/lib/udev/rules.d/95-keyboard-force-release.rules

adding "|*N150/N210/N220*" to the product part of the rules for Samsung in BOTH files, will enable the Fn-up and Fn-down keys. The new product section will look like:

ENV{DMI_VENDOR}=="[sS][aA][mM][sS][uU][nN][gG]*", ATTR{[dmi/id]product_name}=="*NC10*|*NC20*|*N130*|*SP55S*|*SQ45S70S*|*SX60P*|*SX22S*|*SX30S*|*R59P/R60P/R61P*|*SR70S/SR71S*|*Q210*|*Q310*|*X05*|*P560*|*R560*|*N150/N210/N220*"

Now, you can map these keys to any program setting the backlight

and then install some Samsung tools - you need to add the repository to the package manager which you can do graphically or as:

sudo add-apt-repository ppa:voria/ppa
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install samsung-tools samsung-backlight
sudo reboot

at which point the N210 works a treat.

Now - remove all the Windows stickers on the machine, front and back.

If you are looking for software to try, this blog is a good place to start.

Standardising RDF Syntaxes

One area of interest at the RDF Next Steps Workshop is other RDF-related syntaxes, ones that are not RDF/XML. RDF/XML is the standard syntax; N-Triples is defined as part of the RDF test suite but not formally as a syntax on the same level as RDF/XML; there is RDFa for embedding in XHTML.

RDF/XML is not easy to read as RDF. Turtle appeals because it more clearly shows the triple structure of the data. N-Quads is a proposal to extend RDF file format to named graphs and TriG is a Turtle-inspired named graph syntax. There is TriX but I've never come across that in the wild.

Using XML had several advantages, such as comprehensive character set support, neutrality of format and reuse of parsers. However, it's complicated in it's entirety, even after using an XML parser and it is quite expensive to parse, making parsing large (and not some large) files a significant cost. Because it can't, practically, be processed by XSLT there are nowadays few advantages.

All the non-XML formats, which are much easier to read and process, would be good to standardise but they are not without the need for sorting out some details. Details matter when you're dealing with anything over a trivial amount of data and when's it's millions of triples, it's just a friction point to get the data cleaned up if there is disagreement between information publisher and information consumer.

Turtle

Turtle takes the approach of using UTF-8 as the character set, rather than relying on character set control like XML. Given that nowadays UTF-8 support is well understood and widely available, the internationalization issues of different scripts are best dealt with that way. Parsers are both simple to write and fast. (The tricks needed to get Java to parser fast would be a subject for a separate discussion.)

As Turtle is the more mature of the possible syntaxes, it is also the best worked out. One issue I see is the migration from a one-standard-syntax world to a two-standard-syntax world and it's not without its practical problems. What if system A speaks RDF/XML only, and system B speaks only Turtle? How long will it take for uses of content negotiation take to catch up? Going from V-nothing to V1 of a system (which is where we are now) is usually quicker than going from V1 to V2 as the need to upgrade is much less. If it ain't broke why change?

Turtle can write graphs that RDF/XML can't encode. If the property can't be split into namespace and local name, then RDF/XML can't represent it. An XML qname must have a local part of at least one alphabetic character. This isn't common but these details arise and cause problems (that is, costs) when exchanging data at scale.

What would be useful would be a set of language tokens to build all sorts of languages, like rule languages but at the moment there some unnecessary restrictions in Turtle on prefixed name (Turtle calls them qnames but they are not exactly XML qnames).

Turtle disallows:

employee:1234

because the local part starts with a digit. In data converted from existing (non-RDF) data this is a nuisance, and one that caused SPARQL to allow it, based on community feedback.

But there are other forms that can be useful that are not allowed (and aren't in SPARQL):

ex:xyz#abc

ex:xyz/abc

ex:xyz?parm=value

The last one might be a bit extreme but the first two or just using the prefix to tidy up long IRIs. Partial alignment with XML qnames makes no sense in Turtle. Extending the range of characters to include /, # and maybe a few others, makes prefixed names more useful. Issues just like this lead to the CURIE syntax.

While these URIs can be written in Turtle, it needs the long form, with <...>, and the only way to abbreviate is via the base IRI, but you can only have one base URI. It's a workaround really that gets ugly when the advantage of Turtle is that it is readable. Extending the range of characters in the local part does not invalidate old data; it does create friction in interoperability so we have one last chance to sort this out if Turtle is to be standardised.

N-Quads

<s> <p> <o> .

<s> <p> <o> <g> .

What could be simpler? N-Quads is N-Triples with an optional 4th field to give the graph name (or context - it wasn't designed specifically for named graphs, but let's just consider IRIs in the 4th field, not blank nodes or literals which the syntax allows).

But TriG puts the graph name before the triples, while N-Quads puts it after. Maybe N-Quads should be like TriG so that TriG can make N-Quads a subset. Parsing this modified N-Quads only takes buffing of the tokens on the line and counting to 3 or 4 to determine if it's a triple or a quad. Making TriG more flexible, at the cost of the slightly less intuitive graph name first, in what is basically a dump format, seems to me to be a good trade-off.

Blank nodes labels need to be clarified - is the scope the graph or the document? Both are workable. I'd choose scope-to-the-document, if only to avoid the confusion of two identical labels referring to to different bnodes, and it's occasionally useful to say that a bnode in one graph really is the same as another when using it as a transfer syntax (for example, when one graph is a subgraph of another). TriG has the same issue but the use of nested forms for graphs makes scoped-graph more reasonable (except that graphs can be split over different {} blocks). Doing the same in N-Quads and TriG is important, and my preference is document-scoped labels.

TriG

TriG is a Turtle-like syntax for named graphs. It is useful for writing down RDF datasets.

It has some quirks though. Turtle is not a subset of TriG because the default graph needs to be wrapped in {} but the prefixes need to be outside the {}. The default graph needs to be given in a single block, but named graphs can be fragmented (that was just an oversight in the spec). It would be helpful to allow the unnamed graph be specificed as Turtle and similarly if an N-Quads file were legal TriG.

TriG allows the N3-ish form:

<g> = { ... } .

I've seen some confusion about this form in the data.gov.uk data. The addition "=" and ".", which are optional, cause confusion and at least one parser does not accept them as it wasn't expected.

In N3, = is a synonym for owl:sameAs but the relationship isn't likely to be owl:sameAs, read as N3, it's more likely to be log:semantics. Now I like the uniformity of the N3 data model, with graph literals (formulae) because of the simplicity and completeness it introduces but it's not RDF, it's an extension and it breaks all RDF-only systems.

If <g> is the IRI of a graph document, it would be more like the N3:

 <g> log:semantics { ... } .

or

<g> log:semantics ?v .
?v owlSameAs { ... } .

Avoiding the variability of syntax, which brings no benefit, is better. Drop the optional adornment.

Summary

None of these issues are roadblocks; they are just details that need sorting out to move from the current de facto formats to specifications. When exchanging data between systems that are not built together, details matter.

Running TDB on a cloud storage system

Project Voldemort is an open-source (Apache2 license) distributed, scalable, fault-tolerant, key-value storage system for large scale data. Being a key-value store the only operations it provides are:

• get(key) -> value
• put(key, value)
• delete(key)

Key and value can be various custom types but at the lowest level, they are arrays of bytes. Serialization schemes on top of byte arrays given structure but access is only via the key (so no filters or joins as part of the store. It's built for scale and speed, and fault tolerance.

TDB has internal APIS so that difefrentindexing scheme or different stroage technologies can be plugged in. A key-value store can be used as the storage layer for TDB.

There are two areas of storage needed: the node table (a 2-way mapping between the data making up the RDF terms and the associated, fixed size NodeId) and the indexes, which provide the matching of triple patterns. See the TDB Design Notes.

But a key-value store isn't an ideal backend. The node table is a pair of key-value stores because all that is needed is lookup between RDF term and the NodeId. The issues that arise are the granularity of access. TDB heavily caches the mapping in the query engine.

The indexes don't naturally map to key-value access because looking up a triple pattern results in all matches. There are (at least) two ways of doing this. Either store something like all PO pairs and use S as a key (a bit like Jena's memory model), or use the key-value store to hold part of a datastructure and access it like a disk.

TDB uses threaded B+Trees with a pluggable disk block layer (this is used to switch between 32 and 64 bit modes) so the key-value store a block storage is a simple fit. Because B+Trees store the entries in sorted order, caching means that a block probably contains all the PO for a given S if a look up is by S so these two schemes end up being similar even though at the design level they are quite different.

Both apects are relying on the query engine doing caching to work sensibly to compensate for the mismatch in requirements (triple match for joins) and interface granularity (for node access).

See also:

• Taylor Cowan has explored the S->PO in his work putting Jena on Google App engine.
• The Infinite Graph for Jena uses the Jena memory model and pages data.

Does Project Voldemort work as storage for TDB? Yes, and with only a small amount of code. Not surprisingly, the performance is limited in this experimental system (e.g. storing invidiual RDF terms in the node table needs better management to avoid latency and overhead in the round trip to the remote table). Truncating to only the used space then compressing would be useful on teh indexes (see RDF-3X for an interesting compression scheme). But it's a workable scheme and the style of using a key-value store shows TDB can be ported to a wide variety of environments because key-value stores are currently a very active area - project Voldemort provides a cloud-centric stiorage fabric.

I've started putting experimental systems on github. This experiment is available in the TDB/V repository. These are not released, supported systems; they are the source code and development setup (for Eclipse usually). I used Project Voldemort release v0.57.

BSBM-Jena

This a version of the Berlin SPARQL Benchmark tools, modified to allow the query benchmark driver to work with a local database, rather than a SPARQL endpoint. I've changed benchmark.testdriver.TestDriver to accept a Jena assembler description.

 TestDriver -runs ... -w ... -idir ...-o ... local:assembler.ttl

Git clone git://github.com/afs/BSBM-Jena.git

In the repository, there are versions of ARQ and TDB with significant performance improvements. It will the run benchmark in a reasonable time now. There are some shell scripts to help run the benchmark as well.

Update:

The GIT repository has been renamed as "BSBM-Local". The Jena pseudo URI scheme is now "jena:". The project now includes support for running tests directly on a Sesame native repository using the pseudo URI scheme "sesame:directory" - this could be easily extended to any Sesame repository implementation.

Moving to Talis

I'll be leaving HP soon when the semantic web group winds down. I'll be joining the the platform division at Talis, still living in Bristol, working from home much of the time then travelling to Birmingham as needed . This is one of the reasons why Talis is attractive as a place to work is beause they understand such working arrangements. I'll get to continue support and development of my contributions to Jena.

And the first question I have been getting is about what will happen to Jena.

Jena has a BSD-style licence so there is no block to continuing any use by any users nor continued development by the Jena developers. But we plan to go further and become an open source project with no one commercial backer. After discussions with HP, our current plan is to transfer the ownership of the copyright to a commercially neutral body. In immediate terms, there is no change to people/companies using Jena but this change will make it easier to continue and expand the core developer community and indeed it enables us to accept contributions more easily. It has been a (cultural, not legal) barrier that HP was seen to have controlling interest despite the fact we have always acted openly.

I also get to continue participating in the W3C SPARQL working group. The list of things the WG has decided it has the time and resources to work on is here. The charter states that no queries from the spec of 2008 will change. The new thing for the working group to address is update, both as a language but also some RESTful operations.

Exciting times.

A small mystery about deletion in T-Trees

T-Trees are a generalisation of AVL trees. They are useful for in-memory databases because they have better packing densities than AVL trees and need less rotations. They provide a sorted index (so they are not good as the only index structure in an in-memory RDF store). This posting is only loosely triple store or SPARQL related.

The paper "A Study of Index Structures for Main Memory Database Management Systems" (Tobin J. Lehman and Michael J. Carey, VLDB 1986) has the details.

T-Trees keep an array of items per tree node (usually a short array) and have 3 pointers and 2 integers per tree node stored as opposed to 3 pointers, 1 number per single item stored for AVL. (both can be done with 2 pointers, with no parent but it's more complicated and the code has to run it's own stack to record it's path through the tree). Make the array a few entries long, and a T-Tree is a bit more more compact; rotations only happen when the tree structure after a leaf-array fills up.

I understand these algorithms in depth if I code them up. My implementation of T-Trees which includes consistency checking because I find it easier to write data structure algorithms this way - lots of internal checking, lots of test cases and then move to large scale randomized insertion and deletion patterns because I don't trust myself to enumerate all possibilities in a hand-written test suite. Run the randomized tests for a few million iterations checking the structure for internal consistency constraints on every insertions and deletion. Then disable (but don't remove!) the checking code, and rely on the fact that "if (false)" compiles to nothing in Java and statics tend to get in-lined by the JIT.

But one area is puzzling me. The mystery, to me, is in the delete algorithm. One feature of a T-Tree is that the internal nodes (internal nodes have both a left and right subtree) should always be larger than some minimum amount.

The delete algorithm, from the paper, is (section 3.2.1):

3) Delete Algorithm

The deletion algorithm is similar to the insertion algorithm in the sense that the element to be deleted is searched for, the operation is performed, and then re-balancing is done if necessary. The algorithm works as follows:

1. Search for the node that bounds the delete value. Search for the delete value within this node, reporting an error and stopping if it is not found.
2. If the delete will not cause an underflow (i.e. if the node has more than the minimum allowable number of entries prior to the delete), then simply delete the value and stop; else, if this is an internal node, then delete the value and borrow the greatest lower bound of this node from a leaf or half-leaf to bring this node’s element count back up to the minimum; else, this is a leaf or a half-leaf, so just delete the element. (Leaves are permitted to underflow, and half-leaves are handled in step 3.
3. If the node is a half-leaf and can be merged with a leaf, coalesce the two nodes into one node (a leaf) and discard the other node. Proceed to step 5.
4. If the current node (a leaf) is not empty, then stop; else, free the node and proceed to step 5 to re-balance the tree.
5. For every node along the path from the leaf up to the root, if the two subtrees of the node differ in height by more than one, perform a rotation operation. Since a rotation at one node may create an imbalance for a node higher up in the tree, balance-checking for deletion must examine all of the nodes on the search path until a node of even balance is discovered.

But what if a half-leaf, a node with just one sub-node as a leaf, becomes less than the minimum size of a node, yet can not be merged with it's leaf? The t-tree is still valid - the size constraint is on internal nodes only. But a half-leaf can be become an internal node by a rotation of the tree. So our less-than-min-sized half-leaf can become an invalid internal node and the constraint on internal nodes is validated.

Several possible solutions ocurr to me (and probably more than just these):

• Just don't worry (works for me because I'm expecting insertion if much more important in the any usage I might make of the T-Tree implementation). The internal node that was too small may become larger due to a later insertion. But my internal consistency checking code is now weakened because there is a condition on internal nodes that is no longer always true.
• Treat a half-leaf more like an internal node with respect to deletion and pull up an entry from its leaf to keep the half-leaf at the minimum size. If the half-leaf has a left-leaf, this is the same as the rule for deletion in an internal node. If the half-leaf has a right-leaf, the lowest element of the leaf is required, which is a shift down of all the other elements in the leaf so is less than ideal.
• Have special code in the rotation operations to move elements around when rotating a half-leaf into an internal node position. This is like possibility 2, except delaying it until it is know it will cause an invalid internal node. T-Trees already have a special case rotation on insertion anyway.

I choose the second way for now - fix up during deletion - because the checking code can now check half-leaves as well as internal nodes for size constraints, so catching problems earlier in some insert/delete sequence.

A search of the web does not find any mention of this - most web pages are either a copy of the wikipedia page or reference the original paper.

If anyone can help me out with this, then please leave a comment or get in touch. I'd be surprised if it isn't that I'm missing something obvious (T-Trees are not new) but the situation of a small half-leaf becoming an internal node does occur as I found from the randomized testing.

Walking the Web

It's nice to see Freebase providing an RDF interface:  http://rdf.freebase.com/. The example they give is <http://rdf.freebase.com/ns/en.blade_runner> so let's see what is actually there and how we might use the information.

Each graph describing something contains Freebase URLs to be explored.  What we want is the ability to load data into our local store while some query is running, enabling the dataset to be enlarged as the query makes choices about how to proceed.

This is similar to cwm's log:semantics. http://ww.w3.org/2000/10/swap/doc/Reach

In SPARQL, the dataset is fixed. No good if you want to write a graph-walking process without some glue in your favourite programming language. In one way, it's scripting for the web but in a special way.  It's not a sequence of queries and updates; it's changing the collection of graphs, expanding the RDF dataset known to the application.

Query 1 : See what's in the graph

Let's first look at what's available at the example URL.  That does not require anything special: it's just a FROM clause (which in ARQ will content-negotiate for RDF; if you use a web browser you will see an HTML page):

PREFIX fb: <http://rdf.freebase.com/ns/>
SELECT *
FROM fb:en.blade_runner
{ ?s ?p ?o }

Hmm - 294 triples.

Query 2 : Look for interesting properties

PREFIX fb: <http://rdf.freebase.com/ns/>
SELECT DISTINCT ?p
FROM fb:en.blade_runner
{
  ?s ?p ?o
}

62 distinct properties used.  fb:film.film.starring looks interesting.

Query 3 : Follow the links

As an experimental feature, consider a new SPARQL keyword "FETCH" which takes a URL, or a variable bound to a URL by the time that part of the query is reached, and fetches the graph at that location.

Now we fetch the documents at each of the URLs that are objects of the blade runner, film.film.starring triples.

FETCH loads the graph and places it in the dataset as a named graph, the name being the URL is fetched it from. We use GRAPH to access the loaded graph. Done this way, triples from different sources are kept separately which might be important in deciding what sources to believe.

This also shows a critical limitation: just placing in a named graph is a basic requirement for deciding what to believe but really there ought to be a lot more metadata about the graph, including when it was read, possibly why it was read (how we got here in the query) etc etc. But we are not an agent system so we will note this and move on.

By poking around with GRAPH ?personUUID { ?s ?p ?o} (60 triples) the property film.performance.actor looks hopeful.

PREFIX fb: <http://rdf.freebase.com/ns/>
SELECT ?actor
FROM fb:en.blade_runner
{
  fb:en.blade_runner fb:film.film.starring ?personUUID
  FETCH ?personUUID
  GRAPH ?personUUID
    { ?personUUID fb:film.performance.actor ?actor }
}

12 results.

--------------------------------------------
| actor                                    |
============================================
| fb:en.james_hong                         |
| fb:en.brion_james                        |
| fb:en.edward_james_olmos                 |
| fb:en.joanna_cassidy                     |
| fb:en.william_sanderson                  |
| fb:en.rutger_hauer                       |
| fb:authority.netflix.role.20000077       |
| fb:guid.9202a8c04000641f80000000054cbccc |
| fb:en.sean_young                         |
| fb:en.joe_turkel                         |
| fb:en.harrison_ford                      |
| fb:en.daryl_hannah                       |
--------------------------------------------

and more URLs to follow.

Looking in the next graph, there is fb:type.object.name so let's guess and use that.  But each time we have chosen a property, we didn't have to guess, we can follow that property URL itself:

PREFIX fb: <http://rdf.freebase.com/ns/>
SELECT *
FROM fb:type.object.name
{
  ?s ?p ?o
}

but it's easier to read the description in HTML (and freebase is link following internally to build the page).

Query 3 : The names of actors in Blade Runner

So a query to find the names of actors in "Blade Runner" is:

PREFIX fb: <http://rdf.freebase.com/ns/>
SELECT ?actor ?name
FROM fb:en.blade_runner
{
  fb:en.blade_runner fb:film.film.starring ?personUUID
  FETCH ?personUUID
  GRAPH ?personUUID
    { ?personUUID fb:film.performance.actor ?actor }
  FETCH ?actor
  GRAPH ?actor
    { ?actor fb:type.object.name ?name }
}
ORDER BY ?actor

which gives:

-------------------------------------------------------------------
| actor                                    | name                 |
===================================================================
| fb:authority.netflix.role.20000077       | "M. Emmet Walsh"     |
| fb:authority.netflix.role.20000077       | "M・エメット・ウォルシュ"    |
| fb:en.brion_james                        | "Brion James"        |
| fb:en.daryl_hannah                       | "Daryl Hannah"       |
| fb:en.daryl_hannah                       | "Ханна, Дэрил"       |
| fb:en.daryl_hannah                       | "דריל האנה"          |
| fb:en.daryl_hannah                       | "ダリル・ハンナ"         |
| fb:en.edward_james_olmos                 | "Edward James Olmos" |
| fb:en.harrison_ford                      | "Harrison Ford"      |
| fb:en.harrison_ford                      | "Форд Гаррісон"      |
| fb:en.harrison_ford                      | "Форд, Харрисон"     |
| fb:en.harrison_ford                      | "Харисон Форд"       |
| fb:en.harrison_ford                      | "Харисън Форд"       |
| fb:en.harrison_ford                      | "האריסון פורד"       |
| fb:en.harrison_ford                      | "ハリソン・フォード"       |
| fb:en.harrison_ford                      | "哈里森·福特"         |
| fb:en.harrison_ford                      | "해리슨 포드"          |
| fb:en.james_hong                         | "James Hong"         |
| fb:en.joanna_cassidy                     | "Joanna Cassidy"     |
| fb:en.joe_turkel                         | "Joe Turkel"         |
| fb:en.rutger_hauer                       | "Rutger Hauer"       |
| fb:en.rutger_hauer                       | "Хауэр, Рутгер"      |
| fb:en.rutger_hauer                       | "ルトガー・ハウアー"      |
| fb:en.rutger_hauer                       | "魯格·豪爾"           |
| fb:en.sean_young                         | "Sean Young"         |
| fb:en.sean_young                         | "Шон Йънг"           |
| fb:en.sean_young                         | "Янг, Шон"           |
| fb:en.sean_young                         | "ショーン・ヤング"        |
| fb:en.william_sanderson                  | "William Sanderson"  |
| fb:guid.9202a8c04000641f80000000054cbccc | "Morgan Paull"       |
-------------------------------------------------------------------

 

We are left with a question: why use (extended) SPARQL? If you're doing it once, then a web browser is easier. After all, I used one to choose the properties to follow.

But with a query you can send it to someone else for them to reuse your knowledge, you can rerun it to look for changes, you can generalise and let the computer do some brute force search to find things that would take you, the human, a long time.

ARQ Property Paths

SPARQL basic graph patterns only allow fixed length routes through the graph being matched. Sometimes, the application wants a more general path so ARQ has acquired syntax and built-in evaluation for a path language as part of the ARQ's extensions to SPARQL. The path language is like string regular expressions, except it's over predicates, not string characters.

Property path documentation for ARQ.

Simple Paths

The first operator for simple paths is "/", which is path concatenation, or following property links between nodes, the other simple path operator is "^" which is like "/" except the graph connection is traversed (it's the inverse property).

# Find the names of people 2 "foaf:knows" links away.
PREFIX <http://xmlns.com/foaf/0.1/>
SELECT ?name
{ ?x foaf:mbox <mailto:alice@example> .
  ?x foaf:knows/foaf:knows/foaf:name ?name .
}

This is the same as the strict SPARQL query:

{
  ?x  foaf:mbox <mailto:alice@example> .
  ?x  foaf:knows [ foaf:knows [ foaf:name ?name ]]. 
}

or, with explicit variables:

{
  ?x  foaf:mbox <mailto:alice@example> .
  ?x  foaf:knows ?a1 .
  ?a1 foaf:knows ?a2 .
  ?a2 foaf:name ?name .
}

And these two are the same:

 ?x foaf:knows/foaf:knows/foaf:name ?name . 

 ?name ^foaf:name^foaf:knows^foaf:knows ?x .

Complex Paths

The simple paths don't change the expressivity; they are a shorthand for part of a basic graph pattern and ARQ compiles simple paths by generating the equivalent basic graph patterns then merging adjacent ones together.

Alternation, the "|" operator does not change the expressivity either - the same thing could be done with a SPARQL UNION.

# Use with Dublin core 1.0 or Dublin Core 1.1 "title"
 :book (dc10:title|dc11:title) ?title

Some complex paths do change the expressivity of language; the query can match things that can't be matched in a strictly fixed length paths because they allow arbitrary length paths through the use of "*" (zero or more), "+" (one or more), "?" (zero or one) as well as the form "{N,}" (N or more).

Two very useful cases are:

 # All the types, chasing the subclass hierarchy
 <http://example/> rdf:type/rdfs:subClassOf* ?type

and:

 # Members of a list
 ?someList rdf:rest*/rdf:first ?member .

because "*" includes the case of a zero length path - all nodes are "connected" to themselves by a zero-length path.

Strict SPARQL

The Property path documentation shows how to install paths and name them with a URI so you can use a path in strict SPARQL syntax.

Other

There have been some other path-related extensions to SPARQL:

• GLEEN is a library that provides path-functionality in graph matching via property functions.  It also provides subgraph extraction based on pattern.
• PSPARQL allows variables in paths
• SPARQLeR which has path value type

TDB: Loading UniProt

TDB passed a milestone this week - a load of the complete UniProt V13.3 dataset.

UniProt V13.3 is 1,755,773,303 triples (1.7 billion) of which 1,516,036,125 are unique after duplicate suppression.

This dataset is interesting in a variety of ways. Firstly, it's quite large. Secondly, it is the composite of a small number of different, related databases and has some large literals (complete protein sequences - some over 70k characters in a single literal) as well as the full text of many abstracts. (LUBM doesn't have literals at all. Testing using both synthetic data and real-world data is necessary.)

UniProt comes as a number of RDF/XML files.  These had already been checked before the loading, by parsing to give N-Triples, using it as a sort of dump format. The Jena RDF/XML parser does extensive checking, and the data had some bad URIs. I find that most large datasets do throw up some warnings on URIs.

TDB also does value-based storage for XSD datatypes decimals. integer, dates, and dateTimes. Except there aren't very many. For example, there are just 18 occurrences of the value "1", in any form, in the entire dataset. They are just xsd:ints in some cardinality constraints. I was a bit surprised by this. Given the size of the dataset, I expected none or lots of uses of the value 1, so I grepped the input data to check - it's much, much quicker to use SPARQL than run grep on 1.7 billion triples in gzip'ed files but working with N-triples makes it easy to produce small tools you can be sure that work. And indeed they are the only 1 values. Trust the SPARQL query next time.

Two more ARQ extensions

I've implemented two new extensions for ARQ:

• Assignment
• Sub-queries

Both these expose facilities that are already in the query algebra.  Sub-queries are done by simply allowing query algebra operators to appear anywhere in the query, not requiring solution modifiers to only be at the outer level of the query, so it allows extensions like counting, to be inside the query and available to the rest of the pattern matching. An assigment operator existed as an algebra extension for optimization and to support ARQ SELECT expressions

Both are syntactic extensions and are available if the query is parsed with language Syntax.syntaxARQ.

Currently available in ARQ SVN.

Assignment

This assigns a computed value to a variable in the middle of a pattern.

LET (?x := ?y + 5 )

The assignment operator is ":=". A single "=" is already the test for equals in SPARQL.

This means that a computed value can be used in other pattern matching:

 SELECT ?y ?area
 {
    ?x rdf:type :Rectangle ;
       :height ?h ;
       :width ?w .
    LET (?area := ?h*?w )
    GRAPH <otherShapes>
    {
      ?y :area ?area . # Shapes with the same area
    }
 }

Application writer can provide their own functions, maybe to do a little data munging to map between different formats:

   ?x  foaf:name  ?name .          # "John Smith"
   # Convert to a different style: "Smith, John" for example.
   LET (?vcardName := my:convertName(?name) )
   ?y vCard:FN ?vcardName .

There are some rules for the assignment:

• if the expression does not evaluate (e.g. unbound variable in the expression), no assignment occurs and the query continues.
• if the variable is unbound, and the expression evaluates, the variable is bound to the value.
• if the variable is bound to the same value as the expression evaluates, nothing happens and the query continues.
• if the variable is bound to a different value as the expression evaluates, an error occurs and the current solution will be excluded from the results.

ARQ already has expressions in SELECT expressions so a combination of sub-query and expression can achieve the same effect but it's unnatural and verbose and sometimes requires parts of the pattern matching to be written twice, inside and outside the sub-query.

One place where LET might be useful is in a CONSTRUCT query. In strict SPARQL, only terms found in the original data can be used for variables in the construct template but with LET-assignment:

   CONSTRUCT { ?x :lengthInInches ?inch }
   WHERE
   { ?x :lengthInCM ?cm
     LET (?inch := ?cm/2.54 )
   }

This isn't a new idea - see for example: "A SPARQL Semantics based on Datalog" - although the syntax in ARQ is designed to group the terms better.

Sub-queries

A sub-query can be used to apply some solution modifier to a sub-pattern.  Useful examples include aggregation, especially grouping and counting, and LIMIT with ORDER BY to get only some of the results of a pattern match.

 { SELECT (COUNT(*) AS ?c) { ?s ?p ?o } }

A sub-query is enclosed by {} and must be the only thing inside those braces, the same style as Virtuoso Subqueries. The sub-query will be combined, with SPARQL join, with other patterns in the same group. In the example

Find how many people all persons with two or more phones foaf:knows:

 PREFIX foaf: <http://xmlns.com/foaf/0.1/>

 SELECT ?person ?knowsCount
 {
   # ?person who have 2 or more phones
   { SELECT ?person
     WHERE { ?person foaf:phone ?phone } 
     GROUP BY ?person 
     HAVING (COUNT(?phone) >= 2) 
   }
   # Join on ?person with how many people they foaf:knows
   { SELECT ?person (COUNT(?x) AS ?knowsCount)
     WHERE { ?person foaf:knows ?x .}
     GROUP BY ?person
   }
}

Queries with sub-queries can become complicated quite quickly so I usually write each of the part separately then combining them.

First time out for TDB (pt 2)

Follow-on from previous testing: a larger load of 100 million triples from UniProt 7.0a performed as follows on the SDB1 machine:

• 115,517,840 triples
• 3903s (which is 29594 triples/s) -- or about 65 minutes

First time out for TDB

In other work, I've needed with a storage and indexing components.  To test them out, I've built a persistent Jena graph that behaves like an "RDF VM" whereby an application can handle more triples than memory alone, and it flexes to use and release its cache space based on the other applications running on the machine.  Working name: TDB. Early days, having only just finished writing the core code, but the core is now working to the point where it can load and query reliably.

The RDF VM uses indexing code (currently, classical B-Trees) but in a way that matches the model of implementation of RDF.  There is no translation between the indexing and the disk idea of data. To check that made sense, I also tried with the B-Trees replaced by Berkeley DB Java Edition. The BDB version behaves similarly with a constant slowdown. Of course, BDB-JE is more sophisticated with variable sized data items and duplicates (and transactions but I wasn't using them) so some overhead isn't surprising.

I have also tried some other indexing structures but B-Trees have proved to scale better, from situations where there isn't much free memory to 64-bit machines where there is.

Node Loads

The main area of difference between the custom and BDB-backed implementations is in loading speed.  They handle RDF node representations differently. Storing them in a BDB database, or JDBM htable, was adequate, giving a load rate of around 12K triples/s but it does generate too many disk writes to disk in an asynchronous pattern. Changing to streaming writes in TDB fixed that.  Because all the implementations fit the same framework, this technique can be rolled back into the BDB-implemented code. And BDB supports transactions.  The node technique may also help with a SQL database backed system like SDB as well.

I did try Lucene - not a good idea.  Loading is too slow, but then that's not what Lucene is designed for.

Testing

For testing, I used the Jena test suite for functional tests and the RDF Store Benchmarks with DBpedia dataset for performance.

TDB works and gives the right results for the queries. (It would be good to have the results published as well as described in the DAWG test suite so testing can be done.)

Query 2 benefits hugely from caching.  If run completely cold, after a reboot, it can take up to 30s. Running cold is also a lot more variable on machine sdb1 because other projects use the disk array.

Still room for improvement though. The new index code doesn't quite pack the leaf nodes optimally yet and some more profiling may show up hotspots but for a first pass just getting the benchmark to run is fine.  Rewriting queries, as an optimizer should, lowers the execution time for queries 3 and 5 to 0.48s and 1.46s respectively. 

The results for query 4 show one possible hotspot.  This query churns nodes executing the filters but the node retrieval code does not benefit from co-locality of disk access.  Fortunately alternative code for the node table does make co-locality possible and still run almost as fast. Time to get out the profiler.

To illustrate the "RDF VM" effect; when run with Eclipse, Firefox etc all consuming memory, then my home PC is 5-10% slower than when run without them hogging bytes even on a dataset as small as 16 million triples.

First Results for TDB

Machine	sdb1	Home PC
Date	11/02/2008	11/02/2008
Load (seconds)	686.582	726.1
Load (triples/s)	23,478	22,961
Query 1 (seconds)	0.05	0.03
Query 2 (seconds)	1.30	0.73
Query 3 (seconds)	9.87	9.50
Query 4 (seconds)	30.99	35.32
Query 5 (seconds)	29.87	34.24

Breakdown of the sdb1 load:

Loading	Triples	Load time seconds	Load rate Triples/s
Overall	16,120,177	686.582s	23,478
infoboxes	15,472,624	651.543	24.084
geocordinates	447,517	24.084	18,581
homepages	200,036	10.955	18,259

Setup

My home PC is a media centre - quad core, 3Gbyte RAM, consumer grade disks, running Vista and Norton Internet Security anti-virus. I guess it's quicker on the short queries because there is less latency to getting to the disk - even if the disks are slower - but falls behind when the query requires some crunching or a lot of data drawn from the disk.

sdb1 is a machine in a blade rack in the data centre - details below.

(My work's desktop machine, running WindowsXP has various Symantec antivirus, anti-intrusion software components and is slower for database work generally.)

Disk: Data centre disk array over fiber channel.

/proc/cpuinfo (abbrev):

processor : 0
vendor_id : AuthenticAMD
cpu family : 15
model : 37
model name : AMD Opteron(tm) Processor 252
stepping : 1
cpu MHz : 1804.121
cache size : 1024 KB
fpu : yes
fpu_exception : yes
cpuid level : 1
TLB size : 1088 4K pages
address sizes : 40 bits physical, 48 bits virtual

processor : 1
vendor_id : AuthenticAMD
cpu family : 15
model : 37
model name : AMD Opteron(tm) Processor 252
stepping : 1
cpu MHz : 1804.121
cache size : 1024 KB
fpu : yes
fpu_exception : yes
TLB size : 1088 4K pages
clflush size : 64
address sizes : 40 bits physical, 48 bits virtual

/proc/meminfo (abbrev):

MemTotal: 8005276 kB
MemFree: 435836 kB
Buffers: 40772 kB
Cached: 7099840 kB
SwapCached: 0 kB
Active: 1165348 kB
Inactive: 6141392 kB
SwapTotal: 2048276 kB
SwapFree: 2048116 kB
Mapped: 202868 kB