On 21 Oct 2011, at 02:57, Ali SH wrote:
On Thu, Oct 20, 2011 at 4:08 PM, Bijan Parsia
<bparsia@xxxxxxxxxxxx> wrote:
[BP] If so, then it probably doesn't need the extra expressivity. In expressive logics, size is less important than complexity. Euclid's Theorems don't make for a *large* KB, but good luck writing a reasoner that can return the rest of the Elements :)
[AH] Ummmm, not quite.
[BP] Actually quite.
Hmmmm, sorry, not so quite. ;)
Dude, if you look at what you are actually commenting on, you know the *very words* you say "not quite" too, you'll see that you are being silly.
I think though that we're talking at cross purposes.
As I've been using plain words (size and subset) with their plain meaning, it seems a bit surprising that this is in fact the case.
You'll forgive me for not having interpreted your use of the term "fragment" to mean something defined in a paper which doesn't actually use the term "fragment". Since I gave concrete examples of what I meant, then I'm afraid I'm going to lay this at your feet.
Namely (though see the paper for proper formatting and symbols):
A class of structures M is reducible to the classes of structures N1, ..., Nn
iff there is a set of surjections Pi : M \rightarrow Ni such that if M \in M and M = M1 U ... U Mn
then Mi is weakly definable in Pi(Mi) and Pi(Mi) is weakly definable in Mi
which leads to the theorem:
Let T be a theory and let T1, ... , Tn be a set of modules in the repository.
Mod(T ) is reducible to Mod(T1),..., Mod(Tn) iff
- T faithfully interprets each theory Ti , and
- T1 U ... U Tn is definably equivalent to a subtheory T* \subset T such that
... Basically, see section 3.4 in that paper for a proper treatment of what I meant by fragment. It is in this sense that T* is a fragment of T.
Yeah, that's all interesting. I've no problem with that. I'm pretty skeptical that this would enable people writing large, highly expressive ontologies in FOL, making free use of the language to decompose their ontologies into "tractable" subsets. There is, at the very least, a large engineering gap.
N.B., this statement is wrong: "The major limitation of using E-connections is that the use of such modules as a means
of refining an ontology (non-conservative extensions of a theory) becomes impossible."
Nothing prevents you from non-conservatively extending within a e-connection based module, or from altering the module structure. A decomposition based approach does exactly that. A syntactic enforcement approach would be otherwise, but even there, within module is fine and all breaking modular structure means is that you go through some extra syntactic hoops.
[AH] There are many applications where you might have captured the domain in an expressive ontology, and have ensured consistency (perhaps off-line)
[BP] I would like to know how they've done that, if the ontology is truly using a high level of expressivity and is reasonably large. "Off line" doesn't work if the reasoning problem takes a billion years.
If it can then be factored (without approximation) into tractable fragments, I'll be pretty surprised or bet that the modelling doesn't really exploit the expressivity.
Sure, imagine an ontology that is a union of modules for a subclass taxonomy, time and geo-spatial components. The theory that combined all these modules requires at least first order expressivity to capture intuitions about the domain.
The phrase "at least first order expressivity" needs clarification. My usually understanding is something like, "Does not fall into any known decidable fragment of FOL."
By "tractable" you mean that...all FOL entailments over the theory can be determined in 3-20 minutes? How do you know, if you allow arbitrary FOL queries?
but answers take on the order 3-20 minutes to return based on a kb and a general purpose FOL reasoner. However, properties of each of the modules are also known, and they each have a dedicated reasoners just in case the system receives a query involving vocabulary singularly to do with one of the sub-modules.
This is exactly the case I presented and presented as an example of *not* essentially requiring FOL per se.
For example, if a query involves language only drawn from the taxonomic sub-module, then the FOL reasoner need not be called, and instead something optimized for traversing trees might be invoked. Alternatively, if a query involved solely geospatial terms, then perhaps no reasoner would actually be called, but the query would be computed algebraically.
It is my (perhaps faulty) understanding that the Cyc system does something broadly similar to this.
For another example, consider the PSL-core ontology which is reducible to simpler theories, and these more simple models can be used to construct models of the PSL-core ontology (section 3.5 of the paper referenced above).
[AH] So for example, for real-time interactions of a subset of that ontology, you deploy fragments of it.
[BP As I said, size doesn't necessarily determine difficulty of reasoning in expressive logics. This is just a brute mathematical fact (EXPTIME logics have relatively small theories that take, well, an infeasibly long time to reason with).
Thanks, I know this, and I haven't been talking about size...
Since I have, and have been doing so *explicitly*, it would have been nice for you to have made this clear, oh, some 700 words and three emails earlier!
[BP]Indeed, I've encountered OWL ontologies which have fragments which are *harder* to reasoner over than the whole ontology! (Typically because the reasoner can exploit information in the whole which prunes the search space).
...
Right, so the problem of tractability is part of the domain moreso than an inherent part of a representation language.
Well, this calls into doubt your earlier claim to knowledge. This does not REMOTELY follow, at least on any reasonable interpretation I can find.
EL entailment is decidable in polynomial time. The tractability of EL theories are a consequence of the representation langauge. FOL entailment is not. Thus a random FOL theory is unlikely to be tractable. If you have a domain that's completely representable in EL then reasoning over (a good representation of) that domain will be tractable.
But that's another way of saying that you didn't need very much expressivity to represent the domain.
Which is another way of saying that when people claim they need "full FOL expressivity" it's wise to check what they mean by that.
FOL for all its semi-decidability might still be quite tractable and fast, and OWL for all its decidability might take a super long time...
This is very silly, yes? FOL includes Datalog, but OWL does not. Datalog is more tractable than OWL, so yes, if your FOL theory is entirely in Datalog, and your queries are all ground, and you use a datalog reasoner, ka-ching! your "fol" theory will be very fast indeed.
But you aren't using "FOL", you're using Datalog. At least, that's the most useful analysis.
It's more to do with what you're modelling than your language.B ut this is beside the point here. The rest of your response continues to assume that I'm simply talking about "size" which is certainly not the case.
I'll work on my mind reading.
[BP] Ok. I don't care at all about OOR.
Funny that you're on the OOR mailing list then :P.
Easily solved.
Ah sure, you mean standard notions such as conservative extension. Well, CE for sure will be nasty (undecidable) for OWL alone, so detecting such relations is probably unlikely in the near future. If you have an approximation algorithm, however, you might be able to put some guarantees on the output. And in the OWL world we've worked on various approximations of CE related notions (cf locality based modules).
Though in contrast with most DL research, we've focused more on flavours of non-conservative extensions.
I don't think the problem of deciding whether a theory is not a conservative extension of another is any easier than one that is.
Cheers,
Bijan.