Impacts of Logic and Databases (Invited Paper).

Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259
  author    = {Herv{\'e} Gallaire},
  title     = {Impacts of Logic and Databases (Invited Paper)},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {248-259},
  ee        = {db/conf/vldb/Gallaire81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP,}


This paper deals with the relationships between logic and relational data bases. A goal of the paper is to show, through many results published in the literature, how logic can provide a formal support to study classical database problems, and in some cases, how logic can go further, helping first in their comprehension, and then in their solution. The main points discussed are : query evaluation and data base schema analysis.

Key words : relational data bases, logic, query languages, integrity constraints, deductive data bases, query evaluation, dependencies, data base schema analysis.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX


Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
François Bancilhon: On the Completeness of Query Languages for Relational Data Bases. MFCS 1978: 112-123 BibTeX
Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX
Catriel Beeri, Moshe Y. Vardi: The Implication Problem for Data Dependencies. ICALP 1981: 73-85 BibTeX
Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136 BibTeX
Joachim Biskup: A Formal Approach to Null Values in Database Relations. Advances in Data Base Theory 1979: 299-341 BibTeX
Marco A. Casanova, Philip A. Bernstein: The Logic of a Relational Data Manipulation Language. POPL 1979: 101-109 BibTeX
Marco A. Casanova, Philip A. Bernstein: A Formal System for Reasoning about Programs Accessing a Relational Database. ACM Trans. Program. Lang. Syst. 2(3): 386-414(1980) BibTeX
Chin-Liang Chang: DEDUCE 2: Further Investigations of Deduction in Relational Data Bases. Logic and Data Bases 1977: 201-236 BibTeX
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases (Preliminary Report). STOC 1979: 309-318 BibTeX
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. FOCS 1980: 333-347 BibTeX
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
Eric C. Cooper: On the Expressive Power of Query Languages for Relational Databases. POPL 1982: 361-365 BibTeX
Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX
Claude Delobel: An Overview of the Relational Data Theory. IFIP Congress 1980: 413-426 BibTeX
Robert Demolombe: Semantic Checking of Questions Expressed in Predicate Calculus Language. VLDB 1979: 444-450 BibTeX
Robert Demolombe: Assigning Meaning to Ill-Defined Queries Expressed in Predicate Caculus Language. Advances in Data Base Theory 1979: 367-395 BibTeX
Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 BibTeX
Robert A. Di Paola: The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. J. ACM 16(2): 324-327(1969) BibTeX
Jon Doyle: A Truth Maintenance System. Artif. Intell. 12(3): 231-272(1979) BibTeX
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
Ronald Fagin: Horn Clauses and Database Dependencies (Extended Abstract). STOC 1980: 123-134 BibTeX
Georges Gardarin, Michel A. Melkanoff: Proving Consistency of Database Transactions. VLDB 1979: 291-298 BibTeX
John Grant: Null Values in a Relational Data Base. Inf. Process. Lett. 6(5): 156-157(1977) BibTeX
John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX
Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 BibTeX
Jürgen M. Janas: Towards more Informative User Interfaces. VLDB 1979: 17-23 BibTeX
Charles Kellogg, Larry Travis: Reasoning with Data in a Deductively Augmented Data Management System. Advances in Data Base Theory 1979: 261-295 BibTeX
Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
Alberto O. Mendelzon, David Maier: Generalized Mutual Dependencies and the Decomposition of Database Relations. VLDB 1979: 75-82 BibTeX
Jack Minker: An Experimental Relational Data Base System Based on Logic. Logic and Data Bases 1977: 107-147 BibTeX
Shamim A. Naqvi, Lawrence J. Henschen: Performing Inferences over Recursive Data Bases. AAAI 1980: 263-265 BibTeX
Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367 BibTeX
Jean-Marie Nicolas: First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies. SIGMOD Conference 1978: 40-46 BibTeX
Jean-Marie Nicolas, Kioumars Yazdanian: Integrity Checking in Deductive Data Bases. Logic and Data Bases 1977: 325-344 BibTeX
Jean-Marie Nicolas, Jean-Claude Syre: Natural Language Question Answering and Automatic Deduction in the System Syntex. IFIP Congress 1974: 595-599 BibTeX
Jean-Marie Nicolas, Hervé Gallaire: Data Base: Theory vs. Interpretation. Logic and Data Bases 1977: 33-54 BibTeX
Jan Paredaens, Dirk Janssens: Decompositions of Relations: A Comprehensive Approach. Advances in Data Base Theory 1979: 73-100 BibTeX
Jan Paredaens: On the Expressive Power of the Relational Algebra. Inf. Process. Lett. 7(2): 107-111(1978) BibTeX
Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74 BibTeX
Alain Pirotte: High Level Data Base Query Languages. Logic and Data Bases 1977: 409-436 BibTeX
Vaughan R. Pratt: Semantical Considerations on Floyd-Hoare Logic. FOCS 1976: 109-121 BibTeX
Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) BibTeX
Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX
Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177 BibTeX
Raymond Reiter: Equality and Domain Closure in First-Order Databases. J. ACM 27(2): 235-249(1980) BibTeX
Raymond Reiter: On the Integrity of Typed First Order Data Bases. Advances in Data Base Theory 1979: 137-157 BibTeX
Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX
Fereidoon Sadri, Jeffrey D. Ullman: A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. STOC 1980: 117-122 BibTeX
Yehoshua Sagiv, Claude Delobel, Douglas Stott Parker Jr., Ronald Fagin: An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic. J. ACM 28(3): 435-453(1981) BibTeX
Yehoshua Sagiv: An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic. J. ACM 27(2): 250-262(1980) BibTeX
Stuart C. Shapiro, Donald P. McKay: Inference with Recursive Rules. AAAI 1980: 151-153 BibTeX
Antonio M. Silva, Michel A. Melkanoff: A Method for Helping Discover the Dependencies of a Relation. Advances in Data Base Theory 1979: 115-133 BibTeX
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269 BibTeX
Yannis Vassiliou: Null Values in Data Base Management: A Denotational Semantics Approach. SIGMOD Conference 1979: 162-169 BibTeX
Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 BibTeX
Moshé M. Zloof: Query-by-Example: A Data Base Language. IBM Systems Journal 16(4): 324-343(1977) BibTeX

Referenced by

  1. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
  2. A. Y. Lu, Phillip C.-Y. Sheu: Processing of Multiple Queries in Distributed Databases. ICDE 1991: 42-49
  3. Hervé Gallaire, Jean-Marie Nicolas: Logic and Databases: An Assessment. ICDT 1990: 177-186
  4. Won S. Lee, Phillip C.-Y. Sheu: An Object-based Query Evaluation Scheme for Deductive Databases in Massively Parallel Computing Environment. ICDE 1989: 497-504
  5. Serge Abiteboul: Updates, A New Frontier. ICDT 1988: 1-18
  6. Henryk Rybinski: On First-Order-Logic Databases. ACM Trans. Database Syst. 12(3): 325-349(1987)
  7. C. V. Ramamoorthy, Phillip C.-Y. Sheu: Logic-oriented Object Bases. ICDE 1987: 218-225
  8. Takashi Yokomori: On Analogical Query Processing in Logic Database. VLDB 1986: 376-383
  9. Qiming Chen: A Rule-Based Object/Task Modelling Approach. SIGMOD Conference 1986: 281-292
  10. Motomichi Toyama: Parameterized View Definition and Recursive Relations. ICDE 1986: 707-712
  11. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
  12. Victor Vianu: Dynamic Constraints and Database Evolution. PODS 1983: 389-399
  13. Walter Dosch, Gianfranco Mascari, Martin Wirsing: On the Algebraic Specification of Databases. VLDB 1982: 370-385
  14. David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:12 2009