Re: Final text for Basic Graph Patterns

On Jan 18, 2006, at 7:33 PM, Enrico Franconi wrote:

> On 18 Jan 2006, at 23:12, Pat Hayes wrote:
>>>> SELECT ?x WHERE {:a rdf:type ?x .}
>>>
>>> Look, this is not a legal OWL-DL query.
>>
>> This query pattern has legal OWL-DL instances, so why is it not a 
>> legal OWL-DL query?
>
> Look, we already agreed that we are not here to do research.
> First of all, I have been sloppy in my statement, since OWL-DL queries 
> do not exist - we are defining them now here.
> Now, there is *no* theoretical nor practical result that even 
> considers queries of that kind in the DL literature.

Let me preface my very slight dissent with the fact that the qualifer 
"in the DL literature" makes this *almost* completely true and if you 
added "fully worked out" there's no question :)

However there are some hints from implementations and in the 
literature. E.g., the OWL QL
	ftp://ftp.ksl.stanford.edu/pub/KSL_Reports/KSL-03-14.pdf.gz
has a discussion (though much of it presumes a HiLog like encoding, I 
think, which isn't really satisfactory; rather it prsumes OWL Full I 
think, which makes it rather awkward for OWL DL). Consider:

"""Query languages for description logics and other logic-based 
knowledge representation formalisms often includeexplicit “structural 
queries”, such as queries asking about the subsumers, subclasses, and 
instances of classes [BM96] [BBH91] [BHP99]....For example, answers to 
the query using the query pattern {(subclassOf ?x Person)}, where ?x is 
a must-bind variable, will be the derivablesubclasses of class Person.  
Similarly, answers to the query using the query pattern {(type ?x 
Person)}, where ?x is again a must-bind variable, will be the derivable 
instances of class Person.  This ability is limited toconcepts which 
can be expressed using OWL: for example, there is no way in OWL to 
express the concept of a most general subclass or a most specific type. 
"""

In the next section (V.B) there is a discussion of how to essentially 
implement these other sorts of query with multiple queries (not a 
simple expansion...you have to iteratively incorporate answers from 
prior queries).

So, it's try that, e.g., the DIG interface has a standard set of "query 
functions", i.e., parentsOf, childrenOf, decendents, etc. as does most 
reasoner's apis (see the racer manual). Note that these functions are 
typically rather restricted (e.g., to known terms in the kb).

Now, in two systems, to my knowledge (Pellet and Cerebra) these TBox 
query functions have been incorporated in the implementation. In 
Cerebra, IIRC, they provide functions in their pseudo-XQuery thing that 
parallel the DIG functions (e.g., Individuals() (in a kb). The 
functions return a set of bindings that then get massaged by the XQuery 
algebra (and given the language, could be use to construct families of 
queries I think). Pellet has an experimental (buggy, unsound) engine 
that takes a mixed set of conjuncts and evaluated each conjunct 
separately, abox queries normally, tbox queries by mapping to the 
appropriate function, then algebraically combines the results. (It 
doesn't really work since you have to be a bit more careful about how 
conjuncts can affect each other, but anyway.)

Our experimentation was driven by FLA-CP's interest in a unified 
interface in the form of a query language. I've recently had some other 
users request such features. I'm more inclined to go an RQL sort of 
route in this (and have the query forms more explicitly distinct), but 
I think you could analyze the tbox parts out of a query and map them to 
the standard functions. If you were ok with limiting yourself to those 
semantics (essentially, no bnodes in answers for the tbox query 
functions) then, pace any unforseen problems ;), it should be fine.

So,
	SELECT ?x WHERE {:a rdf:type ?x .}

could be understood as exactly the dig query:
	<types>:a</types>

(<http://dl-web.man.ac.uk/dig/2003/02/interface.pdf>, page 9)

Something like
	SELECT ?x WHERE {:a rdf:type ?x. ?x subClassOf :Person}

Would be the intersection of
	<types>:a</types>
and
	<descendants>:Person<descendants/>

(I don't know if descendants include equivalents, or we shouild mean 
them to here.)

Considering
		SELECT ?x, ?y, ?z WHERE {?x loves ?y.  ?y rdf:type ?z.}

We might separate the query, evaluate the abox query "?x loves ?y", 
take the bindings of ?y (say, :a, :b, :c) and use the second conjunct 
as a template, expanding it to
		<types>:a</types>
		<types>:b</types>	
		<types>:c</types>

In a sense, this isn't *too* far in spirit from some of the FUB 
definitions ways of dealing with property variables In fact, you might 
see
	SELECT ?s, ?p ?o {?s foaf:nick "Bijan". ?s ?p ?o}

as really involving an implicit <allRoleNames/>

Notice the enormous simplification (only terms, not expressions, hence 
no bnodes in the bindings of the higher order looking variables) and 
the lots of work that would need to be done (tons of choices).

However, I don't think it's quite as dire as:

> Queries that have been studied in the world of DL are only first 
> order. Full stop.
[snip]

or

> Yes, but in no DL statements with existential variables in place of 
> classes have ever been considered.
[snip]

However...

>>> Even if we allow high-order queries like the above in OWL-DL, the 
>>> scoping set B would be restricted to be URIs in OWL-DL, so the 
>>> problem doesn't show up in OWL-DL anyway!
>>
>> We could so restrict things, of course: but my point was that such a 
>> restriction might not be semantically/pragmatically correct in the 
>> OWL case.
>
> In the OWL-DL case it is the only one that makes sense given the 
> current state of the research and practice.
[snip]

If all that meant what I think it meant, then indeed. The most I think 
we could feasibly hit is told expressions and there things would end up 
being very confusing for the user (IMHO).

It is also true that the current state of the deployed art, suitable 
for standardization, is conjunctive abox query alone. There there is a 
wealth of theory (see ian's and sergio's and enrico's (and others') 
papers), several reasonably optimized implementations (Racer, Pellet, 
KAON2, with Racer and KAON2 being commercial...I guess Cerebra also 
does conjunctive abox query, and it is, of course, commercial, but I'm 
not very familiar for it).  Oh, various subsets of OWL DL (e.g., DL 
Lite) also fit this model. It would be nice to standards this level so 
that we can get interoperability between the 4 query implementation. (I 
imagine FaCT++ will have something soon).

Cheers,
Bijan.

Received on Thursday, 19 January 2006 05:50:14 UTC