49:
queries are precisely those relational calculus queries that are invariant under choosing domains of values beyond those appearing in the database itself. That is, queries that may return different results for different domains are excluded. An example of such a forbidden query is the query "select
50:
all tuples other than those occurring in relation R", where R is a relation in the database. Assuming different domains, i.e., sets of atomic data items from which tuples can be constructed, this query returns different results and thus is clearly not domain independent.
71:
by Codd. By Codd's
Theorem, this includes relational calculus. Relational completeness clearly does not imply that any interesting database query can be expressed in relationally complete languages. Well-known examples of inexpressible queries include simple
30:
queries, two well-known foundational query languages for the relational model, are precisely equivalent in expressive power. That is, a database query can be formulated in one language if and only if it can be expressed in the other.
96:
semantics as allowing duplicate rows. Nevertheless, relational completeness constitutes an important yardstick by which the expressive power of query languages can be compared.
353:
256:
117:
76:(counting tuples, or summing up values occurring in tuples, which are operations expressible in SQL but not in relational algebra) and computing the
64:
Relational calculus is essentially equivalent to first-order logic, and indeed, Codd's
Theorem had been known to logicians since the late 1940s.
313:
163:
235:
Proceedings of the 6th
Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27–30, 2012
290:. Proceedings of 6th Courant Computer Science Symposium (May 24–25, 1971: New York, N.Y.). Prentice-Hall. pp. 65–98.
81:
295:
276:
137:
53:
Codd's
Theorem is notable since it establishes the equivalence of two syntactically quite dissimilar languages:
348:
320:
58:
92:
they entail; the logical treatment of nulls remains mired in controversy. Additionally, SQL has
57:
is a variable-free language, while relational calculus is a logical language with variables and
286:
Codd, E. F. (1972). "Relational
Completeness of Data Base Sublanguages". In Rustin, R. (ed.).
67:
Query languages that are equivalent in expressive power to relational algebra were called
8:
46:
27:
265:
126:
89:
77:
73:
54:
23:
291:
272:
133:
210:
193:
177:
158:
205:
172:
39:
252:
113:
342:
154:
35:
260:
121:
319:. Institute of Logic and Computation, DBAI Group, TU Wien. Archived from
227:
85:
93:
224:
For recent work extending Codd's theorem in this direction see
16:
Theorem of expressive equivalence between relational languages
80:
of a graph given by its binary edge relation (see also
264:
251:
125:
112:
340:
225:
194:"Some General Properties of Cylindric Algebras"
191:
198:Bulletin of the American Mathematical Society
164:Bulletin of the American Mathematical Society
226:Franconi, Enrico; Tessaris, Sergio (2012).
354:Theorems in the foundations of mathematics
152:
209:
176:
84:). Codd's theorem also doesn't consider
311:
341:
314:"Database Theory: 3. Codd's Theorem"
312:Pichler, Reinhard (March 20, 2018).
285:
192:Tarski, A.; Thompson, F. B. (1952).
13:
14:
365:
305:
159:"Remarks on Projective Algebras"
211:10.1090/S0002-9904-1952-09549-5
178:10.1090/S0002-9904-1948-08948-0
218:
185:
146:
106:
1:
245:
7:
228:"On the Logic of SQL Nulls"
34:The theorem is named after
26:and the domain-independent
10:
370:
42:for database management.
267:Foundations of Databases
128:Foundations of Databases
99:
45:The domain independent
69:relationally complete
38:, the father of the
47:relational calculus
28:relational calculus
326:on August 22, 2020
271:. Addison-Wesley.
132:. Addison-Wesley.
90:three-valued logic
78:transitive closure
55:relational algebra
24:relational algebra
288:Data Base Systems
361:
349:Relational model
335:
333:
331:
325:
318:
301:
282:
270:
257:Hull, Richard B.
253:Abiteboul, Serge
239:
238:
232:
222:
216:
215:
213:
189:
183:
182:
180:
150:
144:
143:
131:
118:Hull, Richard B.
114:Abiteboul, Serge
110:
82:expressive power
40:relational model
369:
368:
364:
363:
362:
360:
359:
358:
339:
338:
329:
327:
323:
316:
308:
298:
279:
248:
243:
242:
230:
223:
219:
190:
186:
151:
147:
140:
111:
107:
102:
17:
12:
11:
5:
367:
357:
356:
351:
337:
336:
307:
306:External links
304:
303:
302:
296:
283:
277:
247:
244:
241:
240:
217:
184:
145:
138:
104:
103:
101:
98:
59:quantification
20:Codd's theorem
15:
9:
6:
4:
3:
2:
366:
355:
352:
350:
347:
346:
344:
322:
315:
310:
309:
299:
297:0-13-196741-X
293:
289:
284:
280:
278:0-201-53771-0
274:
269:
268:
262:
261:Vianu, Victor
258:
254:
250:
249:
236:
229:
221:
212:
207:
203:
199:
195:
188:
179:
174:
170:
166:
165:
160:
156:
153:Chin, L. H.;
149:
141:
139:0-201-53771-0
135:
130:
129:
123:
122:Vianu, Victor
119:
115:
109:
105:
97:
95:
91:
87:
83:
79:
75:
70:
65:
62:
60:
56:
51:
48:
43:
41:
37:
36:Edgar F. Codd
32:
29:
25:
21:
328:. Retrieved
321:the original
287:
266:
234:
220:
201:
197:
187:
171:(1): 80–81.
168:
162:
148:
127:
108:
74:aggregations
68:
66:
63:
52:
44:
33:
22:states that
19:
18:
343:Categories
246:References
237:: 114–128.
155:Tarski, A.
330:August 8,
204:(1): 65.
86:SQL nulls
263:(1995).
157:(1948).
124:(1995).
94:multiset
88:and the
294:
275:
136:
324:(PDF)
317:(PDF)
231:(PDF)
100:Notes
332:2019
292:ISBN
273:ISBN
134:ISBN
206:doi
173:doi
345::
259:;
255:;
233:.
202:58
200:.
196:.
169:54
167:.
161:.
120:;
116:;
61:.
334:.
300:.
281:.
214:.
208::
181:.
175::
142:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.