[seek-dev] [Fwd: Re: [xml-dev] Semantic Web and First Order Logic]
Bertram Ludaescher
ludaesch at sdsc.edu
Sun Mar 30 10:46:22 PST 2003
Hi Matt et al.:
I agree with you: Decidability may not be the most burning
problem. Indeed, whether decidablility is a practical problem or not
depends really on the question what it is that one wants to do:
For example, the statements "SQL is undecidable" and "Java is
undecidable" (or XQuery for that matter) are all true in a certain
sense (but maybe false in another):
-- In SQL it is undecidable whether to queries are equivalent, or
whether on query subsumes another (follows from the undecidability of
first-order logic)
-- In Java the termination problem is undecidable (follows from
undecidabilty of halting problem).
However, nobody would argue that SQL or Java are not practical
languages. Conversely, sometimes decidability is not good enough. For
example, as part of the BIRN project, we recently stumbled over a
query rewriting problem that turned out to be NP-hard. Now we know
that creating "optimal plans" (wrt. a certain criterion) is infeasible
in practice. However, we may get away with some good (albeit not
optimal) plans in quadratic time.
Bottom line: I don't think it is possible to answer some of the
questions raised by XML-dev folks in a meaningful way, unless one
picks a specific problem and then looks at decidability and efficiency
issues for those specific problems.
Coming to our SEEK specific KR/AMS/SMS problems, it requires some
study to find out what mix of formalism we will need. Take
ontologies, for example: if we just want to do "reasonable concept
substitution" as part of say a "smart data discovery query" we may get
away with concept hierarchies. No logic at all.
If we want to define new concepts relative to existing ones, then
description logics (the basis of OWL) will probably be a good choice.
For semantic web languages such as OWL (and RDF) speaks that they may
become standard/widespread. For us as SEEK, however, the harder
problem is to identify what kind of operations we want to support for
KR ontologies, pipelines, etc.
For example, for the type checking and type conversion issues of
analytical pipelines, we may use different formalisms. Maybe we can
check data type compatibility using XML Schema types, and/or on top of
it use "type constraint solving" a la Hindley-Milner or extensions
thereof. I need to do some homework there (and hope my local CS
buddies will help me with the assignment ;-)
Here are two refs that I just found that may be relevant:
http://citeseer.nj.nec.com/demoen99type.html
http://www.lfcs.informatics.ed.ac.uk/reports/98/ECS-LFCS-98-384/
I guess we can do some homework assignment prior to our May meeting
;-)
Bertram
>>>>> "MJ" == Matt Jones <jones at nceas.ucsb.edu> writes:
MJ>
MJ> Bertram,
MJ> This is an interesting thread that's going on now on XML-DEV wrt to
MJ> first order logic and decidability. Do you agree with some of the
MJ> posters that decidability isn't really a practical problem, given that
MJ> 'decidable' itself only tells you something wil take finite time, which
MJ> can be pretty long :) Given that OWL is aiming at FOL, does this have
MJ> any implications for the type of language we choose for use in our
MJ> KR/SMS efforts? Is there a well-known language that would allow us to
MJ> express second order logic (and don't say prolog!)?
MJ>
MJ> Thanks in advance for the tutorial...
MJ>
MJ> Matt
MJ> Return-Path: <xml-dev-return-21673-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id LAA11632
MJ> for <jones at nceas.ucsb.edu>; Thu, 20 Mar 2003 11:51:26 -0800 (PST)
MJ> Received: (qmail 20828 invoked by uid 60909); 20 Mar 2003 19:41:35 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 20822 invoked by uid 60881); 20 Mar 2003 19:41:35 -0000
MJ> X-Spam-Status: No, hits=-3.5 required=8.0
MJ> Message-ID: <3E7A1B27.5050008 at dehora.net>
MJ> Date: Thu, 20 Mar 2003 19:48:55 +0000
MJ> From: =?ISO-8859-1?Q?Bill_de_h=D3ra?= <bill at dehora.net>
MJ> User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.3) Gecko/20030312
MJ> X-Accept-Language: en, en-us
MJ> MIME-Version: 1.0
MJ> To: "Bullard, Claude L (Len)" <clbullar at ingr.com>
MJ> CC: xml-dev at lists.xml.org
MJ> References: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com>
MJ> In-Reply-To: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com>
MJ> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
MJ> Content-Transfer-Encoding: 8bit
MJ> Subject: Re: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> Bullard, Claude L (Len) wrote:
>> Is it true or false that the semantic web
>> limits the use of First Order Logic
MJ>
MJ> RDF is less expressive than FOL, yes. N3 is closer as it has things
MJ> like quantifiers. OWL has 3 levels to cater for how much you want
MJ> ranging from 'I could hack that together' to 'this may never be
MJ> implemented fully'.
MJ>
MJ> This concern about decidability on the semantic web comes from
MJ> description logics work. DLs are carefully designed to allow engines
MJ> to be tractable and scalable when it comes to generating results;
MJ> the downside is that it makes some things awkward to say and
MJ> enforces constraints based on what you can expect a reasoning engine
MJ> to be able to deal with, whether or not you care about reasoning
MJ> engines. IMVHO,if you force content providers and developers to chow
MJ> down on a DL for a length of time, they'll ask for a scripting hook.
MJ> Which kind of defeats the point of using a logic to begin with.
MJ>
MJ> Pat Hayes has written (a very nice read) on how DLs square with the
MJ> semantic web [1]:
MJ>
MJ>
MJ> [[[
MJ> The semantic web doesnt need all these DL guards and limitations,
MJ> because it doesn't need to provide the industrial-quality guarantees
MJ> of inferential performance. Using DLs as a semantic web content
MJ> markup standard is a failure of imagination: it presumes that the
MJ> Web is going to be something like a giant corporation, with the same
MJ> requirements of predictability and provable performance. In fact (if
MJ> the SW ever becomes a reality) it will be quite different from
MJ> current industrial ontology practice in many ways. It will be far
MJ> 'scruffier', for a start; people will use ingenious tricks to scrape
MJ> partly-ill-formed content from ill-structured sources, and there is
MJ> no point in trying to prevent them doing so, or tutting with
MJ> disapproval. But aside from that, it will be on a scale that will
MJ> completely defeat any attempt to restrict inference to manageable
MJ> bounds. If one is dealing with 10|9 assertions, the difference
MJ> between a polynomial complexity class and something worse is largely
MJ> irrelevant. And, further, almost all of this content will be
MJ> extremely simple and shallow, seen from a logical perspective.
MJ> Worrying about the complexity class of the few intricate ontologies
MJ> on the web is like being obsessed with the quality of the salt in a
MJ> supermarket.
MJ> ]]]
MJ>
MJ>
>> I realize that FOL has the undecidability
>> problem, but is sufficient for everyday
>> reasoning and is the most widely used
>> logic in business.
MJ>
MJ> I believe that would be EC logic as used in relational databases and
MJ> Prolog. Otherwise the most widely used 'business logic' is whatever
MJ> you can get to run in a middleware.
MJ>
MJ>
>> I realize that is controversial and is
>> deliberately so. I am wondering if the
>> semantic web is somewhat over-engineered.
MJ>
MJ> It's hardly engineered at all Len, that's the problem ;)
MJ>
MJ> Bill de hÓra
MJ> --
MJ> Propylon
MJ> www.propylon.com
MJ>
MJ> [1]
MJ> http://www.aifb.uni-karlsruhe.de/~sst/is/WebOntologyLanguage/hayes.htm
MJ>
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21678-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id RAA20630
MJ> for <jones at nceas.ucsb.edu>; Thu, 20 Mar 2003 17:24:34 -0800 (PST)
MJ> Received: (qmail 14576 invoked by uid 60909); 21 Mar 2003 01:14:49 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 14570 invoked by uid 60881); 21 Mar 2003 01:14:49 -0000
MJ> X-Spam-Status: No, hits=-0.6 required=8.0
MJ> Date: Thu, 20 Mar 2003 20:20:20 -0500
MJ> From: "Thomas B. Passin" <tpassin at comcast.net>
MJ> To: xml-dev at lists.xml.org
MJ> Message-id: <004c01c2ef48$09e43630$6401a8c0 at tbp1>
MJ> MIME-version: 1.0
MJ> X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2800.1106
MJ> X-Mailer: Microsoft Outlook Express 6.00.2800.1106
MJ> Content-type: text/plain; charset=Windows-1252
MJ> Content-transfer-encoding: 7BIT
MJ> X-Priority: 3
MJ> X-MSMail-priority: Normal
MJ> References: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com>
MJ> Subject: Re: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> [Bullard, Claude L (Len)]
MJ>
>> Is it true or false that the semantic web
>> limits the use of First Order Logic?
>>
>> I realize that FOL has the undecidability
>> problem, but is sufficient for everyday
>> reasoning and is the most widely used
>> logic in business.
MJ>
MJ> I do not think that ordinary business applications today come close to using
MJ> full FOL. Mostly things run on ordinary assertions (this would cover
MJ> relational databases), and sometimes on rulesets. Ordinary markup languages
MJ> are EC - Existential Conjunctive - only one sector of FOL - and they are
MJ> almost always enough for these kinds of uses.
MJ>
MJ> I do not see just what you mean that the semweb "limits the use of" FOL? Do
MJ> you mean that the semweb must use a subset of FOL? I think that will be so
MJ> as a practical matter - full FOL would rarely be seen in the wild, I would
MJ> think. For one thing, it is so specialized and complex that one really
MJ> needs an experienced specialist, from what I have observed.
MJ>
>> One would think that
>> the semantic web as a business application
>> framework would use it profusely given that
>> otherwise, the existing dominant base of
>> relational business systems users would
>> likely not want to be "on the semantic web".
>>
MJ>
MJ> I think almost everything people want to say on the semweb will be sayable
MJ> with EC, because most of it will be simple assertions of facts or
MJ> properties. The ontology builders will want more, and OWL DL could be seen
MJ> as an effort to fill the bulk of that need.
MJ>
MJ> There will be those who want to have less limitations that DL imposes, and
MJ> it remains to be seen how that can work on the open web without ending up
MJ> with mostly undecidable problems soaking up large processing times.
MJ>
MJ> More likely would be some extensions to FOL (like modalities of various
MJ> kinds), but applied to a subset of FOL. After all, you will probably want
MJ> to be able to make assertions about the reliability or probability or period
MJ> of validity, etc., of some assertion, and you need some extensions to do
MJ> that, AFAIK.
MJ>
MJ> Cheers,
MJ>
MJ> Tom P
MJ>
MJ>
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21679-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id SAA22103
MJ> for <jones at nceas.ucsb.edu>; Thu, 20 Mar 2003 18:32:23 -0800 (PST)
MJ> Received: (qmail 19137 invoked by uid 60909); 21 Mar 2003 02:22:41 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 19131 invoked by uid 60881); 21 Mar 2003 02:22:41 -0000
MJ> X-Spam-Status: No, hits=-3.2 required=8.0
MJ> From: Miles Sabin <miles at milessabin.com>
MJ> To: xml-dev at lists.xml.org
MJ> Date: Fri, 21 Mar 2003 02:30:33 +0000
MJ> User-Agent: KMail/1.5
MJ> References: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com> <004c01c2ef48$09e43630$6401a8c0 at tbp1>
MJ> In-Reply-To: <004c01c2ef48$09e43630$6401a8c0 at tbp1>
MJ> MIME-Version: 1.0
MJ> Content-Type: text/plain;
MJ> charset="windows-1252"
MJ> Content-Transfer-Encoding: 7bit
MJ> Content-Disposition: inline
MJ> Message-Id: <200303210230.33407.miles at milessabin.com>
MJ> Subject: Re: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> Thomas B. Passin wrote,
>> I do not think that ordinary business applications today come close
>> to using full FOL. Mostly things run on ordinary assertions (this
>> would cover relational databases), and sometimes on rulesets.
>> Ordinary markup languages are EC - Existential Conjunctive - only one
>> sector of FOL - and they are almost always enough for these kinds of
>> uses.
MJ>
MJ> I disagree.
MJ>
MJ> Actually, I'll go further. Even full first-order logic is too
MJ> restrictive to express many trivial inferences straightforwardly. For
MJ> example,
MJ>
MJ> There's a 5% surcharge on primary coloured widgets
MJ> x is a red widget
MJ> red is a primary colour
MJ>
MJ> therefore,
MJ>
MJ> There's a 5% surcharge on x
MJ>
MJ> This is easy to express in second-order logic, or in first-order logic
MJ> plus set theory (the "plus set theory" bit means that you can forget
MJ> about decidability). Not so easy in plain first-order logic.
MJ>
MJ> Expressive power, decidablity ... pick one.
MJ>
MJ> Cheers,
MJ>
MJ>
MJ> Miles
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21681-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id VAA25303
MJ> for <jones at nceas.ucsb.edu>; Thu, 20 Mar 2003 21:07:05 -0800 (PST)
MJ> Received: (qmail 28467 invoked by uid 60909); 21 Mar 2003 04:57:19 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 28461 invoked by uid 60881); 21 Mar 2003 04:57:19 -0000
MJ> X-Spam-Status: No, hits=-1.7 required=8.0
MJ> Date: Fri, 21 Mar 2003 00:08:27 -0500
MJ> From: "Thomas B. Passin" <tpassin at comcast.net>
MJ> To: xml-dev at lists.xml.org
MJ> Message-id: <001101c2ef67$e84b15a0$6401a8c0 at tbp1>
MJ> MIME-version: 1.0
MJ> X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2800.1106
MJ> X-Mailer: Microsoft Outlook Express 6.00.2800.1106
MJ> Content-type: text/plain; charset=Windows-1252
MJ> Content-transfer-encoding: 7BIT
MJ> X-Priority: 3
MJ> X-MSMail-priority: Normal
MJ> References: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com>
MJ> <004c01c2ef48$09e43630$6401a8c0 at tbp1> <200303210230.33407.miles at milessabin.com>
MJ> Subject: Re: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> [Miles Sabin]
>>
>> I disagree.
>>
>> Actually, I'll go further. Even full first-order logic is too
>> restrictive to express many trivial inferences straightforwardly. For
>> example,
>>
>> There's a 5% surcharge on primary coloured widgets
>> x is a red widget
>> red is a primary colour
>>
>> therefore,
>>
>> There's a 5% surcharge on x
>>
>> This is easy to express in second-order logic, or in first-order logic
>> plus set theory (the "plus set theory" bit means that you can forget
>> about decidability). Not so easy in plain first-order logic.
>>
MJ>
MJ> Hmm, it depends on your definition of FOL, I suppose, and it also depends on
MJ> how you model things. I assumed that FOL includes types and your "plus set"
MJ> stuff (but a set of individuals is a kind of quantifier over individuals, is
MJ> it not?). I take it that in FOL, quantifiers range over individuals while
MJ> in second order logic, quantifiers can range over predicates and relations.
MJ> Is that what you understand?
MJ>
MJ> Applying this to your example, if you used Red(widget), then your statement
MJ> would be about the predicate (ie., Red), and therefore second order, right?
MJ> But the redness can be modeled in other ways.
MJ>
MJ> For example, we could say Color(x,red) and IsPrimaryColor(red). Then your
MJ> example could be stated something like this -
MJ>
MJ> {for all x,y| Widget(x) and Color(x,y) and IsPrimaryColor(y)}==>
MJ> Surcharge(x,5%)
MJ> {Widget(x) and Color(x,red)}
MJ> {IsPrimaryColor(red)}
MJ>
MJ> Now we are only making statements about the arguments, and they are
MJ> individuals, not predicates or relations. So it is FOL, right? And an SQL
MJ> query could extract the surcharge from a database.
MJ>
MJ> OK, I have to admit, second order logic can make things more compact and
MJ> readable, and if you are getting into statements about types (which are
MJ> second order) you probably need it.
MJ>
>> Expressive power, decidablity ... pick one.
>>
MJ>
MJ> Yes ...
MJ>
MJ> Cheers,
MJ>
MJ> Tom P
MJ>
MJ>
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21682-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id DAA02824
MJ> for <jones at nceas.ucsb.edu>; Fri, 21 Mar 2003 03:04:20 -0800 (PST)
MJ> Received: (qmail 7750 invoked by uid 60909); 21 Mar 2003 10:54:31 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 7742 invoked by uid 60881); 21 Mar 2003 10:54:31 -0000
MJ> X-Spam-Status: No, hits=-1.3 required=8.0
MJ> From: "Danny Ayers" <danny666 at virgilio.it>
MJ> To: "Bullard, Claude L \(Len\)" <clbullar at ingr.com>, <xml-dev at lists.xml.org>
MJ> Date: Fri, 21 Mar 2003 12:01:01 +0100
MJ> Message-ID: <BKELLDAGKABIOCHDFDBPKEGDCEAA.danny666 at virgilio.it>
MJ> MIME-Version: 1.0
MJ> Content-Type: text/plain;
MJ> charset="iso-8859-1"
MJ> Content-Transfer-Encoding: 7bit
MJ> X-Priority: 3 (Normal)
MJ> X-MSMail-Priority: Normal
MJ> X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0)
MJ> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106
MJ> In-Reply-To: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com>
MJ> Importance: Normal
MJ> Subject: RE: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> It's an interesting situation really - the work being done on making OWL
MJ> formally solid is very impressive, but then how interested in proof,
MJ> decidability etc are the business community going to be? Messrs. Pascal,
MJ> Date and friends are keen on pointing out how the tools commonly called
MJ> relational DBs are a long way removed from Codd's relational model. Semantic
MJ> web systems may start firmly based on the RDF/OWL model, but then if a
MJ> programmatic hack outside of the model gets the answer 10x faster then you
MJ> can be sure it'll go in.
MJ> Personally I suspect it'll be a very good thing to have over-engineered
MJ> foundations, so the duct tape gets passed up to a higher layer.
MJ>
MJ> Cheers,
MJ> Danny.
MJ>
MJ>
MJ>
>> -----Original Message-----
>> From: Bullard, Claude L (Len) [mailto:clbullar at ingr.com]
>> Sent: 20 March 2003 18:18
>> To: xml-dev at lists.xml.org
>> Subject: [xml-dev] Semantic Web and First Order Logic
>>
>>
>> Is it true or false that the semantic web
>> limits the use of First Order Logic?
>>
>> I realize that FOL has the undecidability
>> problem, but is sufficient for everyday
>> reasoning and is the most widely used
>> logic in business. One would think that
>> the semantic web as a business application
>> framework would use it profusely given that
>> otherwise, the existing dominant base of
>> relational business systems users would
>> likely not want to be "on the semantic web".
>>
>> I realize that is controversial and is
>> deliberately so. I am wondering if the
>> semantic web is somewhat over-engineered.
>>
>> len
>>
>> -----------------------------------------------------------------
>> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
>> initiative of OASIS <http://www.oasis-open.org>
>>
>> The list archives are at http://lists.xml.org/archives/xml-dev/
>>
>> To subscribe or unsubscribe from this list use the subscription
>> manager: <http://lists.xml.org/ob/adm.pl>
>>
MJ>
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21688-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id GAA07242
MJ> for <jones at nceas.ucsb.edu>; Fri, 21 Mar 2003 06:23:55 -0800 (PST)
MJ> Received: (qmail 28363 invoked by uid 60909); 21 Mar 2003 14:14:06 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 28357 invoked by uid 60881); 21 Mar 2003 14:14:06 -0000
MJ> X-Spam-Status: No, hits=-3.5 required=8.0
MJ> From: Miles Sabin <miles at milessabin.com>
MJ> To: xml-dev at lists.xml.org
MJ> Date: Fri, 21 Mar 2003 14:22:01 +0000
MJ> User-Agent: KMail/1.5
MJ> References: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0AB at hq1.pcmail.ingr.com> <200303210230.33407.miles at milessabin.com> <001101c2ef67$e84b15a0$6401a8c0 at tbp1>
MJ> In-Reply-To: <001101c2ef67$e84b15a0$6401a8c0 at tbp1>
MJ> MIME-Version: 1.0
MJ> Content-Type: text/plain;
MJ> charset="windows-1252"
MJ> Content-Transfer-Encoding: 7bit
MJ> Content-Disposition: inline
MJ> Message-Id: <200303211422.01255.miles at milessabin.com>
MJ> Subject: Re: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> Thomas B. Passin wrote,
>> [Miles Sabin]
>> > This is easy to express in second-order logic, or in first-order
>> > logic plus set theory (the "plus set theory" bit means that you can
>> > forget about decidability). Not so easy in plain first-order logic.
>>
>> Hmm, it depends on your definition of FOL, I suppose, and it also
>> depends on how you model things. I assumed that FOL includes types
>> and your "plus set" stuff
MJ>
MJ> Those'd be first-order theories (ie. they're expressed in first-order
MJ> logic) but they're not first-order logic. And they're not necessarily
MJ> decidable (a type theory might be, set theory isn't).
MJ>
>> (but a set of individuals is a kind of quantifier over individuals, is
>> it not?).
MJ>
MJ> In first-order set-theory a set of individuals is an individual in it's
MJ> own right, not a quantifier.
MJ>
>> I take it that in FOL, quantifiers range over individuals while in
>> second order logic, quantifiers can range over predicates and
>> relations. Is that what you understand?
MJ>
MJ> More or less.
MJ>
>> Applying this to your example, if you used Red(widget), then your
>> statement would be about the predicate (ie., Red), and therefore
>> second order, right?
MJ>
MJ> Yup.
MJ>
>> But the redness can be modeled in other ways.
MJ>
MJ> Oh, sure. I mentioned one: first-order logic plus set-theory.
MJ>
>> For example, we could say Color(x,red) and IsPrimaryColor(red). Then
>> your example could be stated something like this -
>>
>> {for all x,y| Widget(x) and Color(x,y) and IsPrimaryColor(y)}==>
>> Surcharge(x,5%)
>> {Widget(x) and Color(x,red)}
>> {IsPrimaryColor(red)}
>>
>> Now we are only making statements about the arguments, and they are
>> individuals, not predicates or relations. So it is FOL, right? And
>> an SQL query could extract the surcharge from a database.
MJ>
MJ> It's a first-order _theory_, but it's not first-order _logic_. Chances
MJ> are that the first-order theory of widget-colour-surchages will be
MJ> decidable, but that's not true of first-order theories in general: viz.
MJ> arithmetic, set-theory ...
MJ>
MJ> And this is where the constraint that Len was complaining about bites:
MJ> the base-level logical frameworks being considered for the SW insist on
MJ> decidability, and that excludes many practically useful, tho' formally
MJ> undecidable first-order theories.
MJ>
MJ> Here's something else you might try to first-orderize nicely,
MJ>
MJ> Some widgets attach only to one another
MJ>
MJ> You can express this is second-order logic,
MJ>
MJ> {exists P |
MJ> {exists x | Px } and
MJ> {for all x |
MJ> Px ==>
MJ> Widget(x) and {for all y | attach(x, y) ==> Py } } }
MJ>
MJ> and you can express it in first-order set theory,
MJ>
MJ> {exists X |
MJ> {exists x | member(x, X) } and
MJ> {for all x |
MJ> member(x, X) ==>
MJ> Widget(x) and {for all y | attach(x, y) ==> member(y, X) } } }
MJ>
MJ> but neither second-order logic nor first-order set theory are decidable,
MJ> so neither of these renderings is compatible with the frameworks touted
MJ> for the SW which respect the decidability constraint. Can you come up
MJ> with a rendering which is?
MJ>
MJ> OTOH, can you persuade me that this kind of assertion is irrelevant to
MJ> business applications? All it's doing is saying that there's a binary
MJ> relation ("attach" in the example) which partitions the domain of
MJ> widgets in a particular way. That seems like a useful kind of thing to
MJ> be able to say.
MJ>
MJ> Cheers,
MJ>
MJ>
MJ> Miles
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21690-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id GAA07667
MJ> for <jones at nceas.ucsb.edu>; Fri, 21 Mar 2003 06:43:25 -0800 (PST)
MJ> Received: (qmail 478 invoked by uid 60909); 21 Mar 2003 14:33:37 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 472 invoked by uid 60881); 21 Mar 2003 14:33:36 -0000
MJ> X-Spam-Status: No, hits=-1.0 required=8.0
MJ> Message-ID: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0B7 at hq1.pcmail.ingr.com>
MJ> From: "Bullard, Claude L (Len)" <clbullar at ingr.com>
MJ> To: "'Miles Sabin'" <miles at milessabin.com>, xml-dev at lists.xml.org
MJ> Date: Fri, 21 Mar 2003 08:41:26 -0600
MJ> X-Mailer: Internet Mail Service (5.5.2653.19)
MJ> Subject: RE: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> Can you tell me why decidability was given that
MJ> level of importance? This is what I meant by
MJ> "over-engineered" when I could have said "over-specified".
MJ>
MJ> There is a paper from TimBL on the issue of FOL
MJ> and the SemWeb at
MJ>
MJ> http://www.w3.org/DesignIssues/Logic
MJ>
MJ> which I have trouble following not being well-trained
MJ> or just not able to determine his conclusions. Dan
MJ> Connoly comments on it elsewhere. At first, I thought
MJ> it the case that the notion was to not require FOL
MJ> so that other logic systems could be used as needed,
MJ> or as in the spirit of HTML, to make initial fielding
MJ> easy and get some mind share. Your arguments make
MJ> me unsure because requiring decidability would seemingly
MJ> make it harder and cut the SemWeb away
MJ> from uptake of where the majority of the world's
MJ> business semantics reside: relational databases
MJ> with client or server based business rules and logic
MJ> in the form of code libraries. This would appear
MJ> to limit the role of the semweb to being merely
MJ> metadata about web pages, and that isn't that useful.
MJ> So that can't be right.
MJ>
MJ> len
MJ>
MJ> From: Miles Sabin [mailto:miles at milessabin.com]
MJ>
MJ> And this is where the constraint that Len was complaining about bites:
MJ> the base-level logical frameworks being considered for the SW insist on
MJ> decidability, and that excludes many practically useful, tho' formally
MJ> undecidable first-order theories.
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
MJ> Return-Path: <xml-dev-return-21692-jones=nceas.ucsb.edu at lists.xml.org>
MJ> Received: from mail.oasis-open.org ([209.202.168.102])
MJ> by ulysses.nceas.ucsb.edu (980427.SGI.8.8.8/8.8.8-ajr) with SMTP id HAA08406
MJ> for <jones at nceas.ucsb.edu>; Fri, 21 Mar 2003 07:13:18 -0800 (PST)
MJ> Received: (qmail 6039 invoked by uid 60909); 21 Mar 2003 14:59:47 -0000
MJ> Mailing-List: contact xml-dev-help at lists.xml.org; run by ezmlm
MJ> Precedence: bulk
MJ> X-No-Archive: yes
MJ> List-Post: <mailto:xml-dev at lists.xml.org>
MJ> List-Help: <mailto:xml-dev-help at lists.xml.org>
MJ> List-Unsubscribe: <mailto:xml-dev-unsubscribe at lists.xml.org>
MJ> List-Subscribe: <mailto:xml-dev-subscribe at lists.xml.org>
MJ> Delivered-To: mailing list xml-dev at lists.xml.org
MJ> Received: (qmail 6032 invoked by uid 60881); 21 Mar 2003 14:59:47 -0000
MJ> X-Spam-Status: No, hits=-3.5 required=8.0
MJ> From: Miles Sabin <miles at milessabin.com>
MJ> To: xml-dev at lists.xml.org
MJ> Date: Fri, 21 Mar 2003 15:07:42 +0000
MJ> User-Agent: KMail/1.5
MJ> References: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0B7 at hq1.pcmail.ingr.com>
MJ> In-Reply-To: <15725CF6AFE2F34DB8A5B4770B7334EEEAD0B7 at hq1.pcmail.ingr.com>
MJ> MIME-Version: 1.0
MJ> Content-Type: text/plain;
MJ> charset="iso-8859-1"
MJ> Content-Transfer-Encoding: 7bit
MJ> Content-Disposition: inline
MJ> Message-Id: <200303211507.42049.miles at milessabin.com>
MJ> Subject: Re: [xml-dev] Semantic Web and First Order Logic
MJ>
MJ> Bullard, Claude L (Len) wrote,
>> Can you tell me why decidability was given that level of importance?
>> This is what I meant by "over-engineered" when I could have said
>> "over-specified".
MJ>
MJ> No idea. Decidable systems are guaranteed to give answers in finite
MJ> time. That sounds great until you remember that "finite" extends well
MJ> beyond the expected lifespan of the universe.
MJ>
MJ> I think it's just a cool formal property rather than having any real
MJ> practical import. It's also a hot research topic at the formal end of
MJ> academic AI, so there are papers to be written and research projects to
MJ> be done. I guess that's attractive to some.
MJ>
MJ> But it's unnecessarily constraining: for all that inferences in an
MJ> undecidable system aren't guaranteed to terminate, in many practical
MJ> cases they will. After all, when was the last time you worried about
MJ> the halting problem wrt a business system?
MJ>
>> There is a paper from TimBL on the issue of FOL and the SemWeb at
>>
>> http://www.w3.org/DesignIssues/Logic
>>
>> which I have trouble following not being well-trained or just not able
>> to determine his conclusions. Dan Connoly comments on it elsewhere.
MJ>
MJ> As far as I can make it out, TimBL and I are more or less in agreement
MJ> here. I've no idea if that represents his current position.
MJ>
>> At first, I thought it the case that the notion was to not require FOL
>> so that other logic systems could be used as needed, or as in the
>> spirit of HTML, to make initial fielding easy and get some mind share.
>> Your arguments make me unsure because requiring decidability would
>> seemingly make it harder and cut the SemWeb away from uptake of where
>> the majority of the world's business semantics reside: relational
>> databases with client or server based business rules and logic in the
>> form of code libraries. This would appear to limit the role of the
>> semweb to being merely metadata about web pages, and that isn't that
>> useful. So that can't be right.
MJ>
MJ> Can't it? ;-)
MJ>
MJ> Cheers,
MJ>
MJ>
MJ> Miles
MJ>
MJ> -----------------------------------------------------------------
MJ> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
MJ> initiative of OASIS <http://www.oasis-open.org>
MJ>
MJ> The list archives are at http://lists.xml.org/archives/xml-dev/
MJ>
MJ> To subscribe or unsubscribe from this list use the subscription
MJ> manager: <http://lists.xml.org/ob/adm.pl>
More information about the Seek-dev
mailing list