[seek-kr-sms] OBOE clarifications and questions

[Kai Lin]

Bertram,

I think the actual question is not about the mathematical truths. The
actual question is how to use DL (or OWL DL) to present N-ary relations
and solve our application problems. People usually think that DL only
allows binary relations, but there is a nice way to present SOME N-ary
relations in DL with binary relations. Note that I use the term
"present" instead of "define"; also not all the N-ary relations can be
presented in DL, but some of them can be presented in DL depending on
the problems. Once a N-ary relation is presented in DL, you get the
ability of DL for free.  

Here is an example which may be helpful for understanding:

We measure chemical element A on material B and get a value V with a
unit U. To specify it in FOL, we may use a relation Measure(A, B, V, U).
To present this 4-ary relation in DL, we define a new class Measurement
and 4 properties:

     subject : Measurement -> Material
     object  : Measurement -> Element
     value   : Measurement -> int
     unit    : Measurement -> Unit

In other words, a measurement is a composition of a element, a material,
a value and a unit. You can add DL constraints on these properties.
Obviously not all the FOL constraints can be translated into DL
constraints. For real applications, DL may be enough, may be not.      

That W3C document tells us some other patterns we can used to PRESENT
n-ary relations in DL. They are just some useful tricks, not theory at
all.

-- Kai



-----Original Message-----
From: Bertram Ludaescher [mailto:ludaesch at ucdavis.edu] 
Sent: Friday, June 16, 2006 9:02 AM
To: Kai Lin
Cc: Bertram Ludaescher; seek-kr-sms at ecoinformatics.org
Subject: RE: [seek-kr-sms] OBOE clarifications and questions


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