Re: David Karger's issue on inferencing search

Hi mark.  I agree that the 3 specific cases you mention are both
critical and tractable.  Any revision you make that makes it clear
that these 3 cases are what you mean by inferencing search are fine by
me.  Actually, you might be able to reserve inferencing search for
more complex problems by noting that these 3 cases are all instances
of transitive closure.  I think it is plausible for us to assume
transitive closure capability.

d

   From: "Butler, Mark" <Mark_Butler@hplb.hpl.hp.com>
   Cc: www-rdf-dspace@w3.org
   Date: Fri, 16 May 2003 17:37:54 +0100
   X-MailScanner: Found to be clean
   X-Archived-At: http://www.w3.org/mid/5E13A1874524D411A876006008CD059F066A1CB0@0-mail-1.hpl.hp.com
   X-Mailing-List: <www-rdf-dspace@w3.org> archive/latest/249
   X-Loop: www-rdf-dspace@w3.org
   X-SBClass: Nonlocal Origin [192.6.10.2]
   X-Spam-Status: No, hits=2.8 required=5.0 tests=TO_EMPTY,TO_MALFORMED version=2.20
   X-Spam-Level: **
   X-SpamBouncer: 1.5 (2/23/03)
   X-SBPass: NoBounce
   X-SBClass: OK
   X-Folder: Bulk


   Hi David

   RE: Your issue on inferencing search

   [ 029. ]
   Summary: Inferencing Search
   Raised By: David Karger
   Status: open
   Description: 

   3.2.6 

   I am made nervous by the discussion of inferencing search.  This
   formulation takes a tractable database problem and turns it into an
   NP-hard or even undecidable computational nightmare.  I feel much more
   secure factoring the problem into "search what's currently explicit in
   the databse" and "use tools to infer (best effort) new information
   that can be added to the database.

   Equivalence does feel like a "safe" specialized form of inference
   worth giving attention to.

   ================

   When I wrote inferencing search I was thinking about subclass, subproperty
   and equivalence relationships i.e. arguably the core semantic network
   relationships. So can your issue be resolved by:

   1. Replacing the term "inferencing search" with something else? Do you have
   any suggestions?

   2. Noting that when you perform inferencing, often it is advantageous to
   cache results so that these results do not have to be recomputed later on? 

   3. Just by noting that inferencing search may be problematic as you
   highlight?

   Alternatively do you have a suggestion of how to change section 3.2.6 so you
   are happier with the wording? 

   Dr Mark H. Butler
   Research Scientist                HP Labs Bristol
   mark-h_butler@hp.com
   Internet: http://www-uk.hpl.hp.com/people/marbut/

Received on Tuesday, 20 May 2003 02:04:43 UTC