[seek-kr-sms] OBOE clarifications and questions

Fri Jun 16 09:01:48 PDT 2006

Kai:

Great to hear from you! I need to check out that reference more
carefully...  But I can already say that no matter what the W3C says,
there are mathematical truths that are above the W3C standardization
processes and that by their very nature will outlast W3C, the Web, the
life span of mankind, the biosphere (life on planet Earth), and maybe
the universe/multiverse itself (ok, I'm getting a bit more speculative
towards the end ;-)

If I want to relate n objects simultaneously, I can use, e.g., an
n-ary relation symbol R(A1,..., An), or I can use a first-order
formula with n free variables. 

However, in general I can no longer decide satisfiability (and related
notions) in such first-order fragments.

I just came across the following very nice material that might shed
some light on this -- here are the slides: 
    http://www-mgi.informatik.rwth-aachen.de/~graedel/kalmar.pdf
(e.g. slide #53 shows how one can express the existence of a path of
length 17 in FO2, i.e., in FO w/ only two variables.

And here is the paper that apparently goes with the slides:
    http://citeseer.ist.psu.edu/631148.html

enjoy!

Bertram

>>> On Thu, 15 Jun 2006 12:37:57 -0700
>>> "Kai Lin" <klin at sdsc.edu> wrote: 
KL> 
KL> Bertram,
KL> 
KL> I am not sure that I understand the context of the discussion. Actually
KL> it is possible to specify N-ary relations in OWL or RDF. The OWL working
KL> group in W3C has a formal document on this issue. You can find it at the
KL> following URL:
KL> 
KL>     http://www.w3.org/TR/swbp-n-aryRelations/#vocabulary  
KL> 
KL> Best,
KL> 
KL> -- Kai
KL> 
KL> 
KL> -----Original Message-----
KL> From: seek-kr-sms-bounces at ecoinformatics.org
KL> [mailto:seek-kr-sms-bounces at ecoinformatics.org] On Behalf Of Bertram
KL> Ludaescher
KL> Sent: Thursday, June 15, 2006 11:41 AM
KL> To: Shawn Bowers
KL> Cc: seek-kr-sms at ecoinformatics.org
KL> Subject: Re: [seek-kr-sms] OBOE clarifications and questions
KL> 
KL> 
KL> An addition to Shawn's answer to Matt's question for Josh, which Josh
KL> had passed on to Shawn (now let's do an annotation/data lineage graph
KL> for THAT! ;-)
KL> 
KL> Ontologies expressed in description logic have certain limitations in
KL> expressiveness. This has to do w/ the fact that DLs are (almost
KL> always) decidable first-order fragments of a special kind, i.e.,
KL> "2-variable first-order logic". In particular, this means that any
KL> individual statement (axiom) cannot--in general--refer to more than
KL> two things at one time. Think of the two variables as pointers
KL> (pebbles for logic game-theorists). You then make statements about two
KL> domain elements. So in general you cannot make statements that require
KL> inter-relating 3 or more individuals at the same time (or else you
KL> might risk getting into undecidability land..)
KL> 
KL> On the other hand, there are other logic fragments, most notably
KL> conjunctive queries CQ (aka Select-Project-Join queries) which are
KL> able to refer to many individuals at the same time. But there you have
KL> only existential quantification and no negation.
KL> 
KL> Mixing CQ and DL in general leads to undecidability. 
KL> 
KL> Shawn: we might want to look up the decision procedure for 2-FO (and
KL> DLs in particular). 
KL> 
KL> Maybe there is some interesting research to be done in combining
KL> CQ-like fragements with DL for specialized "alpha languages" that are
KL> still decidable.
KL> 
KL> For now, my lips are sealed on any further comments, since this list
KL> is googleable ;-)
KL> 
KL> Bertram
KL> 
KL> 
KL> 
>>> 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?
KL> For
>>> example, a 'site' table, and a 'tree measurement' table that has a
>>> foreign key into the site table.  Can we create annotations that
KL> refer
>>> to attributes in both tables?
>>> 
>>> 
>>> I'm not 100% sure what you mean here.  I hope that we can do this.
KL> Shawn 
>>> might have a better sense for this question.
SB> 
SB> Matt, we have typically been defining a semantic annotation as a
KL> mapping 
SB> from relation (database) instances to ontology instances. These
KL> 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) &
KL> measuredIn(y,x)
SB> 
SB> asserts that if x is a value in the Site table, and x,y are values
KL> 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
KL> '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
KL> side, and 
SB> not for specifying the annotation logic itself.
KL> 
KL> _______________________________________________
KL> Seek-kr-sms mailing list
KL> Seek-kr-sms at ecoinformatics.org
KL> http://mercury.nceas.ucsb.edu/ecoinformatics/mailman/listinfo/seek-kr-sm
KL> s