[seek-kr-sms] OBOE clarifications and questions

[Bertram Ludaescher]

An addition to Shawn's answer to Matt's question for Josh, which Josh
had passed on to Shawn (now let's do an annotation/data lineage graph
for THAT! ;-)

Ontologies expressed in description logic have certain limitations in
expressiveness. This has to do w/ the fact that DLs are (almost
always) decidable first-order fragments of a special kind, i.e.,
"2-variable first-order logic". In particular, this means that any
individual statement (axiom) cannot--in general--refer to more than
two things at one time. Think of the two variables as pointers
(pebbles for logic game-theorists). You then make statements about two
domain elements. So in general you cannot make statements that require
inter-relating 3 or more individuals at the same time (or else you
might risk getting into undecidability land..)

On the other hand, there are other logic fragments, most notably
conjunctive queries CQ (aka Select-Project-Join queries) which are
able to refer to many individuals at the same time. But there you have
only existential quantification and no negation.

Mixing CQ and DL in general leads to undecidability. 

Shawn: we might want to look up the decision procedure for 2-FO (and
DLs in particular). 

Maybe there is some interesting research to be done in combining
CQ-like fragements with DL for specialized "alpha languages" that are
still decidable.

For now, my lips are sealed on any further comments, since this list
is googleable ;-)

Bertram



>>> On Wed, 14 Jun 2006 11:14:38 -0700 (PDT)
>>> Shawn Bowers <sbowers at ucdavis.edu> wrote: 
SB> 
>>> 3) How to deal with multiple relations with integrity constraints?  For
>>> example, a 'site' table, and a 'tree measurement' table that has a
>>> foreign key into the site table.  Can we create annotations that refer
>>> to attributes in both tables?
>>> 
>> 
>> I'm not 100% sure what you mean here.  I hope that we can do this.  Shawn 
>> might have a better sense for this question.
SB> 
SB> Matt, we have typically been defining a semantic annotation as a mapping 
SB> from relation (database) instances to ontology instances. These mappings 
SB> have signatures of the form (where a is the annotation)
SB> 
SB>    a: R1 x R2 x ... x Rn -> O1 x O2 x ... x Om
SB> 
SB> such that R1 to Rn are relations (tables) and O1 to Om are ontology 
SB> classes and properties.  For example, the annotation
SB> 
SB>   a: Site(x) & Tree(x, y) -> StudyArea(x) & TreeMeasure(y) & measuredIn(y,x)
SB> 
SB> asserts that if x is a value in the Site table, and x,y are values in the 
SB> Tree table, then x is an instance of a study area concept, y is an 
SB> instance of a tree measure concept, and there is a property 'measuredIn' 
SB> from y to x.
SB> 
SB> OBOE is only concerned with providing a useful vocabulary for the 
SB> right-hand side of these rules. Not for specifying the left-hand side, and 
SB> not for specifying the annotation logic itself.