ARQtick

Importing SourceForge code into Apache for Jena

2011-05-19T15:16:00.002+01:00

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

2011-03-02T19:41:00.001Z

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)

2010-12-09T13:41:00.001Z

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

2010-12-09T13:41:00.000Z

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

2010-12-03T19:29:00.000Z

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

2010-08-28T22:29:00.001+01:00

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

2010-07-30T10:42:00.003+01:00

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

2010-07-17T20:50:00.000+01:00

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

2010-06-02T10:57:00.003+01:00

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 { ... } .

<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

2009-12-14T15:29:00.002Z

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).

BSBM-Jena

2009-10-01T14:47:00.003+01:00

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

2009-09-14T15:00:00.001+01:00

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

2008-12-27T16:39:00.003Z

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:

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.

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.

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.

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.

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

2008-10-29T20:29:00.004Z

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

2008-07-12T20:00:00.003+01:00

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

2008-06-08T20:59:00.005+01:00

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

2008-03-25T18:47:00.002Z

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)

2008-02-19T12:13:00.003Z

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

2008-02-13T10:53:00.006Z

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

Jena-Mulgara : example of implementing a Jena graph

2008-01-05T20:20:00.001Z

In Jena, Graph is an interface. It abstracts anything that looks like RDF - storage options, inference, other legacy data sources.

The main operations are find(Triple), add(Triple) and remove(Triple). In addition, there are a number of getters to access handlers of various features (query, statistics, reification, bulk update, event manager) . Having handlers, rather than directly including all the operations for each feature reduces the size of the interface and makes it easier to provide default implementations of each feature.

Implementing a graph rarely needs to directly implement the interface. More usually, an implementation starts by inheriting from the class GraphBase. A minimal (read-only) implementation just needs to implement graphBaseFind. Wrapping legacy data often only makes sense as a read-only graph. To provide update operations, just implement the methods performAdd and performDelete, which are the methods called from the base implementations of add(Triple) and remove(Triple).

Then for testing with JUnit, inherit from AbstractGraphTest (override tests that don't make sense in a particular circumstance) and provide the getGraph operation to generate a graph instance to test.

Application APIs

Graph/Triple/Node provide the low level interface in Jena; Model/Statement/Resource/Literal provide the RDF API and the ontology API provides an OWL-centric view of the RDF data.

Where the graph level is minimal and symmetric (e.g. literal as subjects, inclusion of named variables) for easy implementation, the RDF API enforces the RDF conditions and provides a wide variety of convenience operations so writing a program can be succinct, not requiring the application writer to write unnecessary boilerplate code sequences. The ontology API does the same for OWL. If you look at the javadoc, you'll see the APIs are large but the system level interface is small.

A graph is turned into a Model by calling ModelFactory.createModelForGraph(Graph). All the key application APIs are interface-based although it's rarely needed to do anything other that use the standard Model-Graph bridge.

Data access to the graph all goes via find. All the read operations of application APIs, directly or indirectly, come down to calling Graph.find or a graph query handler. And the default graph query handler works by calling Graph.find, so once find is implemented everything (read-only) works. ARQ's query API, which includes a SPARQL implementation, included. It may not be the most efficient way but importantly all functionality is available and so the graph implementer can quickly get a first implementation up and running, then decide where and when to spend further development time - or whether that's needed at all.

Jena-Mulgara

An example of this is a prototype Jena-Mulgara bridge (work in progress as of Jan'08). This maps the Graph API to a Mulgara session object, which can be a local Mulgara database or a remote Mulgara server. The prototype is a single class together with a set of factory operations for more convenient creation of a bridge graph wrapped in all Jena's APIs.

Implementing graph nodes, for IRIs and for literals is straight forward. Mulgara uses JRDF to represent these nodes and to represent triples. Mapping to and from Jena versions of the same is just the change in naming.

Blank nodes are more interesting. A blank node in Jena has an internal label (which is not a URI in disguise). When working at the lowest level of Graph, the code is manipulating things at a concrete, syntactic level.

A blank node in Mulgara has an internal id but it can change. It really is the internal node index as I found out by creating a blank node with id=1 and found it turned into rdf:type which was what was really at node slot 1. Paul has been (patiently!) explaining this to me on a Mulgara mailing list. The session interface is an interface onto the RDF data, not an interface to extend the graph details to the client. Both approaches are valid - it's just different levels of abstraction.

If the Jena application is careful about blank nodes (not assuming they are stable across transactions, and not deleting all triples involving some blank node, then creating triples involving that blank node) then it all works out. The most important case of reading data within a transaction is safe. Bulk loading is better down via the native Mulgara interfaces anyway. The Jena-Mulgara bridge enables a Jena application to access a Mulgara server through the same interfaces as any other RDF data.

Counting and GROUP BY

2007-09-08T20:06:00.001+01:00

One thing people miss from SPARQL is counting. It's a feature that working group didn't have time for.

There's an implementation, following the design in SQL, in ARQ SVN which will be in the next release (v2.1). v2.1 introductions the cost-based optimizer for in-memory basic graph patterns by Markus.

It's a syntactic extension, not strict SPARQL, so you have to tell the system to parse queries in the "ARQ" langauge by passing Syntax.syntaxARQ to the query factory.

The following queries will work:

SELECT count(*) { ... }

SELECT (count(*) AS ?count) { ... }

This is based on having SELECT expressions as well as grouping. Using AS to give a named variable is better style because the results can go into the SPARQLXML results format; otherwise, an internal variable is allocated and they have illegal SPARQL names.

Other examples:

SELECT (count(*) AS ?rows)
{ ... }
GROUP BY ?x

SELECT count(distinct *)
{ ... }
GROUP BY ?x

SELECT count(?y)
{ ... }
GROUP BY ?x

What is being counted is solutions, in the case of count(*) and names, in the case of count(?var).

The current list of ARQ extensions is:

SERVICE - call-out from a query to a SPARQL endpoint over HTTP
SELECT expressions
GROUP BY
count()

So what features should be next?

Syntax Comparison of N3 and Turtle

2007-08-08T11:33:00.000+01:00

Some notes on the syntax differences between N3 and Turtle, with a little SPARQL thrown in.

Some of the differences are low-level issues, which are enough to trip-up machine reading of RDF data in these formats across the web. It also makes writing reliable RDF output writers harder because of variability of parsers.

RDF/XML really does win for web exchange but it is also a barrier to people who find N3 or Turtle much easier to understand and produce.

This collection of differences is not complete and I'll add and amend the note. Please let know me of anything that should be added or corrected.

Basic Federated SPARQL Query

2007-07-27T19:06:00.000+01:00

There are already ways to access remote RDF data. The simplest is to read a document which is an RDF graph and query it. Another way is with the SPARQL protocol which allows a query to be sent to a remote service endpoint and the results sent back (in RDF, or an XML-based results format or even a JSON one).

Several people writing on jena-dev have been attempting to created federated query applications where part of a query needs to sent to one or more remote services.

Here's a basic building block for such federated query use cases. It adds the ability to make a SPARQL protocol call within a query, not just send the whole query to the remote service.

Syntax

A new keyword SERVICE is added to the extended SPARQL query language in ARQ. This keyword causes the sub-pattern to be sent to a named SPARQL service endpoint, and not matched against a local graph.

PREFIX : <http://example/>
PREFIX  dc:     <http://purl.org/dc/elements/1.1/>

SELECT ?a
FROM <mybooks.rdf>
{
  ?b dc:title ?title .
  SERVICE <http://sparql.org/books>
     { ?s dc:title ?title . ?s dc:creator ?a }
}

Algebra

There is a new operator in the algebra.

(prefix ((dc: <http://purl.org/dc/elements/1.1/>))
  (project (?a)
    (join
      (BGP [triple ?b dc:title ?title])
      (service <http://sparql.org/books>
          (BGP
            [triple ?s dc:title ?title]
            [triple ?s dc:creator ?a]
          ))
      )))

Performance Considerations

This feature is a basic building block to allow remote access in the middle of a query, not a general solution to the issues in distributed query evaluation. The algebra operation is executed without regard to how selective the pattern is. So the order of the query will affect the speed of execution. Because it involves HTTP operations, asking the query in the right order matters a lot. Don't ask for the whole of a bookstore just to find book whose title comes from a local RDF file - ask the bookshop a query with the title already bound from earlier in the query.

Proper SPARQL

On top of this access operation, it would be possible to build a query processor that does what DARQ (the DARQ project is not active) does which is to read SPARQL query, analyse it, and build a query on the extended algebra.The execution order is chosen based on the selectivity of the triple patterns so it minimises network traffic.

Hopefully, given the building block in ARQ, someone will add the necessary query execution analysis to give a query broker that accepts strict SPARQL and uses a number of SPARQL services to answer the query.

SSE

2007-07-25T20:43:00.000+01:00

Following on from SPARQL S-Expressions :: a description of SSE, a notation for RDF-related data structures (like the SPARQL algebra).

Installing OracleXE

2007-06-29T11:51:00.000+01:00

We have been adding support for Oracle into SDB. As part of that, I installed Oracle XE ("Oracle Database 10g Express Edition") on my WindowsXP machine at work, which is part of a Windows domain.

It didn't go smoothly. I hope these notes help someone else trying to do the same thing.

Summary

Install when logged in as administrator (NOT a domain user, even if in group Administrators).
In order to use the command line SQL interface, you need to change SQLNET.ORA from (NTS) to (none)

Account

The Oracle installation instructions say to log in with administrative privileges and be attached to the domain.

The installation proceeded with no errors, and the 5 Windows services start up OK. But I found that I could not connect to the database web-based admin interface.

An additional symptom was that I can't change my domain password, nor create Windows local user accounts. In both cases, the error was that the password does not meet the requirements on characters and length. HP has tighter guidelines than the default for passwords but why installation of OracleXE broke a part of WindowsXP, I don't understand. After uninstalling OracleXE, I could change my password and create local user accounts as usual.

There are lots of articles about not being about to contact the database home page but only a few were related to the situation I had: this one was most useful (that link is into the OracleXE forum which is not publicly readable - you have to register first).

A way to see if your installation has been affected is to see if there is a file server\dbs\SPFILEXE.ORA. If not, the installation is probably broken.

Logging in as the local administrator account, uninstalling, reinstalling got an installation where I could get to the database home page and administer the database. I guess any local user account in group Administarors would work.

But sqlplus.exe still didn't work. (The error is "ORA-12638: Credential retrieval failed"). Following that thread again, I changed SQLNET.ORA to SQLNET.AUTHENTICATION_SERVICES = (none) and could connect to the database from the SQL command prompt.

Afterwards ...

Installing on Windows XP/Home worked fine but that is not a domained machine.

And after all that, the SDB SPARQL test suite runs perfectly with OracleXE.

Joseki 3.1

2007-06-22T13:51:00.000+01:00

New version of Joseki released, primarily to package together all the updated jars files for Jena and ARQ that Joseki uses. At the same time, other jars have been upgraded so there are jar naming changes.

Joseki 3.1 download

SPARQL Papers at ESWC 2007

2007-06-10T16:22:00.001+01:00

There were 3 papers that particularly caught my SPARQL-driven attention at ESWC2007.

SPARQLeR: Extended Sparql for Semantic Association Discovery
Krys J. Kochut, Maciej Janik

This describes an extension to SPARQL for path variables. A path is a regular expression of properties but in addition the paper describes the need for reverse properties and constraints on paths (like length).

See also: PSPARQL: http://psparql.inrialpes.fr/

Minimal Deductive Systems for RDF
Sergio Muñoz, Jorge Pérez and Claudio Gutierrez.

This is a proposal for reduced RDFS with just rdfs:domain, rdfs:range, rdfs:subClassOf, rdfs:subPropertyOf and rdf:type.

This results in (on page 8) a small set of rules that have to be applied to the data but there is no core vocabulary. The rules can be applied to a streaming data stream, if the RDFS schema is known, because each rule only refers to at most one data triple.

There are no containers, which may be inconvenient, but that might more usefully be covered by not using typing, but having a different property just to match these syntactic constructs. That removes the container vocabulary from interacting with the application vocabulary.

A colleague here, Nipun Bhatia, has been working on streaming checking and rule application based on extending Eyeball. Nipun even adds cardinality validation by preprocessing the data to get the triples in subject order. Unix sort(1) is quite capable of sorting very large N-triples files in sensible amounts of time.

Semantic Process Retrieval with iSPARQL
Christoph Kiefer, Abraham Bernstein, Hong Joo Lee, Mark Klein and Markus Stocker.

((Non) interest declaration: Markus is now spending a few months working with us in Bristol - this work was done before that.)

The core of this paper is an example where statistical techniques beats logic. There is a strong message to us all here - don't think logic and perfect organization is necessarily the best solution to actual problems.

As part of this work, but not the main argument of the paper, they created iSPARQL (i=inprecise) which is an embedding of access to similarity metrics inside standard SPARQL without syntax changes. They use property functions (they are using ARQ but the principle is quite general) to access the similarity engine.

The idea of embedding some index or other functionality that can provide bindings of variables for some expression seems like a general extension technique for SPARQL. LARQ provides free-texting matching, using Lucene to do matching, and can include all the Lucene loose matching

SPARQL S-expressions

2007-04-09T19:45:00.001+01:00

I'm interested in exposing the SPARQL algebra support in ARQ for others (and me!) to experiment with SPARQL and SPARQL extensions.

Having a syntax to be able to write algebra expressions is useful and makes writing test cases of the algebra easier. ARQ already uses S-expressions to detail the syntax tree so it was natural to use S-expressions for algebra expressions.

I split the lowest levels of syntax out, to avoid having to write a many parsers. The result - SSE (SPARQL S-Expressions), a vaguely lisp-ish syntax. It consists of lists, RDF terms (IRIs, blank nodes, prefixed names and literals) in SPARQL syntax, and also words which are plain symbols without colon.

Given this universal syntax, it's a matter of building code libraries to build the Java data structures from SSE. This is mundane but being able to do this without rebuilding a parser each time is easier.

Example query:

 PREFIX : <http://example/> 

 SELECT ?x ?v
 { ?x :p ?v 
   OPTIONAL { ?v :q ?w }
 }

which is the algebra expression:

 (project (?x ?v)
   (leftjoin
     (bgp [triple ?x <http://example/p> ?v])
     (bgp [triple ?v <http://example/q> ?w])))

The use of either () or [] for lists, where beginning and end must match, aids readability but has no other significance.

Another example: 'prefix' defines namespaces for the enclosed body:

 (prefix ((: <http://example/>))
   (project (?c)
     (filter (= ?c "world")
       (bgp [triple ?s :p ?c]) )))

It doesn't just capture strict SPARQL: tables-as-constants mean an SSE file can contain data as well

(prefix ((x: <http://example/>))
  (join
    (table
      (row [?x 1] [?y x:g])
      (row [?x 2] ))
    (table 
      (row [?y x:g])
      (row [?x 2] ))
  ))

evaluating to:

 --------------------------
 | y                  | x |
 ==========================
 | <http://example/g> | 1 |
 | <http://example/g> | 2 |
 |                    | 2 |
 --------------------------

It's still "work in progress" and a bit rough - it can be inconsistent in layout, mainly due to slipping in a quick bit of hacking between doing other things; and also this leads to different coding styles in different places. But it's already proved to be an efficient way to write SPARQL algebra expressions and evaluate them for testing.

And doing an Emacs mode for SSE is trivial.

As an aside - I did a little web-trawling for the lisp information and gathered my links together.

Some Lisp Links

2007-04-09T19:38:00.000+01:00

A partial, incomplete set of links to things about Lisp from a couple hours of web wandering. It's a bit of a change to be linking to web pages from the last millennium.

Lisp / General

The function/value namespace thing:: Scheme vs Common Lisp: http://www.nhplace.com/kent/Papers/Technical-Issues.html. Some of the arguments look a bit dated by modern standards.

Scheme

http://swiss.csail.mit.edu/projects/scheme/

Wikipedia - Scheme

http://www.r6rs.org/ - The latest Scheme definition. The nice thing, from a purely practical point of view, in this round of agreement is the definition of the library system.

Online books:

CMU Scheme repository: ftp://ftp.cs.cmu.edu/user/ai/lang/scheme/0.html

Community: http://community.schemewiki.org/

Object-oriented programming and Scheme

SLIB (A portable scheme library - "portable" seems to mean "it can be ported"). Included in SISC. http://swissnet.ai.mit.edu/~jaffer/SLIB

Websites:

http://www.schemers.org/
http://srfi.schemers.org/
SRFI - Scheme Requests for Implementation
http://readscheme.org/
http://library.readscheme.org/
Original lambda papers: http://library.readscheme.org/page1.html

Scheme / JVM Implementations

Access to access to ARQ for a SPARQL engine is important.

http://sisc-scheme.org/ (GPL 2 or MPL 1.1)
http://jscheme.sourceforge.net/ (Apache, zlib)
http://www.gnu.org/software/kawa/ (GPL 2)

Scheme / Eclipse

One of things that Java does have going for it is a free, sophisticated IDEs. Eclipse makes refactoring easy enough so as to encourage it as the project grows. For a project like ARQ, it's near essential to keep the naming and structure aligned to current terminology. Writing lisp in Emacs does not count as an IDE these days.

http://schemeway.sourceforge.net/ - not investigated yet.

http://schemeway.sourceforge.net/update-site/

Other Eclipse plug-ins? Other free, refactoring IDEs for Lisp?

Common Lisp / CLOS

Wikipedia - Common Lisp

Wikipedia - CLOS

Book: Common Lisp the Language, 2nd Edition

A Brief Guide to CLOS

http://jatha.sourceforge.net/ Common LISP library in Java (LGPL)

Common Lisp Wiki - http://www.cliki.net/

Lisp and .net

ARQ runs fine on .Net, so a CLR (.net and mono) lisp implementation is also interesting.

I didn't have time for much of a look around but did find Common Larceny: http://www.ccs.neu.edu/home/will/Larceny/CommonLarceny/download.html

Not scheme nor Common Lisp: http://dotlisp.sourceforge.net/dotlisp.htm (BSD) but last release: July 9, 2003. Patches from the authors home page.

Other

Bigloo: can call Java. Compiles scheme to the JVM (?? and CLR), can link in Java classes but I couldn't find a clear statement as to how to use in a mixed environment.

Download link to Bigloo 2.9a for the JVM broken (2007-04-08)

http://www-sop.inria.fr/mimosa/fp/Bigloo/ (GPL/LGPL)

ARQ 2.0 beta

2007-03-09T11:55:00.000Z

Just released the first ARQ 2.0 beta. This version is a complete implementation of the SPARQL query language, and also includes the ARQ featurs of custom property functions and free-text search. The plan is that this is the only beta. The big change is that it uses the SPARQL algebra for query execution, and there is a query optimizer to choose an execution strategy that makes this better than simple evaluation of the algebra operators. This makes ARQ up to date with where the workign group is going - that includes some changes of results to some queries, but, hopefully, these are restricted to queries that don't appear in the wild.

SPARQL/Update

2007-03-08T21:49:00.000Z

Modern applications are not single programs. Whether web or enterprise systems, they are a number of components running on different computers. What they do have in common is that they cooperate to deliver the application. SPARQL makes publishing RDF data on the web possible, but what about those applications that maintain and update that RDF Data? There needs to be a way for the application components to update their data. SPARQL/Update (also know as SPARUL, pronounced a bit like "spiral") is a language that takes the SPARQL style, and much of the grammar, and provides both graph update and graph management operations. It means those application components can talk a common language between themselves or to a database. Having a common update language then means the application developer can choose one RDF toolkit for one component, and another RDF system for another component, rather than having to choose one programming language and find one system that does everything required. This first draft of SPARQL/Update is published for comments, comment away!

Jena SDB

2007-02-12T15:17:00.000Z

SDB was released for the first time last week. While this is the first alpha release, it's actually at least the second internal query architecture and second loader architecture (Damian did the work to get the loader working fast).

SPARQL now has a formal algebra. ARQ is used to turn the SPARQL query syntax into a algebra expression; SDB takes over and compiles it first to a relational algebra(ish) structure then generates SQL syntax. Now there is a SPARQL algebra, this is all quite a bit simpler for SDB which is why this is the second design for query generation; much of the work now comes naturally from ARQ.

Patterns

At the moment, SDB only translates basic graph patterns, join and leftjoin expressions to SQL and leaves anything else to ARQ to stitch back together. For the current patterns, there are two tricky cases to consider:

SPARQL join relationships aren't exactly SQL's because they may involve unbound variables.
Multiple OPTIONALs may need to be COALESCEd.

For the first, sometimes the join needs to involve more than equality relationships like "if col1 = null or col1 = col2", which is a bit of scope tracking, and for the second, if a variable can be bound in two or more OPTIONALs , you have to take the first binding. The scope tracking is needed anyway.

Over time, more and more of the SPARQL algebra expression will be translated to SQL.

Layouts

SDB supports a number of databases layouts in two main classes:

Type 1 layouts have a single triple table, with all information encoded into the columns of the table.
Type 2 layouts use a triple table with a separate RDF terms table

Type 1 layouts are good at supporting fine-grained API calls where the need to join to get the actual RDF terms is removed because they are encoded into the triple tables columns. Jena's existing database layer, RDB, is an example of this. When the move was made from Jena1 to Jena2, the DB layout changed to a type 1 layout and it went faster. The two type 1 layouts supported are Jena's existing RDB layout and a debug version which encodes RDF terms in SPARQL-syntax directly into the triples table so you can simple read the table with an SQL query browser.

Type 2 layouts, where the triples table has pointers to a nodes table, are better as SPARQL queries gets larger. Databases prefer small, fixed width columns to variable string comparisons. SDB has two variations, one using 4 bytes integer indexes and one using 8 byte hashes. The hash form means that hash of query constants can be calculated and don't have to be looked up in the SQL.

It seemed that the hash form would be better all round. But it isn't - loading was 2x slower (sometimes worse) despite the fact that RDF terms don't have to be inserted into the nodes table first to get their auto-allocated sequence id. Databases we have tried are significant slower indexing 8 byte quantities than 4 byte quantities and this dominates the load performance.

There are three directions to go:

Inference support
Application-specific layout control
Filters support

(1) and (2) are linked by the fact it is looking at a query and deciding, for certain known predicates and part-patterns, that different database tables should be used instead. See Kevin's work on property tables which uses the approach to put some higher level understanding of the data back into the RDF store. (3) is "just" a matter of doing it.

And if you have some feature request, do suggest it.

ARQ : what next?

2007-02-02T15:45:00.000Z

In January, I got round to releasing a new version of ARQ and also doing a first full release of SPARQL version of Joseki. ARQ version 1.5 had a problem with a performance hit for certain database usages (boo, hiss) but this is fixed in version 1.5.1.

A key feature of this version of ARQ is support for free text search. The core indexing is done by Lucene 2. Searches bind matching resources to a variable and are done using a property function. This means they can be fast because it directly exploits the indexing capabilities of Lucene.

Example:

PREFIX pf: <java:com.hp.hpl.jena.query.pfunction.library.>
  SELECT ?doc {
    ?lit pf:textMatch '+text' .
    ?doc ?p ?lit
  }

What next? This release matches the published DAWG working draft but the working group is considering a SPARQL algebra the formalization of the semantic of SPARQL to be based on some like the relational algebra.

This version of ARQ has a number of query engines:

QueryEngine is the one used normally.
QueryEngineHTTP is a SPARQL protocol client for remote query.
QueryEngineRef is a direct, simple implementation of the SPARQL algebra.
QueryEngineQuad is a modified version of the reference query engine that compiles SPARQL to quads, not triples.

QueryEngineRef compiles a SPARQL query into the SPARQL algebra and it also provides a very simple evaluation of that algebra expression. The evaluation can be slow because it calculates all sub-expressions, then joins/left-joins/unions them but it is written to be correct, rather than fast. It is much better to extend the reference engine and convert the algebra expression into something cleverer.

If you use the --engine=ref argument to arq.sparql, it will use the reference engine. To see the algebra expression, use arq.qparse with arguments --engine=ref --print=op.

The original query engine, which is still the default one, uses a substitution algorithm to evaluate a query. This will exploit the indexes that Jena maintains for all graphs by replacing any variables already bound to some value with their current value and so giving more information to the basic graph pattern matcher. This is done in a steaming fashion which is why this query engine only takes a constant amount of memory regardless of the data size.

The next version of ARQ will combine the two approaches in a new query engine - where possible (and, for real world, queries that means nearly always), it will use the streaming, indexed approach to execution and only resort to a potentially more memory-intensive approach for parts of the query that really need it. The good news is that while it might sound like writing a whole new subsystem from scratch, it isn't. The SPARQL algebra compiler is already part of the reference engine and new query engine extends that; in addition, much of the code of the streaming engine is unchanged and it's just the conversion from the algebra to the iterator structure that needs to be written.

It's also a chance to go back and clean up some code that has been around for a long time and, with hindsight, can be structured better. My programming style has changed over the time ARQ has been in development as I try different patterns and designs then learn what works and what doesn't (makes me get frustrated at some of the design of Java as well). Some old-style code does the right thing; it just does it in a way I would not choose to do it now. Don't get that chance very often.

SPARQL Basic Graph Pattern Matching

2006-11-30T22:20:00.000Z

I wrote about the SPARQL algebra last time, not with the idea of a regular update about DAWG work but noting a significant issue being considered by the working. I hope that the wider community will comment and contribute; much of the ground work for the algebra is drawn from outside the working group anyway.

This week DAWG made a significant decision in a different, but nearby area, that of basic graph pattern matching (BGP).

Basic Graph Patterns

Basic graph patterns (BGPs) are the building block in SPARQL. They are a sequence of adjacent triple patterns in the query string. A BGP is matched against whatever is being queried and the results of matching feed into the algebra.

The decision is that no change, or rather the "implementation hint" for BGP matching, made more formal, becomes the basis of SPARQL. No queries will be changed by the decision.

The Issue

Having reveal the punch line, what's the joke? The issue is whether blank nodes in BGP matching behave like hidden, named variables or do they behave as a different kind of variable all together. This matters for counting - it does not matter for the logical meaning of a solution.

Example data:

  :a :p 1 .
  :a :p 2 .

Example query pattern:

 { ?x :p [] }

How many answers? Blank nodes are existential variables in RDF; named variables (the regular ?x ones) are universal variables. Queries don't return the binding of an existential; queries can return the binding of a named variable and the bound value of a named variables can be passed to other parts of the query (FILTERs, OPTIONALs etc) via the algebra.

In the absence of a DISTINCT in the query, are the solutions to this pattern:

1 : ?x = :a
2 : ?x = :a , ?x = :a
Either 1 or 2

In OWL-DL, existential variables give more expressivity: if there is a disjunction in the ontology, the reasoner can know that something exists, but not need to find an actual value - and it may not be able to find the value anyway - but the reasoner does know there is "something there".

Users and Implementers

For application writers, the main use of blank nodes in queries that I've seen is the convenience of using []

 {
   ?x :something [ :p ?v ; :q ?w ]
 }

[] saves having to have a named variable and splitting the expression. It would be one more thing to learn if that causes different answers (duplicates) to the pattern using query variables:

 {
   ?x :something ?z .
   ?z :p ?v ; 
      :q ?w .
 }

especially if the first pattern had been written:

 {
   ?x  :something _:bnode .
   _:bnode :p ?v ; 
           :q ?w . 
 }

which is the [] example written out with a labelled blank node. This is also why it's BGPs that are the building block, not triple patterns - blank nodes are scoped to BGPs.

For implementers, having two kinds of variable that behave different in matching can make life a harder, especially if they using some existing technology, like an SQL database which has one preferred type (universal-like). Work on SPARQL semantics suggests that there can be one (complicated) SQL statement for one SPARQL query. Nice if it's true because all the work that has gone into SQL database optimizers is reusable. Having two types of variables would need extra SQL to be generated like nested SELECTs, or some post-processing done.

More work for implementers is not good; many open source RDF toolkits are built by people in their own time or by people with other things to do at work. So, it might be a noticeable dampener on toolkit development and hence deployment. Not a good idea to do this without a reasonable need.

DAWG Resolution

Logically, duplicates don't make any difference. DAWG decided there are two solutions for simple entailment matching example above. It's what implementations currently do.

The DAWG process is often test case driven. We use test cases as both a concrete way to define what results we expect and also to make concrete decisions. So once consensus was emerging to have duplicates, the working group decided to approve a test case that captured that. In this case, the test is rdfsemantics-bnode-type-var (the example above is the same idea, just shorter).

Defining BGP Matching for SPARQL

In Last Call 2, the first CR publication and the intermediate publication versions of SPARQL, BGP matching is a complicated definition that allows for different entailment regimes for extensibility within a single entailment framework. SPARQL is defined for simple entailment, and so for anything where there a virtual graph, but it allows for extension to more complicated entailment regimes, like OWL-DL.

The trouble is the matching definition is that it has a bug in it; it allows too many solutions when the graph is redundant. The bug has to be fixed.

SPARQL is defined for simple entailment. With this decision on how blank nodes behave, the working group can now rework the BGP matching. The options are outlined in the message 2006OctDec/0140 and either of the variable mapping approaches can be made to work. It's more akin to a formalised version of the last call 1 style and the implementation hint of the complex version.

... and Extensibility

Extensibility comes by replacing the whole of BGP matching, with just a few natural conditions such as all named variables must be bound in a BGP match and there are no accidental clashes of blank nodes.

(Vested interest declaration)

OK - ARQ isn't built on SQL; it's a self contained query engine with various extension points - by default, it queries any Jena graph and exploits Jena's direct connection to the storage layer but only for basic graph patterns, not more complex patterns. It could sort out the two types of variables quite easily.

But we also have a Jena SPARQL database engine (called SDB) that is built on SQL and is specifically designed for SPARQL, for large datasets and for named graphs.

SDB fits in as an ARQ query engine and the more it can turn into a single SQL statement the better. All of the query being the ideal case (and hopefully the normal one). So making the translation to a relational quad store simpler is helpful for SDB.

An Algebra for SPARQL

2006-11-23T15:00:00.000Z

SPARQL, like Gaul, is dividied into three parts:

Basic graph pattern matching
Graph expressions
Solution modifiers

Basic graph patterns (BGPs) are a block of adjacent triple patterns that match, or don't match, all together. In BGP matching every named variable must have some value for the BGP to have been matched. Filters add restrictions on the values variables can take.

They are also an extension point in SPARQL because you can plug in a different BGP matcher (e.g. a DL reasoner or a wrapper for legacy SQL data), then reuse the other two layers to form complex queries out of the exact matches from BGP matching.

Graph expressions (OPTIONAL, UNION, GRAPH, Groups (things between {}) combine BGPs in various ways to give more complicated patterns. Graph expressions are recursive so you can have patterns within patterns. A SPARQL query has one graph expression in the WHERE clause.

Solution modifiers (Project, DISTINCT, ORDER BY, LIMIT/OFFSET) take the output of matching the query graph pattern and process it in various ways to yield the result set.

Current Situation

The semantics for SPARQL have, so far, been declarative and top-down. A solution to a query passes if it meets all the conditions following from the definitions of each of the SPARQL graph pattern forms and filters. That means, in theory, the whole of the solution is available.

In fact, ARQ builds solutions up by adding the minimum necessary at each subpattern to make the solution match. This is what gives ARQ streaming evaluation which keeps the total memory use down. But the effect is the same, whole solutions are available everywhere in the pattern.

Another way is to have a bottom-up algebra. The relational algebra works this way. Subexpressions are evaluated to give tables (relations) and then these tables combined together to form new tables.

It turns out that these are nearly the same as shown by Richard Cyganiak and Jorge Perez et al (see references below). The class of graph patterns that differ are a certain kind of nested OPTIONAL where a variable is used on the outside, fixed part, and in the inner OPTIONAL, but not in between.

SELECT *
{ :x1 :p ?v .
  OPTIONAL
  { :x3 :q ?w .
    OPTIONAL { :x2 :p ?v }
  }
}

Now that is a rather unusual query. The tricky bit is the use of ?v at the outermost and innermost levels but not in between.The query can be rewritten so as not to nest (note the repeat of :x3 :q ?w).

SELECT *
{ :x1 :p ?v .
  OPTIONAL
    { :x3 :q ?w }
  OPTIONAL 
    { :x3 :q ?w  . :x2 :p ?v }
}

A few references for work in this area:

A relational algebra for SPARQL
Semantics and Complexity of SPARQL
Follow up to the paper above: Semantics of SPARQL
The paper "Semantics Preserving SPARQL-to-SQL Query Translation for Optional Graph Patterns" includes doing the difficult case of nested optionals.

A SPARQL Algebra

In DAWG, we're considering an algebra for SPARQL, based on the paper Semantics of SPARQL. This will mean a change of results in the case above. I've never seen such a query in the wild, only in artificial test cases.

The change from declarative semantics to a constructional algebra is motivated primarily by the implementers in the working group wanting to apply all the good stuff on relational algebra optimization to SPARQL engines. The complexity of the exact mapping to SQL in the semantics preserving SPARQL-to-SQL is daunting.

Not that simple!

But other things differ as well if a purely relational style is applied (and that's not being proposed currently) because "Semantics of SPARQL" does not consider the difference in treatment of filters (it's focus is on the combination of graph patterns).

Two cases arise: one where filters are in OPTIONALs, and one where filters are nested inside groups.

SELECT * 
{ ?x :p ?v .
  OPTIONAL
  { 
    ?y :q ?w .
    FILTER(?v = 2)
  }
}

The FILTER uses a variable from the fixed part of the OPTIONAL. Under Jorge's semantics the variable isn't in-scope, so the filter evaluation is an error (unbound variable), otherwise known as false; the optional part never matches. This form of query is realistic and does occur for real so the current proposal for DAWG makes this work. Like SQL and LEFT OUTER JOIN with the ON clause, the LeftJoin operation in the SPARQL algebra can take a condition which applies over the whole LeftJoin.

The fixed pattern could be repeated inside the optional part but such repetition for something application might well use is bad, very bad.

Application writers will have to take care about scope and groups: putting FILTERs inside {} changes their scope.

Currently,

{ :x :p ?v . FILTER(?v < 5) }

and

{ :x :p ?v . { FILTER(?v < 5) } }

have the same effect. But they aren't in the algebraic form because { FILTER(?v < 5) } evaluates on the empty table that does not have a ?v in it; evaluation is an error and hence false.

ARQ

There is an implementation of the algebra in ARQ in CVS (not in the current release ARQ 1.4). It's enabled in the command line tool arq.sparql with --engine=ref from the command line and

QueryEngine2.register() ;

in code.

The work-in-progress unfinished editor's working text is available. Check it is actually up to date because that's just work space and isn't a DAWG document. It does not reflect working group decisions - it more a proposal for consideration.

Disclaimer: Any views expressed here are mime and not the working group (which at the time of writing is thinking about it but hasn't decided anything yet).

LARQ = Lucene + ARQ

2006-11-12T19:40:00.000Z

SPARQL is normally thought of as only querying fixed RDF data. At the core of SPARQL are the building blocks of basic graph patterns, and on top of these there is an algebra to create more complex patterns (OPTIONAL UNION, FILTER, GRAPH).

The key question a basic graph pattern asks is "does this pattern match the graph". The named variables record how the pattern matches.

Not all information needs to be in the raw data. ARQ property functions are a way to let the application add some relationships to be computed at query execution time.

LARQ adds free text search. The real work is done by Lucene. LARQ adds ways to create a Lucene index from RDF data and a property function to perform free text matching in a SPARQL query.

Example: find all the string literals that match '+keyword'

PREFIX pf: <java:com.hp.hpl.jena.query.pfunction.library.>

SELECT *
  { ?lit pf:textMatch '+keyword' }

Any simple or complex Lucene query string can be used.

LARQ provides utilities to index string literals. As the literal can be stored as well, a query can find the subjects with some property value matching the free text search.

So to find all the document that have titles matching some free text search:

PREFIX pf: <java:com.hp.hpl.jena.query.pfunction.library.>
PREFIX dc: <http://purl.org/dc/elements/1.1/>
  
SELECT ?doc {
    ?lit pf:textMatch '+text' .
    ?doc ?p ?lit
  }

More details in the ARQ documentation for LARQ

This will be in ARQ 1.5 but is available from ARQ CVS now. Hopefully, this will be useful to users and application writers. Comments and feedback on the design are welcome, especially before the next ARQ release.

Assignment Property Function

2006-10-13T14:08:00.000+01:00

SPARQL is a graph pattern matching language, The matching can be semantic (basic graph patterns are entailed by the data in order to match) or through the algebra that works over the top of basic graph pattern matching.

Complex queries make use of UNION and OPTIONAL, including the idiom with OPTIONAL and !BOUND, in all sorts of creative ways. And sometimes they want the answers to indicate which way the query matched to get a particular solution.

PREFIX skos: <http://www.w3.org/2004/02/skos/core#>

SELECT ?label
{
   { ?concept skos:prefLabel ?label }
 UNION
   { ?concept skos:altLabel ?label }
}

Which matched? the prefLabel or altLabel? The application can assign the different to branches to different variables although that might be inconvenient in a larger query if ?label is used elsewhere in the query.

PREFIX skos: <http://www.w3.org/2004/02/skos/core#>

SELECT ?label_pref ?label_alt
{
  { ?concept skos:prefLabel ?label_pref }
UNION
  { ?concept skos:altLabel  ?label_alt }
}

ARQ's property functions provide a way of adding different ways to match a triple pattern. Uses include calling out to custom code to perform some calculation, or calling out to use a external index, such as Lucene.

Property functions can assign to variables in the solution - unlike FILTER functions which must not have side effects. Property functions can't change values but they can bind an unbound variable or check an existing binding is compatible.

PREFIX apf:   <java:com.hp.hpl.jena.query.pfunction.library.>
SELECT ?x
{
 ?x apf:assign "Hello World"
}

-----------------
| x             |
=================
| "Hello World" |
-----------------

It works both ways round: { "Hello World" apf:assign ?x } gives the same results.

If subject and object are constants or already bound, apf:assign checks to see if they are the same. If they are, the tripe pattern matches with no change to the solution, otherwise it does not match and that solution is rejected. The "sameness" is Jena's sameValueAs, just like the rest of graph matching. If both variables are unbound, apf:assign complains and the query is broken.

Parameterized Queries

2006-05-07T17:17:00.000+01:00

Sometimes, an application will be making a SPARQL query, using the results from a previous query or using some RDF term found through the other Jena APIs.

SQL has prepared statements - they allow an SQL statement to take a number of parameters. The application fills in the parameters and executes the statement.

One way is to resort to doing this in SPARQL by building a complete, new query string, parsing it and executing it. But it takes a little care to handle all cases like quoting special characters; you can at least use some of the many utilities in ARQ for producing strings such as FmtUtils.stringForResource (it's not in the application API but in the util package currently).

Queries in ARQ can be built programmatically but it is tedious, especially when the documentation hasn't been written yet.

Another way is to use query variables and bind them to initial values that apply to all query solutions. Consider the query:

PREFIX dc <http://purl.org/dc/elements/1.1/>
SELECT ?doc { ?doc dc:title ?title }

It gets documents and their titles.

Executing a query in program might look like:

import com.hp.hpl.jena.query.* ;

Model model = ... ;

String queryString = StringUtils.join("\n",
         new String[]{
     "PREFIX dc <http://purl.org/dc/elements/1.1/>",
     "SELECT ?doc { ?doc dc:title ?title }"
         }) ;
Query query = QueryFactory.create(queryString) ;
QueryExecution qexec =
    QueryExecutionFactory.create(query, model) ;
try {
    ResultSet results = qexec.execSelect() ;
    for ( ; results.hasNext() ; )
    {
       QuerySolution soln = results.nextSolution() ;
       Literal l = soln.getLiteral("doc") ;
    }
} finally { qexec.close() ; }

Suppose the application knows the title it's interesting in - can it use this to get the document?

The value of ?title made a parameter to the query and fixed by an initial binding. All query solutions will be restricted to patterns matches where ?title is that RDF term.

QuerySolutionMap initialSettings = new QuerySolutionMap() ;
initialSettings.add("title", node) ;

and this is passed to the factory that creates QueryExecution's:

QueryExecution qexec = 
    QueryExecutionFactory.create(query,
                                 model,
                                 initialSettings) ;

It doesn't matter if the node is a literal, a resource with URI or a blank node. It becomes a fixed value in the query, even a blank node, because it's not part of the SPARQL syntax, it's a fixed part of every solution.

This gives named parameters to queries enabling something like SQL prepared statements except with named parameters not positional ones.

This can make a complex application easier to structure and clearer to read. It's better than bashing strings together, which is error prone, inflexible, and does not lead to clear code.

From RDQL to SPARQL

2006-04-13T10:07:00.000+01:00

SPARQL is now (April 2006) a W3C Candidate Recommendation which means it is stable enough for wide spread implementation. Actually, there are quite a few implementations already (SPARQL implementations page on ESW wiki).

SPARQL is defined by three documents:

and there are tutorials like this one.

RDQL predates SPARQL - in fact, RDQL design predates the current RDF specifications and some of the design decisions in RDQL are a reflection of that. The biggest of these is that RDF didn't have any datatyping so RDQL handles tests on, say, integers without checking the datatype (if it looks like an integer, it can be tested as integer).

SPARQL has all the features of RDQL and more:

ability to add optional information to query results
disjunction of graph patterns
more expression testing (date-time support, for example)
named graphs
sorting

but, above all, it is more tightly specified so queries in one implementation should behave the same in all other implementations.

ARQ - A Query Engine for Jena

In parallel with the developing the SPARQL specification, I have been developing a new query subsystem for Jena called ARQ. ARQ is now part of the Jena download.

ARQ builds on top of the existing Jena query support for matching of basic graph patterns (BGPs are the building block in SPARQL). ARQ can execute SPARQL and RDQL as well as an extended form of SPARQL. It has several extension points, such as Property functions. The ARQ query engine works with any Jena Graph or Model.

Converting RDQL code to SPARQL code

The functionality of RDQL is a subset of SPARQL so it's not hard to convert RDQL queries to SPARQL. What needs to be done is convert the triple syntax and convert any constraints.

Syntax

SPARQL syntax uses a Turtle-like syntax which is familiar to anyone knowing N3. Namespaces go at the start of the query, not after like USING. There are no () around triple patterns; instaead there is a "." (a single dot) between triple patterns. An RDQL only ever has one graph pattern, in SPARQL, blocks of triple patterns are delimited by {}

You can even use the command line arq.qparse to read in an RDQL query and write out the SPARQL query but it's a rough approximation you'll need to check and it may not be completely legal SPARQL.

Constraints

The constraints need the most care because SPARQL uses RDF datatyping and RDQL doesn't. Some common areas are:

regular expressions
string equality and numeric equality

Regular expressions

A SPARQL regular expression looks like:

regex(expr, "pattern")
regex(expr, "pattern", "i")

The catch is that the expr must be a literal; it can't be a URI. (Well - it can, but it will never match!). If you want to perform a regular expression match on a URI, use the str() built-in to get the string form of the URI.

regex(str(?uri), "^http://example/ns#")

Equality

RDQL has = for numeric equality and eq for string equality. A number in RDQL was anything that can be parsed an a number, whether it had a datatype or not (or even the wrong datatype). Likewise, anything could be treated as a string (like URIs in regular expressions).

SPARQL has = which is taken from XQuery/XPath Functions and Operators. It decides whether that is numeric equals, string equals or URI-equals based on the kind of arguments it is given.

API Changes

The ARQ API is in the package com.hp.hpl.jena.query. The RDQL API is deprecated, starting with Jena 2.4. The new API is similar in style to the old one for SELECT, with iteration over the rows of the results (javadoc). Differences include the widespread use of factories, naming consistent with the SPARQL specifications, and different exec operations for the different kinds of SPARQL query. QueryExecution objects should be properly closed.

One change is that to get the triples that matched a query, instead of asking the binding for the triples that were used in the matching, the application should now make a CONSTRUCT query.

Experimenting with SPARQL

There is a set of command line utilities to try out SPARQL queries from the command line.

A nice graphical interface is twinkle by Leigh Dodds.

There is also an implementation of the SPARQL protocol using ARQ, project Joseki, and a demo site at http://www.sparql.org where you can validate SPARQL queries and try them out.

Questions?

Send question and comments about ARQ to jena-dev.

Send general questions and comments about SPARQL to the W3C list sparql-dev (archive).

If you have experiences converting from RDQL to SPARQL, then let me know and I'll compile a list of common issues.

Property Functions in ARQ

2006-02-16T18:35:00.000Z

These are properties that are calculated by some custom code, and not done by the usual matching. There are two provided now: applications are free to provide application-specifc ones.

list:member - access the members of an RDF list.
rdfs:member - access the members of rdf:Bag, rdf:Seq and rdf:Alt structures

Full Extension documentation

Normally, the unit of matching in ARQ is the basic graph pattern (a sequence of triple patterns). These sets of triple patterns are dispatched to Jena for matching by Jena's graph-level query handler. Each kind of storage provides the appropriate query handler. For example, the database fastpath is a translation of a set of triple patterns into a single SQL query involving joins.

There is also a default implementation that works by using plain graph find (a triple with possible wildcards) so a new storage system does not need to provide it's own query handler until it wants to exploit some feature of the storage.

If a function property is encountered, then it is internally treated as a call to be an extension. There is a registry of function properties to implementing code.

  # Find all the members of a list (RDF collection)
  PREFIX  list:   <http://www.jena.hpl.hp.com/ARQ/list#>
  SELECT ?member
  { ?x :p ?list .
    ?list list:member ?member .
  }

The functionality of list:member is handled by a class in the extension library so this query is treated much like the ARQ extension:

  # Find all the members of a list (RDF collection)
  PREFIX  ext: <java:com.hp.hpl.jena.query.extension.library.>
  SELECT ?member
  { ?x :p ?list .
    EXT ext:list(?list, ?x)
  }

where ext:list is a function that bind its arguments (unlike a FILTER function). The property function form is legal SPARQL.

So, this mechanism shows that collection access can be done in SPARQL without resorting to handling told blank nodes.

cwm (which is a forward chaining rules engine) and Euler (which is a backward-chaining rules engine) already provide this style of access. Their property is - the subject and object meanings are the other way.

ARQ provides list:member to be like rdfs:member.

— Andy

Progress with Jena.Net

2006-02-11T18:26:00.000Z

[GNU] wrote about building Jena for Mono, using IKVM to compile the jar files into .Net IL.

This approach means that the same source code is used for both the Java world and the .Net world, making future improvements visible to both from a single source tree.

I tried doing it for .Net on Windows with C# Express and IKVM-0.24.0.1.

Summary

SPARQL queries work.

Using Jena from C# works for small scale cases - lots of checking to do but it should be a matter of verifying everything from the dependent libraries works properly.

Some things aren't working but there are a few hotspots of trouble that, when fixed, mean that the majority (may be all) of the Jena test suite will run. As it is at the moment, quite a lot can be done including using the ARQ command line programs.

The Conversion

The IKVM bytecode conversion route is my preferred choice because it means one source codebase, not two. When I tried this before, I got an early version of ARQ up and running. But it wasn't complete; the first big block was the lack of java.nio.charset support in GNU Classpath. Jena and ARQ have lots of tests of internationalization and charsets. That alone was enough to make it not worthwhile exploring further at the time.

Now (Feb 2006) GNU Classpath coverage is much better. See the coverage of GNU Classpath compared to Java 1.4.

The process is simple: run ikvmc on all the jars to get a library. Ignore all the warnings about missing stuff. It's surprising what various libraries actually reference - Log4j has references to a lot of log record transports. At the simplest:

ikvmc *.jar -out:XXX.dll -target:library

I've now broken this in two DLLs: jena-libs.dll (all the jars except the jena ones) and jena.dll (jena.jar, jenatest.jar, arq.,jar, iri.jar) but that is just because I keep building the DDLs while testing.

It takes a minute or so (less time than building jena.jar itself). The result is two DLLs of about totaling 16M - the whole assembly is about 23M including the three IKVM DLLs. Not small - but it works and it is simple to do.

What's been tried: in-memory graphs, reading and writing turtle files (but XML types literals broken) and SPARQL queries.

Jena bugs: (this is relative to CVS and so after Jena 2.3)

file:///c:/absolute was incorrectly turned into a windows filename. Worked OK with Sun's Java but not IKVM. Fixed.

GNU Classpath bugs:

InputStreamReader(InputStream, Charset) is broken although the other two constructors that allow the charset conversion to be explicitly controlled do seem to work. This can be worked around in Jena. Bugzilla Entry.
Zero-width lookbehind regexs aren't implemented. They are used by JJC's new IRI code. Bugzilla Entry.

ARQ Test Suite

As a rough comparision, I ran the ARQ test suite:

BEfore any fixes, with Java 5 JVM:
Tests run: 1119, Failures: 0, Errors: 0

Using ikvm as the JVM:
Tests run: 1119, Failures: 32, Errors: 17

Converting to .Net:
Tests run: 1119, Failures: 32, Errors: 59

[20 Feb: JJC recoded around the lack of lookbehind and now its down to 4 failures of which 3 are because GNUClasspath is just different to Sun's runtime]

Now it's work through the broken tests in the ARQ test suite to determine what's the cause as time permits.

IronPython to Jena?

Updates

Calling Jena from VB.Net works
The GNU Classpath/InputStreamReader bug has been fixed
The GNU Classpath/lookbehind bug had already been fixed but very recently so IKVM hasn't picked it up yet.

Now 4 failures, 3 of which are corner case differences of URI resolution in unusual cases.