Using Semi-Joins to Solve Relational Queries

Journal of the ACMPublished 1 January 1981Open access

Philip A. Bernstein, Dah-Ming W. Chiu

DOI10.1145/322234.322238

Source URL

Citations463

SJR quartileQ1

SJR score2.25

SNIP3.16

View PDF

TL;DR

The exact class of relational queries that can be solved using semi-joins is shown and it is shown that queries outside of this class may not even be partially solvable using "short" semi-join programs.

Abstract

article Free Access Share on Using Semi-Joins to Solve Relational Queries Authors: Philip A. Bernstein Aiken Computation Laboratory, Harvard University, Cambridge, Massachusetts Aiken Computation Laboratory, Harvard University, Cambridge, MassachusettsView Profile , Dah-Ming W. Chiu Pierce Hall, Harvard University, Cambridge, Massachusetts Pierce Hall, Harvard University, Cambridge, MassachusettsView Profile Authors Info & Claims Journal of the ACMVolume 28Issue 1Jan. 1981 pp 25–40https://doi.org/10.1145/322234.322238Published:01 January 1981Publication History 392citation1,908DownloadsMetricsTotal Citations392Total Downloads1,908Last 12 Months264Last 6 weeks89 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Keywords

Computer Science

The Design and Analysis of Computer Algorithms

9,456 Citations1974Alfred V. Aho, John E. Hopcroft

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.

Communications of the ACMA relational model of data for large shared data banks

5,238 Citations1970E. F. Codd

A model based on n-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced and certain operations on relations are discussed and applied to the problems of redundancy and consistency in the user's model.

View PDF

Optimal implementation of conjunctive queries in relational data bases

1,237 Citations1977Ashok K. Chandra, Philip M. Merlin

It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal.

View PDF

IBM Journal of Research and DevelopmentSEQUEL 2: A Unified Approach to Data Definition, Manipulation, and Control

521 Citations1976Donald D. Chamberlin, M. M. Astrahan +6 more

SEQUEL 2 is a relational data language that provides a consistent, English keyword-oriented set of facilities for query, data definition, data manipulation, and datac ontrol.

ACM Transactions on Database SystemsDecomposition—a strategy for query processing

387 Citations1976Eugene Wong, Karel Youssefi

Strategy for processing multivariable queries in the database management system INGRES is considered, and algorithms for reduction and for choosing the variable to be substituted are given.

View PDF

SIAM Journal on ComputingEquivalences among Relational Expressions

364 Citations1979A. V. Aho, Yehoshua Sagiv +1 more

A polynomial time algorithm is presented for the equivalences of tableaux that correspond to an important subset of expressions, although the equivalence problem is shown to be NP-complete under slightly more general circumstances.

Communications of the ACMOptimizing the performance of a relational algebra database interface

214 Citations1975John Miles Smith, Philip Yen-Tang Chang

An approach for implementing a “smart” interface to support a relational view of data is proposed to employ automatic programming techniques so that the interface analyzes and efficiently refines the high level query specification supplied by the user.

View PDF

Very Large Data BasesA survey of research and development in distributed database management

102 Citations1977James B. Rothnie, Nathan Goodman

An overview of several key technical problems that must be overcome in developing general purpose distributed database management systems is presented, and current r&d efforts aimed at overcoming these problems are surveyed.

View PDF

ACM Transactions on Database SystemsPerformance evaluation of a relational associative processor

94 Citations1977Esen A. Ozkarahan, S. A. Schuster +1 more

The relational operations provided by the RAP hardware are described, and a representative approach to providing the same relational operations with conventional software and hardware is devised.

Evaluating inter-entry retrieval expressions in a relational data base management system

21 Citations1975James B. Rothnie

This paper will describe an approach to solving one of the key implementation problems of the relational model of data base management, embodied in an experimental system called DAMAS developed at the Massachusetts Institute of Technology.