Logic and Databases: A Deductive Approach.

@article{DBLP:journals/csur/GallaireMN84,
  author    = {Herv{\'e} Gallaire and
               Jack Minker and
               Jean-Marie Nicolas},
  title     = {Logic and Databases: A Deductive Approach},
  journal   = {ACM Comput. Surv.},
  volume    = {16},
  number    = {2},
  year      = {1984},
  pages     = {153-185},
  ee        = {db/journals/csur/GallaireMN84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

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/An4-1 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/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[Adiba et al. 1982]

...

[Aho and Ullman 1979]

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

[Aho et al. 1979]

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

[ANSI/X3/SPARC 1975]

...

[Armstrong 1974]

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

[Artificial Intelligence Journal 1980]

...

[Artraud and Nicolas 1974]

...

[Bancilhon 1978]

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

[Beeri and Vardi 1980]

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

[Beeri and Vardi 1981]

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

[Biskup 1981]

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

[Biskup 1982]

Joachim Biskup: A Foundation of Codd's Relational Maybe-Operations. ACM Trans. Database Syst. 8(4): 608-636(1983)

[Blaustein 1981]

...

[Borgida and Wong 1981]

Alexander Borgida, Harry K. T. Wong: Data Models and Data Manipulation Languages: Complementary Semantics and Proof Theory. VLDB 1981: 260-271

[Bossu and Siegel 1981]

...

[Bowen and Kowalski 1982]

...

[Brodie and Zilles 1980]

Michael L. Brodie, Stephen N. Zilles (Eds.): Proceedings of the Workshop on Data Abstraction, Databases and Conceptual Modelling, Pingree Park, Colorado, June 23-26, 1980. SIGMOD Record 11(2) ACM Press 1981, ISBN 0-89791-031-1
Contents

[Casanova and Bernstein 1979]

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

[Casanova and Bernstein 1980]

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)

[Chakravarthy et al. 1982]

Upen S. Chakravarthy, Jack Minker, Duc Tran: Interfacing Predicate Logic Languages and Relational Databases. ICLP 1982: 91-98

[Chamberlin et al. 1981]

Donald D. Chamberlin, Morton M. Astrahan, Mike W. Blasgen, Jim Gray, W. Frank King III, Bruce G. Lindsay, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Gianfranco R. Putzolu, Patricia G. Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade, Robert A. Yost: A History and Evaluation of System R. Commun. ACM 24(10): 632-646(1981)

[Chandra and Harel 1979]

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

[Chandra and Harel 1980]

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

[Chandra and Merlin 1976]

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

[Chandra et al. 1981]

Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354

[Chang 1970]

Chin-Liang Chang: The Unit Proof and the Input Proof in Theorem Proving. J. ACM 17(4): 698-707(1970)

[Chang 1978]

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

[Chang 1981]

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

[Chang and Lee 1973]

...

[Clark 1978]

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

[Codd 1970]

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

[Codd 1972]

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)

[Codd 1979]

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

[Codd 1980]

E. F. Codd: Data Models in Database Management. Workshop on Data Abstraction, Databases and Conceptual Modelling 1980: 112-114

[Codd 1982]

E. F. Codd: Relational Database: A Practical Foundation for Productivity. Commun. ACM 25(2): 109-117(1982)

[Colmerauer 1973]

...

[Colmerauer and Pique 1981]

Alain Colmerauer, Jean François Pique: About Natural Logic. Advances in Data Base Theory 1979: 343-365

[Cooper 1980]

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

[Dahl 1982]

Verónica Dahl: On Database Systems Development Through Logic. ACM Trans. Database Syst. 7(1): 102-123(1982)

[Date 1977]

C. J. Date: An Introduction to Database Systems, 2nd Edition. Addison-Wesley 1977

[Date 1981]

C. J. Date: An Introduction to Database Systems, 3rd Edition. Addison-Wesley 1981

[Deliyanni and Kowalski 1979]

Amaryllis Deliyanni, Robert A. Kowalski: Logic and Semantic Networks. Commun. ACM 22(3): 184-192(1979)

[Delobel 1978]

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

[Delobel 1980]

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

[Delobel and Casey 1973]

Claude Delobel, Richard G. Casey: Decomposition of a Data Base and the Theory of Boolean Switching Functions. IBM Journal of Research and Development 17(5): 374-386(1973)

[Delobel and Parker 1978]

...

[Demolombe 1980]

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

[Demolombe 1981]

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

[Demolombe 1982]

...

[DiPaola 1969]

Robert A. Di Paola: The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. J. ACM 16(2): 324-327(1969)

[DosSantos et al. 1981]

...

[Enderton 1972]

...

[Fagin 1977a]

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

[Fagin 1977b]

Ronald Fagin: Functional Dependencies in a Relational Data Base and Propositional Logic. IBM Journal of Research and Development 21(6): 543-544(1977)

[Fagin 1980]

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

[Fagin 1982]

Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982)

[Fagin et al. 1983]

Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365

[Florentin 1974]

J. J. Florentin: Consistency Auditing of Databases. Comput. J. 17(1): 52-58(1974)

[Furukawa 1977]

...

[Galil 1982]

Zvi Galil: An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database. J. ACM 29(1): 96-102(1982)

[Gallaire 1981]

Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259

[Gallaire 1983]

...

[Gallaire and Minker 1978]

Hervé Gallaire, Jack Minker (Eds.): Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977. Advances in Data Base Theory Plemum Press 1978, ISBN 0-306-40060-X
Contents

[Gallaire et al. 1981a]

Hervé Gallaire, Jean-Marie Nicolas, Jack Minker (Eds.): Advances in Data Base Theory, Vol. 1, Based on the Proceedings of the Workshop on Formal Bases for Data Bases, December 12-14, 1979, Centre d'Etudes et de Recherches de l'Ecole Nationale Supérieure de l'Aéronautique et de l'Espace de Toulouse (CERT), France. Advances in Data Base Theory Plemum Press 1981, ISBN 0-306-40629-2
Contents

[Gallaire et al. 1981b]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Background for Advances in Data Base Theory. Advances in Data Base Theory 1979: 3-21

[Gallaire et al. 1984]

Hervé Gallaire, Jean-Marie Nicolas, Jack Minker (Eds.): Advances in Data Base Theory, Vol. 2, Based on the Proceedings of the Workshop on Logical Data Bases, December 14-17, 1982, Centre d'études et de recherches de Toulouse, France. Advances in Data Base Theory Plemum Press 1984, ISBN 0-306-41636-0
Contents

[Gardarin and Melkanoff 1979]

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

[Grant 1977]

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

[Grant and Jacobs 1982]

John Grant, Barry E. Jacobs: On the family of generalized dependency constraints. J. ACM 29(4): 986-997(1982)

[Grant and Minker 1981]

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

[Grant and Minker 1983]

John Grant, Jack Minker: Answering Queries in Indefinite Databases and the Null Value Problem. Advances in Computing Research 3: 247-267(1986)

[Green 1969]

...

[Hammer and Zdonik 1980]

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

[Harel 1979]

David Harel: First-Order Dynamic Logic. Lecture Notes in Computer Science Vol. 68 Springer 1979, ISBN 3-540-09237-4

[Harel 1980]

...

[Henschen et al. 1984]

Lawrence J. Henschen, William McCune, Shamim A. Naqvi: Compiling Constraint-Checking Programs from First-Order Formulas. Advances in Data Base Theory 1982: 145-169

[Hewitt 1972]

...

[Hill 1974]

...

[Homeier 1981]

...

[Imielinski and Lipski 1981]

Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397

[International Joint Conference on Artificial Intelligence 1983]

...

[International Symposium on Logic Programming]

...

[Jacobs 1982]

Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982)

[Jacobs et al. 1982]

Barry E. Jacobs, Alan R. Aronson, Anthony C. Klug: On Interpretations of Relational Languages and Solutions to the Implied Constraint Problem. ACM Trans. Database Syst. 7(2): 291-315(1982)

[Jaffar et al. 1983]

Joxan Jaffar, Jean-Louis Lassez, John W. Lloyd: Completeness of the Negation as Failure Rule. IJCAI 1983: 500-506

[Janas 1979]

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

[Janas 1981]

Jürgen M. Janas: On the Feasibility of Informative Answers. Advances in Data Base Theory 1979: 397-414

[Kellogg and Travis 1981]

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

[Kellogg et al. 1978]

Charles Kellogg, Philip Klahr, Larry Travis: Deductive Planning and Pathfinding for Relational Data Bases. Logic and Data Bases 1977: 179-200

[King 1981]

Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517

[Konolige 1981]

...

[Kowalski 1978]

Robert A. Kowalski: Logic for Data Description. Logic and Data Bases 1977: 77-103

[Kowalski 1979]

...

[Kowalski 1981a]

...

[Kowalski 1981b]

...

[Kowalski and Kuehner 1971]

Robert A. Kowalski, Donald Kuehner: Linear Resolution with Selection Function. Artif. Intell. 2(3/4): 227-260(1971)

[Kuhns 1967]

...

[Kuhns 1970]

...

[Kunifuji and Yokota 1982]

...

[Lacroix and Pirotte]

Michel Lacroix, Alain Pirotte: Associating Types with Domains of Relational Data Bases. Workshop on Data Abstraction, Databases and Conceptual Modelling 1980: 144-146

[Levesque 1981]

...

[Lipski 1979]

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

[Logic Programming Workshop Proceedings 1983]

...

[Loveland 1969]

...

[Loveland 1970]

...

[Loveland 1978]

...

[Maier 1983]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents

[Maier et al. 1979]

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

[McCarthy 1980]

John McCarthy: Circumscription - A Form of Non-Monotonic Reasoning. Artif. Intell. 13(1-2): 27-39(1980)

[McSkimin 1976]

...

[McSkimin and Minker 1977]

...

[Mendelson 1978]

...

[Minker 1975a]

Jack Minker: Performing Inferences over Relation Data Bases. SIGMOD Conference 1975: 79-91

[Minker 1975b]

...

[Minker 1978a]

Jack Minker: Search Strategy and Selection Function for an Inferential Relational System. ACM Trans. Database Syst. 3(1): 1-31(1978)

[Minker 1978b]

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

[Minker 1982]

Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308

[Minker 1983]

...

[Minker and Nicolas 1982]

Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983)

[Minker and Perlis 1983]

...

[Minker and Perlis 1984]

Jack Minker, Donald Perlis: Applications of Protected Circumscription. CADE 1984: 414-425

[Minker and Zanon 1982]

Jack Minker, Guy Zanon: An Extension to Linear Resolution with Selection Function. Inf. Process. Lett. 14(4): 191-194(1982)

[Moore 1981]

...

[Mylopoulos 1980]

John Mylopoulos: An Overview of Knowledge Representation. Workshop on Data Abstraction, Databases and Conceptual Modelling 1980: 5-12

[Naqvi and Henschen 1980]

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

[Naqvi and Henschen 1984]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984)

[Nicolas 1978]

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

[Nicolas 1979a]

...

[Nicolas 1979b]

Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982)

[Nicolas and Gallaire 1978]

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

[Nicolas and Syre 1974]

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

[Nicolas and Yazdanian 1978]

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

[Nicolas and Yazdanian 1982]

Jean-Marie Nicolas, Kioumars Yazdanian: An Outline of BDGEN: A Deductive DBMS. IFIP Congress 1983: 711-717

[Paredaens 1978]

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

[Parker and Delobel 1979]

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

[Pirotte 1976]

...

[Pirotte 1978]

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

[Pratt 1976]

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

[Proceedings of the First conference on Logic Programming 1982]

...

[Reiter 1971]

Raymond Reiter: Two Results on Ordering for Resolution with Merging and Linear Format. J. ACM 18(4): 630-646(1971)

[Reiter 1978a]

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

[Reiter 1978b]

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

[Reiter 1978c]

...

[Reiter 1980]

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

[Reiter 1981]

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

[Reiter 1982]

Raymond Reiter: Circumscription Implies Predicate Completion (Sometimes). AAAI 1982: 418-420

[Reiter 1983]

Raymond Reiter: A sound and sometimes complete query evaluation algorithm for relational databases with null values. J. ACM 33(2): 349-370(1986)

[Reiter 1984]

Raymond Reiter: Towards a Logical Reconstruction of Relational Database Theory. On Conceptual Modelling (Intervale) 1982: 191-233

[Robinson 1965]

John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965)

[Roussel 1975]

...

[Sadri and Ullman 1980]

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

[Sadri and Ullman 1982]

Fereidoon Sadri, Jeffrey D. Ullman: Template Dependencies: A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization. J. ACM 29(2): 363-372(1982)

[Sagiv 1980]

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

[Sagiv and Fagin 1979]

...

[Sagiv et al. 1981]

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)

[Selinger et al. 1979]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34

[Shapiro and McKay 1980]

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

[Siklossy and Lauriere 1982]

Laurent Siklóssy, Jean-Louis Laurière: Removing Restrictions in the Relational Data Base Model: An Application of Problem Solving Techniques. AAAI 1982: 310-313

[Stonebraker et al. 1976]

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

[Ullman 1980]

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

[Ullman 1982]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

[van Emden 1978]

...

[van Emden and Kowalski 1976]

Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976)

[Vardi 1981]

Moshe Y. Vardi: The Decision Problem for Database Dependencies. Inf. Process. Lett. 12(5): 251-254(1981)

[Vassiliou 1979]

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

[Vassiliou 1980]

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

[Veloso et al. 1981]

Paulo A. S. Veloso, José Mauro Volkmer de Castilho, Antonio L. Furtado: Systematic Derivation of Complementary Specifications. VLDB 1981: 409-421

[Warren 1981]

David H. D. Warren: Efficient Processing of Interactive Relational Data Base Queries expressed in Logic. VLDB 1981: 272-281

[Woods 1967]

...

[Yannakakis and Papadimitriou 1982]

Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41(1982)

[Yokota et al. 1983]

Haruo Yokota, Susumu Kunifuji, Takeo Kakuta, Nobuyoshi Miyazaki, Shigeki Shibayama, Kunio Murakami: An Enhanced Inference Mechanism for Generating Relational Algebra Queries. PODS 1984: 229-238

[Zaniolo 1976]

...

[Zaniolo 1981]

...

[Zloof 1977]

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