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
- The laws of the state of New-Hampshire [electronic resource] : passed at a session of the Honorable General-Court, begun and holden at Hanover, June, 1795. : Printed from attested copies
- Acts passed by the General Assembly of the province of New-Jersey, in January 1716 [1717 N.S.]. in the third year of the reign of our Soveraign Lord George, by the grace of God, King of Great Britain, France and Ireland, &c [electronic resource]
- Laws of the state of New-Hampshire, June session, 1819 [microform]
- State of New-Hampshire. In the year of our Lord, one thousand seven hundred and eighty-eight [electronic resource] : An act, for carrying into effect an ordinance of Congress of the thirteenth of September last, relative to the Constitution of the United States
- Private and temporary acts. [electronic resource] : Acts of the thirty-sixth General Assembly of the state of New-Jersey. : At a session begun at Trenton, on the eighth day of January, one thousand eight hundred and twelve, and continued by adjournments. : Being the first sitting