Markus Stocker bio photo

Markus Stocker

Between information technology and environmental science with a flair for economics, the clarinet, and the world of soups and salads.

Email Twitter Google+ LinkedIn Github

Which are the Swiss cantons that define the Swiss national border? Does Italy have states within its national border? Which US States overlap with the Ogallala Aquifer?

After roughly 60 posts, this is my first with a more technical nature. I did promise to keep things accessible to as many readers as possible. Therefore, I’ll try to give my best also in technical posts to first and foremost tell a story and introduce the more technical details later, labeling them as such.

During the last few months, I have sporadically been working on a software tool, PelletSpatial, that is able to answer questions like those exemplified above. In a nutshell, if you provide information about (geographical) regions, e.g. countries like France and Germany, in particular information about relationships between regions, e.g. France borders Germany, the tool allows you to ask questions about the regions and their relationships, e.g. which countries border the Czech Republic?

Perhaps, one of the more interesting features of PelletSpatial is its inference capability. For instance, if you describe Madison as a city of Dane County as a county of the US State Wisconsin as one of the fifty states in the USA and then ask for regions within the USA you get not just Wisconsin but also Madison and Dane County as results, even though, in the data, only Wisconsin is stated to be a region within the USA. In short, you get explicit and implicit results. Follow the link if you would like to try this example online. (Note that, in the example, NTPP represents the relationship between two regions for which the first is within the second. The reason why it is called NTPP is explained below in the technical notes.)

Today, Clark & Parsia and I are announcing the first public release of PelletSpatial. If you are interested, follow the link to download it. I would like to thank Clark & Parsia, in particular Evren and Kendall, for the collaboration and support. For questions, issues and ideas regarding PelletSpatial feel free to send a message to the Pellet users mailing list.

Technical notes. We use the Region Connection Calculus (RCC) as underlying formalism. RCC serves for qualitative spatial data representation and reasoning by providing basic relations between two regions. Currently, we support the eight basic topological relations, i.e. RCC-8: disconnectedFrom (DC), externallyConnectedTo (EC), partiallyOverlaps (PO), equalsTo (EQ), tangentialProperPartOf (TPP), nonTangentialProperPartOf (NTPP), hasTangentialProperPart (TPPi) and hasNonTangentialProperPart (NTPPi).

PelletSpatial supports two reasoning engines. The first is based on the translation suggested by Y. Katz and B. Cuenca Grau in their paper Representing Qualitative Spacial Information in OWL-DL. We translate RCC-8 constraint networks into a (OWL-) Description Logics (DL) Knowledge Base on top of which we perform queries using Pellet, an open source reasoner for OWL 2 DL in Java supported and distributed by Clark & Parsia. The second reasoning engine, which is used as default in PelletSpatial, is based on the RCC-8 composition table and uses a path consistency algorithm to check the consistency of RCC-8 constraint networks. This engine uses a dual stage conjunctive query answering algorithm, where the first stage answers spatial query patterns over a consistent RCC-8 constraint network. The bindings returned by this stage are given as input to the second stage which consists in refining the bindings to match non-spatial query patterns, a process executed over a consistent Pellet KB.

In addition to a customized RCC-8 “friendly” data format (which may be interesting to demo the application but less so in real applications,) we support parsing of RCC-8 spatial relationships represented in RDF/OWL. For this to work, you need to either directly use the vocabulary provided by PelletSpatial or define your own RCC-8 vocabulary as subPropertyOf PelletSpatial’s vocabulary by adding appropriate axioms in your ontology (which is, essentially, a mapping between your ontology and the one defined by PelletSpatial using subPropertyOfaxioms).

Further, PelletSpatial supports querying over RDF/OWL data that describes spatial RCC-8 relations mixed with standard semantic RDF relations. This allows us to query for regions and their relationships according to RCC-8 semantics and metadata about the regions described in RDF (e.g. “give me all the Swiss cantons that border Switzerland and have a population greater than 350,000”). Note that, as in one reasoner RCC-8 regions are translated to DL concents, we use Pellet’s support for punning to use names (i.e. region terms) for both OWL classes and individuals.

You should find examples, a README and licensing information in the distribution. The version of this release is 0.1, meaning the software is, currently, a proof-of-concept and should be treated as such. Feel free to contact the Pellet users mailing list with questions, issues and ideas. For issues, try to submit a complete and minimal example in both code and data that helps to quickly identify the problem.