[seek-kr-sms] OBOE clarifications and questions

Serguei Krivov Serguei.Krivov at uvm.edu
Fri Jun 16 11:57:55 PDT 2006


One essential difference between real FOL n-ry relations (n>2) and
simulations/representation of those relations in OWL-DL is that OWL does not
allow to express simple  queries such as:
 r(X,Y,Z)&q(Z,V,Z).

Or, am I wrong?

There are description logics with role compositions or role value maps that
allow to do it, but they are usually undecidable. So, yes we have tricks to
represent general n-ary relations in OWL, but we could not make expressive
queries based on those representations. May be something like SWRL can come
to the rescue? 

sergey


 
 
> -----Original Message-----
> From: seek-kr-sms-bounces at ecoinformatics.org [mailto:seek-kr-sms-
> bounces at ecoinformatics.org] On Behalf Of Bertram Ludaescher
> Sent: Friday, June 16, 2006 2:19 PM
> To: Kai Lin
> Cc: seek-kr-sms at ecoinformatics.org
> Subject: Re: [seek-kr-sms] OBOE clarifications and questions
> 
> 
> 
> Hi Kai:
> 
> Thanks for the clarification! Comments below
> 
> cheers
> 
> Bertram
> 
> >>> On Fri, 16 Jun 2006 10:55:32 -0700
> >>> "Kai Lin" <klin at sdsc.edu> wrote:
> KL>
> KL> Bertram,
> KL>
> KL> I think the actual question is not about the mathematical truths. The
> KL> actual question is how to use DL (or OWL DL) to present N-ary
> relations
> KL> and solve our application problems.
> 
> Good point. Agreed. It is certainly true for GEON and SEEK!
> (neither is in the business of mathematical foundations)
> 
> What I meant to say is that we cannot--in general--reason with n-ary
> relations (meaning, there is no decision procedure for satisfiability,
> once we go beyond certain language classes). That's  were the
> mathematical truth comes in.
> 
> But you're right: I shouldn't have been ranting ;-)
> 
> KL> People usually think that DL only
> KL> allows binary relations,
> 
> that's the "normal case" indeed
> 
> KL> but there is a nice way to present SOME N-ary
> KL> relations in DL with binary relations. Note that I use the term
> KL> "present" instead of "define";
> 
> I see.
> 
> KL> also not all the N-ary relations can be
> KL> presented in DL, but some of them can be presented in DL depending on
> KL> the problems. Once a N-ary relation is presented in DL, you get the
> KL> ability of DL for free.
> 
> ok, the question remains: what can one do w/ these "presentations" ..
> 
> KL>
> KL> Here is an example which may be helpful for understanding:
> KL>
> KL> We measure chemical element A on material B and get a value V with a
> KL> unit U. To specify it in FOL, we may use a relation Measure(A, B, V,
> U).
> 
> or we can use a triple even (as in F-logic or EAV or RDF), right?
> 
> In terms of *representation*, we just need triples. Actually, I wonder
> whether one can get away even with a single binary relation (and
> a powerful underlying universe ..)
> 
> KL> To present this 4-ary relation in DL, we define a new class
> Measurement
> KL> and 4 properties:
> KL>
> KL>      subject : Measurement -> Material
> KL>      object  : Measurement -> Element
> KL>      value   : Measurement -> int
> KL>      unit    : Measurement -> Unit
> KL>
> KL> In other words, a measurement is a composition of a element, a
> material,
> KL> a value and a unit. You can add DL constraints on these properties.
> 
> 
> OK, to me this looks like the class Measurement is a unary predicate.
> There are 4 binary relations (called subject/2, object/2, value/2, and
> unit/2, respectively) that associate a Measurement with one things
> such as Material/1, Element/1, int/1, and Unit/1.
> 
> So there is not really a 4-ary relation here, but 4 binary relations
> and a bunch of unary ones.
> 
> I think we kind of agree here :)
> 
> 
> KL> Obviously not all the FOL constraints can be translated into DL
> KL> constraints. For real applications, DL may be enough, may be not.
> 
> correct. But the above example stays within the realm of conventional
> DL it seems (no real n-ary relations are used).
> 
> KL> That W3C document tells us some other patterns we can used to PRESENT
> KL> n-ary relations in DL. They are just some useful tricks, not theory at
> KL> all.
> 
> I think I see your point. I agree that with "tricks" like the above,
> one can get representations of n-ary relations via n binary
> relations. It seems to make a big difference also what assumptions we
> make about the underlying UoD, i.e., whether we have "complex" domain
> elements or not.. The Ebbinghaus-Flum logic book has a discussion on
> that (need to look up the reference again..)
> 
> cheers
> 
> Bertram
> 
> KL>
> KL> -- Kai
> KL>
> KL>
> KL>
> KL> -----Original Message-----
> KL> From: Bertram Ludaescher [mailto:ludaesch at ucdavis.edu]
> KL> Sent: Friday, June 16, 2006 9:02 AM
> KL> To: Kai Lin
> KL> Cc: Bertram Ludaescher; seek-kr-sms at ecoinformatics.org
> KL> Subject: RE: [seek-kr-sms] OBOE clarifications and questions
> KL>
> KL>
> KL> Kai:
> KL>
> KL> Great to hear from you! I need to check out that reference more
> KL> carefully...  But I can already say that no matter what the W3C says,
> KL> there are mathematical truths that are above the W3C standardization
> KL> processes and that by their very nature will outlast W3C, the Web, the
> KL> life span of mankind, the biosphere (life on planet Earth), and maybe
> KL> the universe/multiverse itself (ok, I'm getting a bit more speculative
> KL> towards the end ;-)
> KL>
> KL> If I want to relate n objects simultaneously, I can use, e.g., an
> KL> n-ary relation symbol R(A1,..., An), or I can use a first-order
> KL> formula with n free variables.
> KL>
> KL> However, in general I can no longer decide satisfiability (and related
> KL> notions) in such first-order fragments.
> KL>
> KL> I just came across the following very nice material that might shed
> KL> some light on this -- here are the slides:
> KL>     http://www-mgi.informatik.rwth-aachen.de/~graedel/kalmar.pdf
> KL> (e.g. slide #53 shows how one can express the existence of a path of
> KL> length 17 in FO2, i.e., in FO w/ only two variables.
> KL>
> KL> And here is the paper that apparently goes with the slides:
> KL>     http://citeseer.ist.psu.edu/631148.html
> KL>
> KL> enjoy!
> KL>
> KL> Bertram
> KL>
> KL>
> KL>
> >>> 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.
> KL> Actually
> KL> it is possible to specify N-ary relations in OWL or RDF. The OWL
> KL> working
> KL> group in W3C has a formal document on this issue. You can find it at
> KL> 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
> KL> Josh
> KL> had passed on to Shawn (now let's do an annotation/data lineage
> KL> graph
> KL> for THAT! ;-)
> KL>
> KL> Ontologies expressed in description logic have certain limitations
> KL> 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
> KL> two
> KL> domain elements. So in general you cannot make statements that
> KL> 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
> KL> 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
> KL> 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>
> KL> http://mercury.nceas.ucsb.edu/ecoinformatics/mailman/listinfo/seek-kr-
> sm
> KL> s
> KL>
> 
> _______________________________________________
> Seek-kr-sms mailing list
> Seek-kr-sms at ecoinformatics.org
> http://mercury.nceas.ucsb.edu/ecoinformatics/mailman/listinfo/seek-kr-sms



More information about the Seek-kr-sms mailing list