AIC Seminar Series
Efficiently Ordering Subgoals with Access Constraints
|Guizhen Yang||Aritificial Intelligence Center, SRI International||[Home Page]|
Date: Thursday, September 28th 2006 at 4:00pm
Location: EJ228 (Directions)
Ordering subgoals under binding pattern restrictions is an important
problem of practical significance in information integration and query
answering systems. In this talk, we will study the problem of ordering
subgoals under binding pattern restrictions for queries posed as
nonrecursive Datalog programs. We will show that despite their limited
expressive power, the problem is computationally hard PSPACE-complete
in the size of the nonrecursive Datalog program even for fairly restricted
cases. As a practical solution to this problem, we will present an
asymptotically optimal algorithm that runs in time linear in the size of
the query plan. We will also study extensions of our algorithm that
efficiently solve other query planning problems under binding pattern
restrictions. These problems include conjunctive queries with nested grouping
constraints, distributed conjunctive queries, and first-order queries.
Please arrive at least 10 minutes early as you will need to sign in by
following instructions by the lobby phone at Building E. (or call Wilma
Lenz at 650 859 4904, or Vicenta at Lopez at 650 859 5750). SRI is
located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the
parking lots off Fourth Street. Detailed directions to SRI, as well as maps,
are available from the Visiting AIC web page.
There are two entrances to SRI International located on Ravenswood Ave.
Please check the Builing E entrance signage.
©2017 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493