[seek-kr-sms] OBOE clarifications and questions

[Shawn Bowers]

These are great pointers -- thanks!

-shawn



On Fri, 16 Jun 2006, Bertram Ludaescher wrote:

>
> 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
>
> _______________________________________________
> Seek-kr-sms mailing list
> Seek-kr-sms at ecoinformatics.org
> http://mercury.nceas.ucsb.edu/ecoinformatics/mailman/listinfo/seek-kr-sms
>