The complexity of querying indefinite information: Defined relations, recursion and linear order [microform]
- Bib ID:
- 3287797
- Format:
- Book and Microform
- Author:
- Van Der Meyden, Ronald
- Description:
- 209 p.
- Summary:
-
This dissertation studies the computational complexity of answering queries in logical databases containing indefinite information arising from two sources: facts stated in terms of defined relations, and incomplete information about linearly ordered domains. First, we consider databases consisting of (1) a DATALOG program and (2) a description of the world in terms of the predicates defined by the program as well as the basic predicates. The query processing problem in such databases is related to issues in database theory, including view updates and DATALOG optimization, and also to the Artificial Intelligence problems of reasoning in circumscribed theories and skeptical abductive reasoning.
If the program is non-recursive, the meaning of the database can be represented by Clark's Predicate Completion, and standard first order theorem proving technology may be used to evaluate queries. However, with recursive definitions such databases are intrinsically second order, and query processing is not even semi-decidable. Nevertheless, the basic queries, which do not contain defined predicates, are decidable. We show that under certain conditions querying this second order form of indefinite information is no more complex than querying indefinite information expressible in first order logic. We also consider the influence of negation and inequality on complexity. Next, we study databases containing basic atomic facts and facts asserting order relations between points in a linearly ordered domain.
Incomplete information about a linearly ordered domain means that the data provide only a partial order, and a query answering requires reasoning about all the compatible linear orders. We show the complexity of this inference problem is in general intractable, but identify a variety of natural conditions under which queries may be answered in polynomial time. Finally, we consider the effect of combining the two sorts of indefinite information: we study databases containing facts defined using recursive rules with linear order constraints. Applications of such rules include reasoning about concurrent, repetitive actions. In general, even the basic queries are undecidable in this context, but by restricting definitions to a reasonable class, we are able to recapture decidability. Further, under a constraint of "bounded concurrency," query processing is in polynomial time.
- Notes:
-
- (UnM)AAI9321333
- Source: Dissertation Abstracts International, Volume: 54-05, Section: B, page: 2606.
- Director: L. Thorne McCarty.
- Thesis (Ph.D.)--Rutgers The State University of New Jersey - New Brunswick, 1992.
- Reproduction:
- Microfiche. Ann Arbor, Mich.: University Microfilms International.
- Subject:
- Computer Science
- Other authors/contributors:
- Rutgers The State University of New Jersey - New Brunswick
- Copyright:
-
In Copyright
Contact us for information about copying.
Copyright status was determined using the following information:
- Material type:
- Literary Dramatic Musical
- Published status:
- Unpublished
- Creation date:
- 1992
Copyright status may not be correct if data in the record is incomplete or inaccurate. Other access conditions may also apply. For more information please see: Copyright in library collections.
Request this item
Request this item to view in the Library’s reading room.
Feedback
Similar items
- Acts of the twenty-ninth General Assembly of the state of New-Jersey. [electronic resource] : At a session begun at Trenton, on Tuesday,the twenty-third day of October, one thousand eight hundred and four, and continued by adjournments. : Being the first sitting
- An act for the gradual abolition of slavery [electronic resource]
- Anno regni Georgii Regis Magnae Britanniae, Franciae & Hiberniae nono [electronic resource] : At a sessions of the General Assembly for the province of New-Jersey begun the five and twentieth day of May, 1725. and continued to the 23th of August following, at which time the following acts were passed and published
- An ordinance for regulating courts of judicatnre [sic] in the province of New-Jersey [electronic resource]
- An ordinance for regulating the times of sitting of the courts of judicature in the province of New-Jersey [electronic resource]