Re: comment on the fragment document: (inverse) functional and DL-Lite

Carsten or Ian -
  Forgive me for being dense, but I went back to my complexity books  
and I cannot find a very good definition of "conjunctive query"  
especially in the presence of an ontology.  A use case would be great  
(i.e. what is it about the Abox done this way that let's it be stored  
in a DB and accessed by SQL - can't I do that for any Abox?) - Also  
what is the difference between query complexity and combined  
complexity?  What are we logspace in?
  One of my students is working on some complexity proofs in the OWL-R  
space and our results are quite different than yours. My assumption is  
we're using different definitions -  I went back to some of the  
papers, but couldn't find a clear definition, and in fact find several  
different definitions of "query complexity" in the DB literature, we  
have looked at the IJCAI paper by you, Ian and Uli  [1] , of course,  
but we're having trouble figuring out how to map those to some of the  
stuff we understand better (like Kolaitis and Varde, [2]) which use  
the data calculus as their base.
  I'm not asking for a formal definition -- in fact, I'm asking for an  
informal one, can you capture the intuition as to the difference  
between conjunctive query in DL-Lite vs. datalog, and also help me  
understand the combined complexity as defined in these things -- the  
definitions in the fragments documents are quite brief, for example:
> The Combined Complexity: the complexity measured with respect to  
> both the size of the axioms and the number of facts. In the case of  
> conjunctive query answering, the combined complexity also includes  
> the query complexity.

and we want to make sure we're not missing anything.
   Please also note that I am very much NOT trying to be snide or  
critical - I believe your proofs, I'm just trying to understand better  
so I can align our work correctly.  Also,  we will have to explain  
this to people who have even less knowledge of DB than I do, so  
finding ways to capture these intuitions is very important.
   thanks
  Jim H.
p.s. If people would prefer we take this off line, let me know - I  
suspect it has something to do with the breaking down of complexity  
into two parts in this literature, but not in the other - and suspect  
if we get into that level of detail it will get pretty geeky...




[1] www.ijcai.org/papers07/Papers/IJCAI07-062.pdf
[2] http://portal.acm.org/ft_gateway.cfm?id=275511&type=pdf&coll=portal&dl=ACM&CFID=19216331&CFTOKEN=99435863

On Mar 7, 2008, at 3:45 AM, Carsten Lutz wrote:

> On Thu, 6 Mar 2008, Ian Horrocks wrote:
>>
>> Actually, the primary idea of DL-Lite is that it has logspace data  
>> complexity, which means that query answering can be implemented  
>> using standard (relational) DB technology. In particular, a  
>> conjunctive query against a DL-Lite ontology can be re-written as  
>> an SQL query against a relational DB containing instance data.
>
> I agree, the goal of DL-Lite is: being able to answer conjunctive
> queries under a OWL-DL style open world semantics by storing the ABox
> in a relational DB, rewriting the query, and then using standard RDB
> query answering. This can be viewed as backward chaining and has the
> advantage that off-the-shelf (completely unmodified) DB technology
> can be used to answer conjunctive queries under an OWL-DL semantics.
>
> A slight correction though: logspace data complexity does not
> necessarily mean that this can be done (at least such a general result
> is unknown). However, the following is true: non-logspace data
> complexity means that this can *not* be done.
>
> greetings,
> 		Carsten
>
>> Ian
>>
>>
>> On 6 Mar 2008, at 19:23, Jim Hendler wrote:
>>
>>> I thought the primary idea of DL-Lite was that it would provide  
>>> primary database functionality -- how can it do that without keys?
>>> On Mar 6, 2008, at 6:18 AM, Bijan Parsia wrote:
>>>> On 6 Mar 2008, at 11:04, Ivan Herman wrote:
>>>>> Boris, Bernardo,
>>>>> I went through
>>>>> http://www.w3.org/2007/OWL/wiki/Fragments_Proposal
>>>>> again today. One thing that I may have missed: I tried to see if  
>>>>> I can use (inverse)functional properties for DL-Lite or not. I  
>>>>> did not find any reference to those neither in 3.1 nor in 3.2.  
>>>>> Again, I may have missed something...
>>>> Let's see if I can discern from the text the situation. (As a  
>>>> test of the spec.)
>>>> In section 3:
>>>> 	http://www.w3.org/2007/OWL/wiki/Fragments_Proposal#DL-Lite
>>>>
>>>> 	"""Several variants of DL-Lite have been described in the  
>>>> literature. The variant presented here is called DL-LiteR since  
>>>> it allows for property inclusion axioms; it therefore contains  
>>>> the intersection between RDFS and OWL 1.1 DL. Other variants  
>>>> trade property inclusion axioms for functionality and inverse- 
>>>> functionality of object properties."""
>>>> I think this is clear that functionality and inverse  
>>>> functionality of *object* properties are forbidden.
>>>> Actually ,the rest of the sections are quiet about data  
>>>> properties altogether. Which would mean that data properties are  
>>>> forbidden in this variant. Which means that it's not really the  
>>>> intersection of RDFS and OWL 1.1 DL?
>>>> I do think that if we make this DL Lite not have data properties,  
>>>> the text should call that out (e.g., in the list of missing  
>>>> features). OTOH, I think we should allow data properties ;) I  
>>>> would think it would be ok to trade datasubproperties for keys  
>>>> (from a user pov)...I don't know if that would be ok from the  
>>>> logic/impelmentation pov off the top of my had (while retaining  
>>>> object subproperties).
>>>> Cheers,
>>>> Bijan.
>>> "If we knew what we were doing, it wouldn't be called research,  
>>> would it?." - Albert Einstein
>>> Prof James Hendler http://www.cs.rpi.edu/~hendler
>>> Tetherless World Constellation Chair
>>> Computer Science Dept
>>> Rensselaer Polytechnic Institute, Troy NY 12180
>>
>>
>
> --
> *      Carsten Lutz, Institut f"ur Theoretische Informatik, TU  
> Dresden       *
> *     Office phone:++49 351 46339171   mailto:lutz@tcs.inf.tu-dresden.de 
>      *

"If we knew what we were doing, it wouldn't be called research, would  
it?." - Albert Einstein

Prof James Hendler				http://www.cs.rpi.edu/~hendler
Tetherless World Constellation Chair
Computer Science Dept
Rensselaer Polytechnic Institute, Troy NY 12180

Received on Friday, 7 March 2008 15:38:23 UTC