This paper presents a binary format for both storing OWL ontologies and describing changes in OWL ontologies. The format is designed to be a fast to parse and serialise format. It is intended as a low level storage and transmission mechanism rather than an end user exchange syntax. Software to parse and serialise binary OWL has been implemented in the form of OWL API parsers and renderers. Some initial experiments seem to indicate that a Binary OWL ontology document can be parsed roughly an order of magnitude faster than the corresponding RDF/XML document.
used as an exchange syntax between tools (although with support in commonly used APIs it could be), rather it is designed to enable applications to support speci c self-contained functionality in a performant way. 2
OWL 2 OWL 2 is the latest standard in ontology languages from the W3C.
For the purposes of this paper an OWL 2 ontology is a set of annotations, a
set of axioms, and a set of imports declarations that can be optionally named
with an Internationalised Resource Identi er (IRI) and a version IRI. Axioms
are statements which specify how entities (classes, properties and individuals)
or complex classes in the domain of interest are related to each other. For a
full description see the OWL 2 Structural Speci cation and Functional-Style
Syntax speci cation [
RDF Graph Based Syntaxes (RDF/XML) As pointed out above, the
normative exchange syntax for OWL 2 ontologies is RDF/XML. As the name
suggests, RDF/XML is an (XML) eXtensible Markup Language based format for
storing RDF graphs. Since OWL 2 ontologies can be mapped into RDF graphs
they can be stored in RDF/XML. To store an OWL 2 ontology in RDF/XML
it is rst necessary to translate it to an RDF Graph using the transformation
to triples de ned in Table 1 and 2 of [
Non-RDF Graph Based Syntaxes Besides RDF/XML and the other avours of RDF graph based syntaxes there exist several other syntaxes which can be used persist OWL ontology documents. OWL/XML is straightforward XML based syntax which can be queried and manipulated with o -the-shelf XML tools. While relatively simple, OWL/XML is extremely verbose|even more verbose than RDF/XML. This means that parsing an OWL/XML version of an ontology document can take as long, or usually longer, than parsing an RDF/XML equivalent. Other syntaxes include the Manchester Syntax, which is designed for use in editing tools such as Protege, and the OWL 2 Functional-Style Syntax, which is used to specify the structure of objects in OWL 2 ontologies in a concrete way. All of these are textual based syntaxes which can be edited in a regular text editor.
Binary le formats Binary les are computer les that are not plain text
based ( les whose bytes aren't aligned to human readable characters). In recent
years there has been a shift away from binary le formats to text based formats,
in particular markup languages such as XML. One of the main reasons for this
shift is the ease in which text based formats, such as XML, can easily be shared
between 3rd party tools and can also be parsed and processed on disparate
platforms (providing a common standard encoding of characters is used such as
UTF-8). Another bene t of textual based formats is that they can be opened,
inspected and tinkered with using a simple text editor|a comfort blanket for
many people, including power users and developers. When a binary le format
is opened in a text editor, the 8 bit blocks of bytes are interpreted as characters,
leading to an unreadable mess. Because of this, unlike a le that is based on a
textual format, it is di cult to repair a damaged or corrupt binary le by hand.
This means that standards and versioning are particularly important when it
comes to binary le formats|it is non-trivial to reverse engineer a binary le
format. Despite good motivations for and the widespread use of text based le
formats such as XML, binary formats have an advantage in terms of performance.
First, binary les tend to be more compact than text based alternatives. There
are typically fewer bytes to read in a binary le than the text based equivalent.
Second, binary les are typically geared towards being fast to parse. In the
extreme case a binary le does not need to be parsed if it is the exact copy of an
in memory based representation of an object or set of objects|the bytes in the
le simply need to be blitted into main memory to load the objects stored in the
le. Where this kind of blitting isn't possible, binary formats can be optimised
for fast parsing since they can store information in an order that is preferred for
parsing rather than in an order that is more palatable to a human reader.
Binary RDF There has recently been an e ort to introduce a binary format
for RDF graphs [
Binary Compatibility Cross Platform Issues One major issue for those working with binary le formats is that of byte ordering, usually known as Endianness. There are two avours: Big Endianness, where the most sign cant byte comes rst, and Little Endianness, where the least signi cant by comes rst. For more information and an example, see the Wikipedia article on Endianness http://en.wikipedia.org/wiki/Endianness. Di erent platforms can use di erent byte orderings and an important consideration in designing a binary le format is to choose one type and stick to it|a le that uses a Big Endian encoding cannot be read by a parser that expects a Little Endian encoding. 3
In what follows Binary OWL is described. It should be noted that this paper is not meant to serve as a precise speci cation of the syntax rather it just presents some of the salient ideas behind the syntax.
A Binary OWL Document is a binary le with a Big Endian encoding. Binary
OWL uses the concept \chunks" which are blocks of binary data of a speci c
type. Each chunk begins with 4 bytes marking the length of the chunk, followed
by 4 bytes marking its type followed by the chunk data which is of the speci ed
length in bytes. The concept of chunking was inspired by the use of chunks in the
PNG speci cation [
Document Header Each binary ontology document begins with a header which contains the usual information such as a magic number identifying that the contained document is Binary OWL and version information for the format. The header also contains a metadata chunk that can be used to store arbitrary metadata that should not necessarily be contained in the actual ontology stored in the document (such as generator, creation time etc.). The metadata chunk is akin to comments in an XML le but slightly more expressive in that property value pairs (of various types) can be stored. Some basic information (a subset of what is usually considered to be \ontology header" information) follows the document header. This ontology header contains the IRI and version IRI (if present) of the ontology contained within the document along with a possibly empty list of OWL imports declarations.
IRI Lookup Table A key component of Binary OWL documents are IRI lookup tables. Lookup tables are used to index IRIs contained in the signature of OWL ontology objects. These indices are then used in the representation of OWL objects throughout the Binary OWL ontology document. The main advantage of IRI lookup tables is that (1) they help to make the whole ontology document much more compact|replacing all occurrences of a commonly occurring IRI string, which could be tens of characters long, saves a lot of bytes. This compacting e ect helps makes the le smaller and faster to read. (2) The IRI table provides an cheap interning mechanism for objects representing IRIs when the ontology is parsed|only one object is used for a given IRI and it is cheap to access these objects because they are pointed to by indices rather than being stored within some kind of map. The net e ect is that fewer objects need to be created in memory which reduces parsing time and memory footprint. In every Binary OWL document there is a main IRI lookup table, which follows the document header, for the main document data block.
Document Data Following the IRI table comes the main document data block which essentially speci es a set of ontology annotations and then a set of axioms for the ontology described in the document. The next two sections below describe how components of this data block are structured. In the current version of Binary OWL a simple encoding mechanism is used which simply lists annotations and then axioms in their binary encoding. In future versions of Binary OWL one could imagine some other encoding scheme which could take advantage of the shared/repeating structure of axioms and their sub-components to produce smaller les, however, as with all compression algorithms there are some space/time tradeo s and more investigation would be needed before setting on a preferred encoding.
Representation of OWL Objects The various kinds of objects, such as axioms, class expressions, data ranges, entities and literals that are de ned in the OWL 2 Structural Speci cation and can be used in various places within an OWL ontology document are encoded in what is in essence a compact version of the Functional-Style syntax. Each type of object is assigned a 1 byte type marker which is written out to mark the start of the object. Next, the various sub-objects, in the order that they appear in the functional-style syntax, are written out. For example, consider SubClassOf(:A ObjectSomeValuesFrom(:R :B)). First the marker byte for SubClassOf (which has a decimal value of 36) is written out. Next, the class :A is written out by writing the marker value corresponding to class names (which has a decimal value of 4) followed by a variable length integer that is the index for :A in the IRI table. The same is repeated for the sub-object ObjectSomeValuesFrom(:R :B) and its sub-objects :R and :B. Representation of Lists and Sets Many OWL 2 constructs consist of sets or lists of objects. For example, component of an ObjectIntersectionOf is a set of class expressions. Additionally, the main top level components of an ontology are sets (of axioms and annotations). Given a collection (set or list) of objects of size n, the Binary OWL format stores the collection using a variable length int (1 - 4 bytes) to store n followed by the serialisation of the n objects that are contained in the collection. It was decided to use a variable length int, rather than say a 4-byte int, because the use of collections can be numerous in any given ontology. In large ontologies, such as SNOMED-CT there can be huge numbers of small collections and storing the size of each collection as a 4-byte int can signi cantly blow up the size of the whole ontology serialisation. A further bene t of this scheme is that it enables precise advanced memory allocation during parsing. When adding items to collections such as sets, lists and maps, programs written in Java can obtain a substantial runtime performance boost by allocating enough memory to hold the complete nal collection. This is especially true of HashSets which require additional memory to be allocated and moreover need to be rehashed (an expensive operation) when an item is added that requires a capacity increase of the HashSet. Thus, allocating precisely enough memory (not too little and equally important not too much) to hold all axioms and hold the numerous other sets of objects that are required in an ontology can lead to faster parsing and can decrease the memory foot print required to hold the parsed ontology in memory.
Encoding of Strings and Literals Many ontologies contain literals as the
values for annotations. In Binary OWL most types of literals are represented
as arrays of UTF-8 encoded characters followed by an index to the IRI
representing the datatype. In terms of encoding strings, a similar mechanism to
the storage of collections are used where the length of the array is encoded
followed by an array of the speci ed length in bytes. For literals that are typed as
rdf:PlainLiteral, xsd:String and xsd:Boolean more compact encodings are used that
omit the datatype pointer and in some cases (e.g. xsd:Boolean) require less bytes
that a raw string representation would require.
As well as a need for performant parsing and serialisation capabilities,
applications typically have robustness requirements which can dictate the choice of
document storage technologies. For example, if an ontology editing application
crashes, or the machine that it is hosted on needs to be restarted, there is
potential for data loss|any changes that have been made since the last save operation
will be lost. This problem can be mitigated to some extent by persisting
ontology changes to disk as they happen. However, the normative and other main
exchange syntaxes such as OWL/XML are XML based meaning that it is not
possible to append changes to existing documents. The upshot of this is that for
small document changes, such as adding an axiom or annotation to an ontology,
the whole ontology document needs to be recreated and rewritten out for that
ontology. The traditional approach to this has been to use database back end
stores, for example [
In order to determine the di erences between parsing a le stored in the normative RDF/XML exchange syntax and Binary OWL, and to look for further areas of optimisation, we implemented an OWL API parser and renderer for Binary OWL and carried out some small scale casual experiments. It should be noted that we decided that a comparison should be made with parsing RDF/XML rather than, say OWL/XML, for two reasons: (1) RDF/XML is the normative (and most widely used) OWL exchange syntax that all OWL tools must support, and (2) some pilot experiments using the OWL API indicated that for a given ontology its RDF/XML parser provides faster parsing performance than its OWL/XML parser. Therefore, the results which follow also hold for OWL/XML in the sense that performance gains provided by Binary OWL over RDF/XML will also be performance gains for Binary OWL over OWL/XML. The software is written in Java and uses the java.io classes DataInput and DataOutput for reading and writing primitive data such as bytes, ints and strings in a crossplatform way by using a big endian encoding.
Several well-known large ontologies ranging from 886,578 axioms in size to 6,062,769 axioms in size, were used for the experiments. The ontologies are shown in Table 2, which shows the number of axioms, the number of logical axioms, the number of annotation axioms, the le size of the RDF/XML le in Megabytes and the le size of the Binary OWL le in Megabytes.
Method To ensure comparable results over the corpus and eliminate network delays each ontology and its imports closure was rst loaded with the OWL API (version 3.4.3), processed so that the imports closure was merged into one ontology, then saved into an RDF/XML le and also a binary OWL File. Next, for each ontology its RDF/XML le and its Binary OWL le were parsed by the OWL API RDF/XML parser and the Binary OWL parser implemented as part of this work. The CPU time taken to parse each le alone, ignoring the time taken to index objects into the OWL API data structures, was recorded and averaged over 10 rounds. The results are shown in Table 3. Analysis As can be seen from Table 2, the size of a Binary OWL le is roughly 4 times smaller than the corresponding RDF/XML le. The main compression comes from using IRI indexes and from compressing away the language vocabulary that is used in RDF/XML (and other serialisations such as the FunctionalStyle Syntax). Even though the RDF/XML parser in the OWL API is highly tuned (even very large ontologies such as the NCBI Taxon ontology, which contains over 6 million axioms, can be parsed in approximately 1 minute of CPU time) parsing the binary OWL version of an ontology document is on average an order of magnitude (between 8 and 12 times) faster than parsing the RDF/XML version of the document. In some cases the time di erence, e.g. 6.56 seconds versus 60 seconds for the NCBI Taxon ontology, could have a large impact on applications that require frequent loading of large numbers of ontologies (or indeed very frequent loading of lots of smaller ontologies). 6
This paper has introduced the idea of a binary format for OWL. The main motivation for this work was to produce a le format geared towards the fast parsing and serialization of OWL ontologies. The format is intended for internal application use rather than being yet another exchange syntax or human consumption format. Although simple, with further room for optimisation, the format looks promising and is roughly an order of magnitude quicker to parse than RDF/XML.
Finally, although the Binary OWL spec is relatively stable, some small details are still being nalised. A release of some libraries for working with Binary OWL is therefore part of future work. Developers who are interesting in trying out the format in its current form should contact the authors.
Acknowledgements This work was supported by Grant GM103316 from the National Institute of General Medical Sciences of the United States National Institutes of Health.