Foundations of Deductive Databases and Logic Programming

This landmark volume explores the close relationship between deductive databases and logic programming and the foundational issues they share. A collection of original research, contributed by leading scientists, the book grew out of preliminary work presented at the Workshop on Foundations of Deductive Databases and Logic Programming held in Washington, DC, August 1986. All the papers have been extensively refereed and revised. Part 1 introduces and examines the import of stratified databases, and its relationship to circumscription, and provides a comprehensive survey of the problem of negation in logic programming. Part 2 addresses fundamental theoretical and practical issues in developing large-scale deductive databases and treats problems such as informative answers, semantic optimization, updates and computing answers in non-Horn theories. Part 3 provides results concerning logic programs and parallel complexity. An introductory survey offering background material and an overview of research topics, name and subject indexes, and extensive bibliographies complete the work. Invaluable to graduate students and researchers in deductive databases and logic programming, Foundations of Deductive Databases and Logic Programming will also be of interest to those working in automated theorem proving, artificial intelligence, and expert systems. Content: Dedication, Page ii Front Matter, Page iii Copyright, Page iv Introduction, Pages 1-16, Jack Minker Chapter 1 - Negation in Logic Programming, Pages 19-88, John C. Shepherdson Chapter 2 - Towards a Theory of Declarative Knowledge, Pages 89-148, Krzysztof R. Apt, Howard A. Blair, Adrian Walker Chapter 3 - Negation as Failure Using Tight Derivations for General Logic Programs, Pages 149-176, Allen Van Gelder Chapter 4 - On the Declarative Semantics of Logic Programs with Negation, Pages 177-192, Vladimir Lifschitz Chapter 5 - On the Declarative Semantics of Deductive Databases and Logic Programs, Pages 193-216, Teodor C. Przymusinski Chapter 6 - On Domain Independent Databases, Pages 217-240, R.W. Topor, E.A. Sonenberg Chapter 7 - Foundations of Semantic Query Optimization for Deductive Databases, Pages 243-273, U.S. Chakravarthy, John Grant, Jack Minker Chapter 8 - Intelligent Query Answering in Rule Based Systems, Pages 275-312, Tomasz Imielinski Chapter 9 - A Theorem-Proving Approach to Database Integrity, Pages 313-362, Fariba Sadri, Robert Kowalski Chapter 10 - A Logic-based Language for Database Updates, Pages 363-394, Sanjay Manchanda, David Scott Warren Chapter 11 - Compiling the GCWA in Indefinite Deductive Databases, Pages 395-438, Lawrence J. Henschen, Hyung-Sik Park Chapter 12 - Performance Evaluation of Data Intensive Logic Programs, Pages 439-517, Francois Bancilhon, Raghu Ramakrishnan Chapter 13 - A Superjoin Algorithm for Deductive Databases, Pages 519-543, James A. Thom, Kotagiri Ramamohanarao, Lee Naish Chapter 14 - Logic Programming and Parallel Complexity, Pages 547-585, Paris C. Kanellakis Chapter 15 - Unification Revisited, Pages 587-625, J-L. Lassez, M.J. Maher, K. Marriott Chapter 16 - Equivalences of Logic Programs, Pages 627-658, M.J. Maher Chapter 17 - Optimizing Datalog Programs, Pages 659-698, Yehoshua Sagiv Chapter 18 - Converting AND-Control to OR-Control by Program Transformation, Pages 699-709, M.H. van Emden, P. Szeredi Authors, Pages 711-713 Referees, Pages 715-716 Author Index, Pages 717-721 Subject Index, Pages 723-746 Foundations of Deductive Databases and Logic Programming focuses on the foundational issues concerning deductive databases and logic programming. The selection first elaborates on negation in logic programming and towards a theory of declarative knowledge. Discussions focus on model theory of stratified programs, fixed point theory of nonmonotonic operators, stratified programs, semantics for negation in terms of special classes of models, relation between closed world assumption and the completed database, negation as a failure, and closed world assumption. The book then takes a look at negation as failure using tight derivations for general logic programs, declarative semantics of logic programs with negation, and declarative semantics of deductive databases and logic programs. The publication tackles converting AND-control to OR-control by program transformation, optimizing dialog, equivalences of logic programs, unification, and logic programming and parallel complexity. Topics include parallelism and structured and unstructured data, parallel algorithms and complexity, solving equations, most general unifiers, systems of equations and inequations, equivalences of logic programs, and optimizing recursive programs. The selection is a valuable source of data for researchers interested in pursuing further studies on the foundations of deductive databases and logic programming.