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. J. ACM 47(4): 644-680(2000)
  Electronic Edition BibTeX

Volume 46, 1999

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

Volume 45, 1998

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

Volume 44, 1997

• Serge Abiteboul, Moshe Y. Vardi, Victor Vianu:
  Fixpoint logics, relational machines, and computational complexity. J. ACM 44(1): 30-56(1997)
  Electronic Edition BibTeX
• Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens:
  On the completeness of object-creating database transformation languages. J. ACM 44(2): 272-319(1997)
  Electronic Edition BibTeX

Volume 43, 1996

• Sherry Marcus, V. S. Subrahmanian:
  Foundations of Multimedia Database Systems. J. ACM 43(3): 474-523(1996)
  Electronic Edition BibTeX

Volume 42, 1995

• Ke Wang, Weining Zhang, Siu-Cheung Chau:
  Decomposition of Magic Rewriting. J. ACM 42(2): 329-381(1995)
  Electronic Edition BibTeX
• Michael Kifer, Georg Lausen, James Wu:
  Logical Foundations of Object-Oriented and Frame-Based Languages. J. ACM 42(4): 741-843(1995)
  Electronic Edition BibTeX

Volume 41, 1994

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

Volume 36, 1989

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

Volume 35, 1988

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

Volume 34, 1987

• Victor Vianu:
  Dynamic functional dependencies and database aging. J. ACM 34(1): 28-59(1987)
  Electronic Edition BibTeX
• Edward P. F. Chan, Alberto O. Mendelzon:
  Answering queries on embedded-complete database schemes. J. ACM 34(2): 349-375(1987)
  Electronic Edition BibTeX
• Catriel Beeri, Michael Kifer:
  A theory of intersection anomalies in relational database schemes. J. ACM 34(3): 544-577(1987)
  Electronic Edition BibTeX

Volume 33, 1986

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

Volume 32, 1985

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

Volume 31, 1984

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

Volume 30, 1983

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

Volume 29, 1982

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

Volume 28, 1981

• Philip A. Bernstein, Dah-Ming W. Chiu:
  Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981)
  Electronic Edition BibTeX
• Witold Lipski Jr.:
  On Databases with Incomplete Information. J. ACM 28(1): 41-70(1981)
  Electronic Edition 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)
  Electronic Edition BibTeX
• David Maier, Yehoshua Sagiv, Mihalis Yannakakis:
  On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981)
  Electronic Edition BibTeX

Volume 27, 1980

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

Volume 26, 1979

• Alberto O. Mendelzon:
  On Axiomatizing Multivalued Dependencies in Relational Databases. J. ACM 26(1): 37-44(1979)
  Electronic Edition BibTeX
• Steven P. Reiss:
  Security in Databases: A Combinatorial Study. J. ACM 26(1): 45-57(1979)
  Electronic Edition BibTeX
• Christos H. Papadimitriou:
  The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979)
  Electronic Edition BibTeX

Volume 23, 1976

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

Volume 22, 1975

• Robert A. Kowalski:
  A Proof Procedure Using Connection Graphs. J. ACM 22(4): 572-595(1975)
  Electronic Edition BibTeX

Volume 20, 1973

• C. L. Liu, James W. Layland:
  Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM 20(1): 46-61(1973)
  Electronic Edition BibTeX

Volume 18, 1971

• Alfred V. Aho, Peter J. Denning, Jeffrey D. Ullman:
  Principles of Optimal Page Replacement. J. ACM 18(1): 80-93(1971)
  Electronic Edition BibTeX

Volume 17, 1970

• C. V. Ramamoorthy, K. Mani Chandy:
  Optimization of Memory Hierarchies in Multiprogrammed Systems. J. ACM 17(3): 426-445(1970)
  Electronic Edition BibTeX

Volume 16, 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)
  Electronic Edition BibTeX
• Sakti P. Ghosh, Michael E. Senko:
  File Organization: On the Selection of Random Access Index Points for Sequential Files. J. ACM 16(1): 569-579(1969)
  Electronic Edition BibTeX

Volume 15, 1968

• Donald R. Morrison:
  PATRICIA - Practical Algorithm To Retrieve Information Coded in Alphanumeric. J. ACM 15(4): 514-534(1968)
  Electronic Edition BibTeX
• Thomas C. Lowe:
  The Influence of Data Base Characteristics and Usage on Direct Access File Organization. J. ACM 15(4): 535-548(1968)
  Electronic Edition BibTeX

Volume 12, 1965

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

Volume 9, 1962

• Stephen Warshall:
  A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962)
  Electronic Edition BibTeX