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)

[AHOU]

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

[ANSI]

...

[ARMS]

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

[ARTA]

...

[BANC]

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

[BEER1]

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

[BEER2]

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

[BERN]

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

[BISK]

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

[CASA1]

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

[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)

[CHAG1]

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

[CHAG2]

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

[CHAN1]

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

[CHAN2]

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

[CHAN3]

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

[CLAR]

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

[CODD1]

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

[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)

[CODD3]

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

[CODD4]

...

[COOP]

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

[DELO1]

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

[DELO2]

...

[DELO3]

...

[DELO4]

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

[DEMO1]

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

[DEMO2]

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

[DEMO3]

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

[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)

[DOYL]

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

[ENDE]

...

[FAGI]

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

[FAGI2]

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

[FAGI3]

...

[FLOR]

...

[FURU]

...

[GALL1]

...

[GALL2]

...

[GARD]

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

[GRAN1]

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

[GRAN2]

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

[GRAN3]

...

[HAMM]

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

[HARE]

...

[JACO]

...

[JANA]

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

[KELL]

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

[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)

[MAIB]

...

[MAIE]

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

[McSK]

...

[MEND]

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

[MENE]

...

[MINK]

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

[NAQV]

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

[NICO1]

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

[NICO2]

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

[NICO3]

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

[NICO4]

...

[NICO5]

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

[NICO6]

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

[PARE1]

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

[PARE2]

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

[PARK]

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

[PIRO1]

...

[PIRO2]

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

[PRAT]

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

[REIT1]

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

[REIT2]

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

[REIT3]

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

[REIT4]

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

[REIT5]

...

[REIT6]

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

[REIT7]

...

[RISS]

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

[ROUS]

...

[SADR]

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

[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)

[SAGI4]

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

[SCHW]

...

[SHAP]

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

[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

[STON1]

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

[STON2]

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

[ULLM]

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

[VASS1]

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

[VASS2]

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

[YANN]

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

[ZANI]

...

[ZLOO]

Moshé M. Zloof: Query-by-Example: A Data Base Language. IBM Systems Journal 16(4): 324-343(1977)