Hello,

In order to not use an external reasoner each time, I got to ask how can we implement our own reasoning capabilities in a triple store as to do deductions on the triple store? BigOWLim do this but how about creating ours? doable? hard to do it? needs lots of time? complicated? will I need an ontology OWL DL or OWL RL 2 ...etc ?

And plz, would someone explain me what we mean by materialising inferrences in a triple store?

Regards!

asked 25 Jan '11, 14:17

Hzjit's gravatar image

Hzjit
18916
accept rate: 0%


Erwachen,

In order to not use an external reasoner each time, I got to ask how can we implement our own reasoning capabilities in a triple store as to do deductions on the triple store?

There are a few different ways:

  • Tableaux based implementation
  • Rule based implementation

Tableaux approaches are good at getting a subset of inferences which (succinct) rule based approaches can't (mainly involving disjunctive knowledge, something is of type A or B; negation which deals with falsity; existential quantification, which deals with anonymous individuals; or universal quantification, which deals with all individuals matching certain criteria; or combinations of these). Anyways... unless you have specific needs for very expressive reasoning, or have expertise in logics, I would advise against this method.

Next you have rule-based approaches, which are much more intuitive to get your head around. (Inference-)Rules are just:

IF condition THEN consequent

If the condition is met by your data, then the consequent holds in your data. An example is for subclass:

?c rdfs:subClassOf ?d . ?x rdf:type ?c .?x rdf:type ?d .

If you have two triples matching the first two patterns in your data (on the left side of →), then your data entails the third pattern (on the right side of →).

Rules are more than sufficient for many use-cases (see here for nice discussion). For implementing rule-based approaches, you then have two major options.

  • Rule based implementation
    • Forward chaining (e.g., full materialisation)
    • Backward chaining (e.g., query rewriting)

Forward chaining means that you take the data you know, and recursively add new data based on the rules. Materialisation means that you store the data the rules give you as if it were input data... you materialise (create/make concrete) the entailments. This is typically done as you load data into your index/application. For example... we know that all foaf:Persons are foaf:Agents, so for all foaf:Person members in the data, we'll add a triple stating that they're of type foaf:Agent as well.

Backward chaining means that you (typically) leave the data as is, but when you get a query, you expand that query (according to the rules) so that if will get more answers. For example... someone is asking for foaf:Agent... we know that all foaf:Persons are foaf:Agents, so we'll return all foaf:Person members as well.

If you want to implement rules, there are four main rulesets which are common amongst implementers:

Systems also commonly mix and match rules from the various profiles depending on their requirements.

There are also hybrid approaches... but that's further down the road.

doable?

Yep.

hard to do it? needs lots of time? complicated?

It depends. I don't know what your use-case is, but my advice would be to start by implementing a simpler rule-based profile of reasoning, like RDFS (you can even leave our the more esoteric stuff and just do the four rules rdfs2, rdfs3, rdfs7, and rdfs9 for supporting the main entailments of rdfs:domain, rdfs:range, rdfs:subClassOf, rdfs:subPropertyOf). You can then look to extend your ruleset once you get a feel for how its done.

If you stick to rules, it shouldn't take too much time, and it shouldn't be so complicated... but that depends on how dynamic your data is, what scale you require, what rules you want to apply, etc.

And plz, would someone explain me what we mean by materialising inferrences in a triple store?

Hopefully the above covers it... it just means creating new triples which are inferred by your rules/data.

permanent link
This answer is marked "community wiki".

answered 25 Jan '11, 15:48

Signified's gravatar image

Signified ♦
24.0k1623
accept rate: 37%

edited 26 Jan '11, 19:21

Just wanted to note that, apart from "disjunctive knowledge", tableaux methods (and other first-order logic'ish deduction methods) also provide for "negated knowledge", "existential knowledge" and "universal knowledge"; and all of this in pretty arbitrary combination. ;-)

(25 Jan '11, 21:20) Michael Schn... ♦ Michael%20Schneider's gravatar image

Not sure I get you... you can model a lot of these in rule based approaches, no? For example, you have (restricted) negation in Datalog, existential support in simple entailment and pD*sv... okay I have no idea what universal knowledge is :) (axiomatic triples maybe?).

(26 Jan '11, 00:03) Signified ♦ Signified's gravatar image

@Signified: is backward chaining always a query rewriting process ? or is it sometimes running the reasoner at query time ? thanks

(26 Jan '11, 07:44) Fabian Cretton Fabian%20Cretton's gravatar image
1

I was about how far you can get with tableaux aproaches: there are some for full first-order logic proving! By "existential" and "universal" knowledge I meant that existential and universal quantification can be freely intermixed in logic formulas. And negation-as-failure (NAF), as often found in datalog systems, is not a replacement for "true" negation and can lead to surprising results, when used to implement traditional logic-style semantics, as of OWL. Just play with the OWL 2 DL semantics of =2 cardinality restrictions and negative property assertions to see some of the issues.

(26 Jan '11, 08:00) Michael Schn... ♦ Michael%20Schneider's gravatar image

@Fabian... backward chaining is typically, but not always necessarily a query rewriting process... strictly speaking it refers to the idea of working backwards from a goal (a query) to find the knowledge you need. @Michael... okay, I'm a little out of my depth now :), but I'll edit the answer a bit... I'll also wiki it if you'd like to revise it.

(26 Jan '11, 19:14) Signified ♦ Signified's gravatar image

@Signified, thanks for the information. But thinking about it, how can query rewriting fulfill reasoning ? I can see in simple example as the one you gave here above, but when more complex DL rules are involved, how is that possible ? I ask you all those question cause it never occurs to me so far that backward chaining could be query rewriting ;-)

(27 Jan '11, 06:54) Fabian Cretton Fabian%20Cretton's gravatar image

Hey Fabian. Little tricky to answer here. I believe you're correct in that I don't think that (assertional) query-answering wrt. (e.g.) OWL 2 DL could be fully supported by query-rewriting, but certain profiles are... check out OWL 2 QL which is designed for query-rewriting: http://www.w3.org/TR/owl2-profiles/#OWL_2_QL . If you need more info, I'd recommend a new question [so other ppl can answer/re-use/critique]. :)

(27 Jan '11, 08:10) Signified ♦ Signified's gravatar image

Thats fine for me, I was just surprised and happy to learn about that idea of query rewriting in backward chaining. Thanks!

(27 Jan '11, 10:10) Fabian Cretton Fabian%20Cretton's gravatar image

Hope it works out for you :)

(27 Jan '11, 19:00) Signified ♦ Signified's gravatar image
showing 5 of 9 show 4 more comments

Reasoners are mostly implemented by using so called tableaux algorithms. In general I would say yes, it is hard to do, it needs lots of time and it is complicated.

Lots of smart people invested quite some time into developing reasoners, so it is nothing you can do just 'en passant', but you need to look deep into description logics and algorithms to do different sort of reasoning on these logics.

There are already related questions here:

A good introduction into description logics is the Enrico Franconis course on the topic. If you're a Java developer, you might want to take a look at the source code of Pellet, a Java based reasoner which implements OWL DL reasoning.

And finally:

what we mean by materialising inferrences in a triple store?

That simply means, that all the triples which are inferred by the reasoner are written back to the dataset, e.g. if you have a triple

 ex:Kitkat rdf:type ex:Cat.

and your ontology says

 ex:Cat rdfs:subClassOf ex:Animal

that the the reasoner will infer the triple

 ex:Kitkat rdf:type ex:Animal

and will write this triple back to your data. Depending on your scenario that can be troublesome, as you also need to take care that when entities are deleted from your dataset, all triples that were inferred from them have to be removed, too, or at least be checked.

permanent link

answered 25 Jan '11, 15:47

Bastian%20Spanneberg's gravatar image

Bastian Span...
2.0k1613
accept rate: 21%

2

Re: "Reasoners are mostly implemented by using so called tableaux algorithms." Come on! There are, of course, a couple of Semantic Web reasoners around that are implemented in this way, but most Semantic Web reasoners I know are implemented in a rule-based way, as Signified describes it. Just think of all the triple stores that come with some form of "light-weight" built-in reasoning. Or think of RDF frameworks such as Jena and Sesame, which also provide rule-based reasoning. Even some OWL DL reasoners are rule-based, such as KAON2 (http://kaon2.semanticweb.org/).

(25 Jan '11, 21:27) Michael Schn... ♦ Michael%20Schneider's gravatar image

@Michael: OK, ok, I was more thinking of "full-blown" OWL DL reasoners like Racer.

(26 Jan '11, 08:10) Bastian Span... Bastian%20Spanneberg's gravatar image

Ok, so I was more thinking of "reasoning capabilities in triple stores" ;-)

(26 Jan '11, 14:19) Michael Schn... ♦ Michael%20Schneider's gravatar image
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×206
×162
×112

question asked: 25 Jan '11, 14:17

question was seen: 2,465 times

last updated: 26 Jan '11, 19:21