forward vs backward chaining

As someone trying to grok reasoners, I'm trying to figure out when would you use a forward chaining reasoner vs a backward chaining one? Is it to be decided by space/time tradeoffs only, or are there other considerations? And, why would you use a hybrid?

asked 22 Feb '11, 18:32

harschware ♦
7.4k●5●15
accept rate: 19%

3 Answers:

oldest newest most voted

In engineering terms, for query-answering, the benefits between forward-chaining and backward-chaining can be reduced to a simple trade-off:

forward-chaining (~materialisation): precomputing and storing answers is suitable for:
- frequently accessed data,
- which are relatively static,
- which are expensive to compute, and/or
- which are small enough to efficiently store
- (a la Lesson 6)
backward-chaining (~query-rewriting): storing a minimal index from which answers can be computed on demand is more suitable where:
- there is little scope for reuse of computed answers,
- the answers are dynamic,
- answers can be efficiently computed at runtime, and/or
- the "answer space" is too large to materialise and store

A hybrid approach should then give the best of both worlds, materialising the inferences that are frequently accessed, static, and/or small, and supporting query-rewriting for inferences that are large, cheap to do at runtime, dynamic and/or infrequently accessed.

For example, many large-scale reasoners:

typically rely on materialisation to do the bulk of reasoning.
use backward-chaining to support stuff like reflexive owl:sameAs statements, or rdf:type rdfs:Resource/owl:Thing
use a hybrid approach for equality (to avoid ~quadratic materialisation: a maximum of n² inferences where n is the no. of input triples), where
- each set of "URI aliases" (identifiers related by owl:sameAs) is stored in a special index
- one URI is chosen as a canonical identifier to represent all such aliases in the indexed data
- queries are rewritten to use the chosen canonical identifer
- results data can be (optionally as needed) expanded to use all combinations of identifiers.

Just a quick addendum on the phrases (...'cause this used to confused me):

Given a set of inference rules:

Forward chaining means applying rules in a forward direction: recursively applying the rules over data to generate more data (and applying the rules over that data... I have a member of po:Person... it must also be a member of foaf:Person... and so it must be a foaf:Agent and dc:Agent... and so...)
Backward chaining means applying rules in a backwards manner: taking a goal (e.g., a query) and recursively working backwards to find more data that can satisfy the goal (I'm looking for foaf:Agents... I should also look for dc:Agents and foaf:Persons and po:Persons...)
Materialisation means writing the results of forward-chaining down
Query-rewriting means directly rewriting/expanding queries (e.g., adding UNIONs to also look for dc:Agents and foaf:Persons and po:Persons...) using backward-chaining techniques
Materialisation ≠ Forward chaining
Query-rewriting ≠ Backward chaining

link

answered 22 Feb '11, 18:42

Signified ♦
20.9k●6●22
accept rate: 39%

edited 23 Feb '11, 01:22

From a practical point of view, frequency of change is probably not a major issue: under reasonable assumptions (usually a monotonic logic), advanced engines should be able to incrementally maintain the inferred closure, with comparable efficiency for assertions and retractions.

(22 Feb '11, 20:40) AB

To a certain extent true, but (in particular) high rates of deletion can become a notable factor when combined with the other consideration, esp. if data-sizes/materialisations are large. Plus, it can make your on-disk indexes more "fragmented" by increasing the amount you store and subsequently delete (how much of a factor this is depends on your particular low-level indexing).

(22 Feb '11, 21:44) Signified ♦

For reference of others: when materialising, and assuming inferencing is monotonic (~incremental: adding new data cannot "invalidate" previous data or inferences) for insertions you need only figure out inferences involving the delta, and materialise/store them. However, for deletions, you also need to delete those inferences which depend on the deletions, usually done by (i) using the same forward-chaining procedure you would use for an insertion to find all inferences which involve statement(s) to delete; (ii) finding alternate derivations for these inferences not involving deletions.

(22 Feb '11, 21:50) Signified ♦

You mention "quadratic materialisation", which I see has been mentioned here once before. Should I know what that is?

(23 Feb '11, 01:11) Jodi Schneider

Small typo: Materialistaion is here once.

(23 Feb '11, 01:12) Jodi Schneider

Got it, cheers.

(23 Feb '11, 01:16) Signified ♦

showing 5 of 6 show 1 more comments

Referring to Signified's answer, a full form of materialization (by whatever technique it is actually being performed) is, of course, possible only for entailment regimes for which the entailment closure is always finite. So, for more complex languages, the tradeoff between materialization and whatever technique then replaces "backward chaining" is also about the degree of completeness of reasoning.

For example, in OWL DL the set of entailments is /not/ finite. For instance, for a given class C all the statements of the form "C owl:unionOf (C ... C)" are entailments. That's not particularly interesting information, of course, and one would not really like to have this in the result of a materialization task. There may also be more interesting entailments, for instance when two very complex class expressions happen to be equivalent. One may like to ask for this very specific reasoning result in a given situation, and one would then use a form of query answering for doing this (an entailment check in the easiest case), but one would not seriously expect to have such specific stuff materialized out by default.

So, materialization in more complex languages will always need to be restricted to a certain well-defined finite subset of entailments. For example, OWL DL reasoners typically allow for /classification/, that is, all implicit subsumption relationships between named classes are computed. That's obviously always a finite result set for a given ontology. Classification does, however, typically /not/ give subsumption relationships between arbitrary class expressions, even if they hold semantically. This would, in general, lead to an infinite result set with a lot of redundant or uninteresting information. So if one want's to know about a specific subsumption relationship between class expressions, one needs to query for it specifically, and will, in OWL DL at least, be guaranteed to receive a correct answer in every case (provided enough resources and time given).

link

answered 22 Feb '11, 23:23

Michael Schn... ♦
5.6k●1●6●11
accept rate: 31%

Good point... similar case for datatypes in OWL 2 RL/RDF (although entailments can be finitely "constrained" to the set of datatype literals appearing in the data, you can't anticipate user-specified literals).

(23 Feb '11, 01:05) Signified ♦

to take this simple, forward chaining is data driven and backward chaining is goal driven. Probably is obvious that solving a real problem will start with a goal and usualy implies inference over a data set, therefor the need for mixing both.

link

answered 14 Feb '12, 22:22

oesxyl
324●1●4
accept rate: 3%

edited 14 Feb '12, 22:23

Your answer

toggle preview

community wiki

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

learn more about Markdown

Tags:

reasoning ×119
inference ×81
reasoner ×44
entailment ×5
chaining ×1

Asked: 22 Feb '11, 18:32

Seen: 8,958 times

Last updated: 14 Feb '12, 22:23

forward vs backward chaining

Follow this question

Upcoming Events

Related questions