Impacts of Logic and Databases (Invited Paper).

@inproceedings{DBLP:conf/vldb/Gallaire81,
  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, http://dblp.uni-trier.de}
}

Abstract

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[AHOS]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[AHOU]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[ANSI]

...

[ARMS]

William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX

[ARTA]

...

[BANC]

François Bancilhon: On the Completeness of Query Languages for Relational Data Bases. MFCS 1978: 112-123 BibTeX

[BEER1]

Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX

[BEER2]

Catriel Beeri, Moshe Y. Vardi: The Implication Problem for Data Dependencies. ICALP 1981: 73-85 BibTeX

[BERN]

Philip A. Bernstein, Barbara T. Blaustein, Edmund M. Clarke: Fast Maintenance of Semantic Integrity Assertions Using Redundant Aggregate Data. VLDB 1980: 126-136 BibTeX

[BISK]

Joachim Biskup: A Formal Approach to Null Values in Database Relations. Advances in Data Base Theory 1979: 299-341 BibTeX

[CASA1]

Marco A. Casanova, Philip A. Bernstein: The Logic of a Relational Data Manipulation Language. POPL 1979: 101-109 BibTeX

[CASA2]

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

[CHAG1]

Chin-Liang Chang: DEDUCE 2: Further Investigations of Deduction in Relational Data Bases. Logic and Data Bases 1977: 201-236 BibTeX

[CHAG2]

Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX

[CHAN1]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases (Preliminary Report). STOC 1979: 309-318 BibTeX

[CHAN2]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. FOCS 1980: 333-347 BibTeX

[CHAN3]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[CLAR]

Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX

[CODD1]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[CODD2]

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

[CODD3]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[CODD4]

...

[COOP]

Eric C. Cooper: On the Expressive Power of Query Languages for Relational Databases. POPL 1982: 361-365 BibTeX

[DELO1]

Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX

[DELO2]

...

[DELO3]

...

[DELO4]

Claude Delobel: An Overview of the Relational Data Theory. IFIP Congress 1980: 413-426 BibTeX

[DEMO1]

Robert Demolombe: Semantic Checking of Questions Expressed in Predicate Calculus Language. VLDB 1979: 444-450 BibTeX

[DEMO2]

Robert Demolombe: Assigning Meaning to Ill-Defined Queries Expressed in Predicate Caculus Language. Advances in Data Base Theory 1979: 367-395 BibTeX

[DEMO3]

Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 BibTeX

[DIPA]

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

[DOYL]

Jon Doyle: A Truth Maintenance System. Artif. Intell. 12(3): 231-272(1979) BibTeX

[ENDE]

...

[FAGI]

Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX

[FAGI2]

Ronald Fagin: Horn Clauses and Database Dependencies (Extended Abstract). STOC 1980: 123-134 BibTeX

[FAGI3]

...

[FLOR]

...

[FURU]

...

[GALL1]

...

[GALL2]

...

[GARD]

Georges Gardarin, Michel A. Melkanoff: Proving Consistency of Database Transactions. VLDB 1979: 291-298 BibTeX

[GRAN1]

John Grant: Null Values in a Relational Data Base. Inf. Process. Lett. 6(5): 156-157(1977) BibTeX

[GRAN2]

John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX

[GRAN3]

...

[HAMM]

Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 BibTeX

[HARE]

...

[JACO]

...

[JANA]

Jürgen M. Janas: Towards more Informative User Interfaces. VLDB 1979: 17-23 BibTeX

[KELL]

Charles Kellogg, Larry Travis: Reasoning with Data in a Deductively Augmented Data Management System. Advances in Data Base Theory 1979: 261-295 BibTeX

[KING]

...

[KOWA]

...

[KUHN1]

...

[KUHN2]

...

[LACR]

...

[LIPS]

Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX

[MAIB]

...

[MAIE]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[McSK]

...

[MEND]

Alberto O. Mendelzon, David Maier: Generalized Mutual Dependencies and the Decomposition of Database Relations. VLDB 1979: 75-82 BibTeX

[MENE]

...

[MINK]

Jack Minker: An Experimental Relational Data Base System Based on Logic. Logic and Data Bases 1977: 107-147 BibTeX

[NAQV]

Shamim A. Naqvi, Lawrence J. Henschen: Performing Inferences over Recursive Data Bases. AAAI 1980: 263-265 BibTeX

[NICO1]

Jean-Marie Nicolas: Mutual Dependencies and Some Results on Undecomposable Relations. VLDB 1978: 360-367 BibTeX

[NICO2]

Jean-Marie Nicolas: First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies. SIGMOD Conference 1978: 40-46 BibTeX

[NICO3]

Jean-Marie Nicolas, Kioumars Yazdanian: Integrity Checking in Deductive Data Bases. Logic and Data Bases 1977: 325-344 BibTeX

[NICO4]

...

[NICO5]

Jean-Marie Nicolas, Jean-Claude Syre: Natural Language Question Answering and Automatic Deduction in the System Syntex. IFIP Congress 1974: 595-599 BibTeX

[NICO6]

Jean-Marie Nicolas, Hervé Gallaire: Data Base: Theory vs. Interpretation. Logic and Data Bases 1977: 33-54 BibTeX

[PARE1]

Jan Paredaens, Dirk Janssens: Decompositions of Relations: A Comprehensive Approach. Advances in Data Base Theory 1979: 73-100 BibTeX

[PARE2]

Jan Paredaens: On the Expressive Power of the Relational Algebra. Inf. Process. Lett. 7(2): 107-111(1978) BibTeX

[PARK]

Douglas Stott Parker Jr., Claude Delobel: Algorithmic Applications for a new Result on Multivalued Dependencies. VLDB 1979: 67-74 BibTeX

[PIRO1]

...

[PIRO2]

Alain Pirotte: High Level Data Base Query Languages. Logic and Data Bases 1977: 409-436 BibTeX

[PRAT]

Vaughan R. Pratt: Semantical Considerations on Floyd-Hoare Logic. FOCS 1976: 109-121 BibTeX

[REIT1]

Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) BibTeX

[REIT2]

Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX

[REIT3]

Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177 BibTeX

[REIT4]

Raymond Reiter: Equality and Domain Closure in First-Order Databases. J. ACM 27(2): 235-249(1980) BibTeX

[REIT5]

...

[REIT6]

Raymond Reiter: On the Integrity of Typed First Order Data Bases. Advances in Data Base Theory 1979: 137-157 BibTeX

[REIT7]

...

[RISS]

Jorma Rissanen: Theory of Relations for Databases - A Tutorial Survey. MFCS 1978: 536-551 BibTeX

[ROUS]

...

[SADR]

Fereidoon Sadri, Jeffrey D. Ullman: A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. STOC 1980: 117-122 BibTeX

[SAGI1]

...

[SAGI2]

...

[SAGI3]

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

[SAGI4]

Yehoshua Sagiv: An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic. J. ACM 27(2): 250-262(1980) BibTeX

[SCHW]

...

[SHAP]

Stuart C. Shapiro, Donald P. McKay: Inference with Recursive Rules. AAAI 1980: 151-153 BibTeX

[SIG]

...

[SILV]

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

[STON1]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[STON2]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[ULLM]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

[VASS1]

Yannis Vassiliou: Functional Dependencies and Incomplete Information. VLDB 1980: 260-269 BibTeX

[VASS2]

Yannis Vassiliou: Null Values in Data Base Management: A Denotational Semantics Approach. SIGMOD Conference 1979: 162-169 BibTeX

[YANN]

Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 BibTeX

[ZANI]

...

[ZLOO]

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