ACM SIGMOD Anthology, Volume 5, Number 2: Selected Material from Journal of the ACM (JACM)

Volume 47, 2000

• 
  Michael Benedikt, Leonid Libkin:
  Relational queries over interpreted structures. 644-680

Volume 46, 1999

• 
  Paolo Ferragina, Roberto Grossi:
  The String B-tree: A New Data Structure for String Search in External Memory and Its Applications. 236-280
• 
  Jon M. Kleinberg:
  Authoritative Sources in a Hyperlinked Environment. 604-632
• 
  Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum:
  An Optimality Proof of the LRU-K Page Replacement Algorithm. 92-112

Volume 45, 1998

• 
  Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong:
  Relational Expressive Power of Constraint Query Languages. 1-34
• 
  Michael Kifer:
  On the Decidability and Axiomatization of Query Finiteness in Deductive Databases. 588-633
• 
  Serge Abiteboul, Paris C. Kanellakis:
  Object Identity as a Query Language Primitive. 798-842
• 
  Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu:
  An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions. 891-923

Volume 44, 1997

• 
  Serge Abiteboul, Moshe Y. Vardi, Victor Vianu:
  Fixpoint logics, relational machines, and computational complexity. 30-56
• 
  Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens:
  On the completeness of object-creating database transformation languages. 272-319

Volume 43, 1996

• 
  Sherry Marcus, V. S. Subrahmanian:
  Foundations of Multimedia Database Systems. 474-523

Volume 42, 1995

• 
  Ke Wang, Weining Zhang, Siu-Cheung Chau:
  Decomposition of Magic Rewriting. 329-381
• 
  Michael Kifer, Georg Lausen, James Wu:
  Logical Foundations of Object-Oriented and Frame-Based Languages. 741-843

Volume 41, 1994

• 
  Jeffrey F. Naughton, Raghu Ramakrishnan:
  How to Forget the Past Without Repeating It. 1151-1177
• 
  Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian:
  Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases. 1178-1215
• 
  Kenneth A. Ross:
  Modular Stratification and Magic Sets for Datalog Programs with Negation. 1216-1266

Volume 36, 1989

• 
  William McCune, Lawrence J. Henschen:
  Maintaining state constraints in relational databases: a proof theoretic basis. 46-68
• 
  Catriel Beeri, Philip A. Bernstein, Nathan Goodman:
  A model for concurrency in nested transactions systems. 230-269
• 
  Serge Abiteboul, Victor Vianu:
  A transaction-based approach to relational database specification. 758-789
• 
  Marc Gyssens, Jan Paredaens, Dirk Van Gucht:
  A uniform approach toward handling atomic and structured information in the nested relational database model. 790-825

Volume 35, 1988

• 
  Serge Abiteboul, Victor Vianu:
  Equivalence and optimization of relational transactions. 70-120
• 
  Vassos Hadzilacos:
  A theory of reliability in database systems. 121-145
• 
  Anthony C. Klug:
  On conjunctive queries containing inequalities. 146-160
• 
  Gaston H. Gonnet, Per-Åke Larson:
  External hashing with limited internal storage. 161-184
• 
  Jeffrey D. Ullman, Allen Van Gelder:
  Efficient tests for top-down termination of logical rules. 345-373

Volume 34, 1987

• 
  Victor Vianu:
  Dynamic functional dependencies and database aging. 28-59
• 
  Edward P. F. Chan, Alberto O. Mendelzon:
  Answering queries on embedded-complete database schemes. 349-375
• 
  Catriel Beeri, Michael Kifer:
  A theory of intersection anomalies in relational database schemes. 544-577

Volume 33, 1986

• 
  Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi:
  Notions of dependency satisfaction. 105-129
• 
  Raymond Reiter:
  A sound and sometimes complete query evaluation algorithm for relational databases with null values. 349-370
• 
  Catriel Beeri, Michael Kifer:
  Elimination of intersection anomalies from database schemes. 423-450
• 
  Seymour Ginsburg, Richard Hull:
  Sort sets in the relational model. 465-488

Volume 32, 1985

• 
  Serge Abiteboul:
  Disaggregations in Databases. 79-101
• 
  Gael N. Buckley, Abraham Silberschatz:
  Beyond Two-Phase Locking. 314-326
• 
  Michael J. Fischer, Nancy A. Lynch, Mike Paterson:
  Impossibility of Distributed Consensus with One Faulty Process. 374-382
• 
  Y. C. Tay, Rajan Suri, Nathan Goodman:
  A Mean Value Performance Model for Locking in Databases: The No-Waiting Case. 618-651
• 
  Domenico Saccà:
  Closures of Database Hypergraphs. 774-803
• 
  Hector Garcia-Molina, Daniel Barbará:
  How to Assign Votes in a Distributed System. 841-860

Volume 31, 1984

• 
  Catriel Beeri, Martin Dowd, Ronald Fagin, Richard Statman:
  On the Structure of Armstrong Relations for Functional Dependencies. 30-46
• 
  Lawrence J. Henschen, Shamim A. Naqvi:
  On compiling queries in recursive first-order databases. 47-85
• 
  Richard Hull:
  Finitely Specifiable Implicational Dependency Families. 210-226
• 
  Mihalis Yannakakis:
  Serializability by Locking. 227-244
• 
  Richard Hull, Chee-Keng Yap:
  The Format Model: A Theory of database Organization. 518-544
• 
  Michael L. Fredman, János Komlós, Endre Szemerédi:
  Storing a Sparse Table with 0(1) Worst Case Access Time. 538-544
• 
  Catriel Beeri, Moshe Y. Vardi:
  A Proof Procedure for Data Dependencies. 718-741
• 
  Stavros S. Cosmadakis, Christos H. Papadimitriou:
  Updates of Relational Views. 742-760
• 
  Tomasz Imielinski, Witold Lipski Jr.:
  Incomplete Information in Relational Databases. 761-791
• 
  Debasis Mitra, Peter J. Weinberger:
  Probabilistic Models of Database Locking: Solutions, Computational Algorithms, and Asymptotics. 855-878

Volume 30, 1983

• 
  Anthony C. Klug:
  Locking Expressions for Increased Database Concurrency. 36-54
• 
  Henry F. Korth:
  Locking Primitives in a Database System. 55-79
• 
  Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis:
  On the Desirability of Acyclic Database Schemes. 479-513
• 
  Ronald Fagin:
  Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. 514-550
• 
  Giorgio Ausiello, Alessandro D'Atri, Domenico Saccà:
  Graph Algorithms for Functional Dependency Manipulation. 752-766
• 
  Nathan Goodman, Oded Shmueli:
  Syntactic Characterization of Tree Database Schemas. 767-786
• 
  Zvi M. Kedem, Abraham Silberschatz:
  Locking Protocols: From Exclusive to Shared Locks. 787-804
• 
  Per-Åke Larson:
  Analysis of Uniform Hashing. 805-819

Volume 29, 1982

• 
  Yehoshua Sagiv, Scott F. Walecka:
  Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies. 103-117
• 
  Barry E. Jacobs:
  On Database Logic. 310-332
• 
  Y. Edmund Lien:
  On the Equivalence of Database Models. 333-362
• 
  Fereidoon Sadri, Jeffrey D. Ullman:
  Template Dependencies: A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization. 363-372
• 
  Edward Sciore:
  A Complete Axiomatization of Full Join Dependencies. 373-393
• 
  Ravi Sethi:
  Useless Actions Make a Difference: Strict Serializability of Database Updates. 394-403
• 
  Peter Honeyman:
  Testing satisfaction of functional dependencies. 668-677
• 
  Seymour Ginsburg, Sami Mohammed Zaiddan:
  Properties of functional-dependency families. 678-698
• 
  Anthony C. Klug:
  Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. 699-717
• 
  Mihalis Yannakakis:
  A Theory of Safe Locking Policies in Database Systems. 718-740
• 
  Krzysztof R. Apt, Maarten H. van Emden:
  Contributions to the Theory of Logic Programming. 841-862
• 
  Ronald Fagin:
  Horn clauses and database dependencies. 952-985
• 
  John Grant, Barry E. Jacobs:
  On the family of generalized dependency constraints. 986-997
• 
  Christos H. Papadimitriou:
  A theorem in database concurrency control. 998-1006

Volume 28, 1981

• 
  Philip A. Bernstein, Dah-Ming W. Chiu:
  Using Semi-Joins to Solve Relational Queries. 25-40
• 
  Witold Lipski Jr.:
  On Databases with Incomplete Information. 41-70
• 
  Yehoshua Sagiv, Claude Delobel, Douglas Stott Parker Jr., Ronald Fagin:
  An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic. 435-453
• 
  David Maier, Yehoshua Sagiv, Mihalis Yannakakis:
  On the Complexity of Testing Implications of Functional and Join Dependencies. 680-695

Volume 27, 1980

• 
  Abraham Silberschatz, Zvi M. Kedem:
  Consistency in Hierarchical Database Systems. 72-80
• 
  Marshall C. Pease, Robert E. Shostak, Leslie Lamport:
  Reaching Agreement in the Presence of Faults. 228-234
• 
  Raymond Reiter:
  Equality and Domain Closure in First-Order Databases. 235-249
• 
  Yehoshua Sagiv:
  An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic. 250-262
• 
  Yehoshua Sagiv, Mihalis Yannakakis:
  Equivalences Among Relational Expressions with the Union and Difference Operators. 633-655
• 
  David Maier:
  Minimum Covers in Relational Database Model. 664-674

Volume 26, 1979

• 
  Alberto O. Mendelzon:
  On Axiomatizing Multivalued Dependencies in Relational Databases. 37-44
• 
  Steven P. Reiss:
  Security in Databases: A Combinatorial Study. 45-57
• 
  Christos H. Papadimitriou:
  The serializability of concurrent database updates. 631-653

Volume 23, 1976

• 
  Edward M. McCreight:
  A Space-Economical Suffix Tree Construction Algorithm. 262-272
• 
  Mark J. Eisner, Dennis G. Severance:
  Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases. 619-635
• 
  Maarten H. van Emden, Robert A. Kowalski:
  The Semantics of Predicate Logic as a Programming Language. 733-742

Volume 22, 1975

• 
  Robert A. Kowalski:
  A Proof Procedure Using Connection Graphs. 572-595

Volume 20, 1973

• 
  C. L. Liu, James W. Layland:
  Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. 46-61

Volume 18, 1971

• 
  Alfred V. Aho, Peter J. Denning, Jeffrey D. Ullman:
  Principles of Optimal Page Replacement. 80-93

Volume 17, 1970

• 
  Chittoor V. Ramamoorthy, K. Mani Chandy:
  Optimization of Memory Hierarchies in Multiprogrammed Systems. 426-445

Volume 16, 1969

• 
  Robert A. Di Paola:
  The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. 324-327
• 
  Sakti P. Ghosh, Michael E. Senko:
  File Organization: On the Selection of Random Access Index Points for Sequential Files. 569-579

Volume 15, 1968

• 
  Donald R. Morrison:
  PATRICIA - Practical Algorithm To Retrieve Information Coded in Alphanumeric. 514-534
• 
  Thomas C. Lowe:
  The Influence of Data Base Characteristics and Usage on Direct Access File Organization. 535-548

Volume 12, 1965

• 
  John Alan Robinson:
  A Machine-Oriented Logic Based on the Resolution Principle. 23-41

Volume 9, 1962

• 
  Stephen Warshall:
  A Theorem on Boolean Matrices. 11-12