Abstract | ||
---|---|---|
This paper examines a number of programming primitives in query languages for relational databases. The basic framework is a language based on relational algebra, whose variables take relations as values. The primitives considered are (i) looping, (ii) counters, (iii) generic (or unranked) variables, (iv) equality, (v) bounded looping (which corresponds to counting the number of tuples in a relation), and (vi) isomorphism class (which corresponds to knowing the isomorphism class of the data base). A comparison diagram is given relating all combinations of these six primitives, and several of the resulting classes of queries are characterized by their complexity or algebraic properties. It is shown, for example, that equality cannot be simulated using all the other primitives, that generic variables (with loops) cannot be simulated with only ranked variables and all the other primitives, and that with bounded loops one can determine the isomorphism class of the database when generic variables are allowed, but not otherwise. |
Year | DOI | Venue |
---|---|---|
1981 | 10.1145/567532.567537 | POPL |
Keywords | Field | DocType |
isomorphism class,data base,algebraic property,bounded loop,database language,comparison diagram,relational databases,relational algebra,programming primitive,generic variable,bounded looping,basic framework,relational database,relation algebra,query language | Comparison diagram,Query language,Programming language,Ranking,Relational database,Tuple,Computer science,Theoretical computer science,Relational algebra,Isomorphism class,Bounded function | Conference |
ISBN | Citations | PageRank |
0-89791-029-X | 76 | 63.20 |
References | Authors | |
37 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ashok K. Chandra | 1 | 3116 | 1215.02 |