Codd's theorem

Codd's theorem states that relational algebra and the domain-independent relational calculus 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.

The theorem is named after Edgar F. Codd, the father of the relational model for database management.

The domain independent relational calculus 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 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.

Codd's Theorem is notable since it establishes the equivalence of two syntactically quite dissimilar languages: relational algebra is a variable-free language, while relational calculus is a logical language with variables and quantification.

Relational calculus is essentially equivalent to first-order logic,[1] and indeed, Codd's Theorem had been known to logicians since the late 1940s.[2][3]

Query languages that are equivalent in expressive power to relational algebra were called relationally complete 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 aggregations (counting tuples, or summing up values occurring in tuples, which are operations expressible in SQL but not in relational algebra) and computing the transitive closure of a graph given by its binary edge relation (see also expressive power). Codd's theorem also doesn't consider SQL nulls and the three-valued logic they entail; the logical treatment of nulls remains mired in controversy.[4] Additionally, SQL has multiset semantics as allowing duplicate rows. Nevertheless, relational completeness constitutes an important yardstick by which the expressive power of query languages can be compared.

Notes

  1. ^ Abiteboul, Serge; Hull, Richard B.; Vianu, Victor (1995). Foundations of Databases. Addison-Wesley. ISBN 0-201-53771-0.
  2. ^ Chin, L. H.; Tarski, A. (1948). "Remarks on Projective Algebras". Bulletin of the American Mathematical Society. 54 (1): 80–81. doi:10.1090/S0002-9904-1948-08948-0.
  3. ^ Tarski, A.; Thompson, F. B. (1952). "Some General Properties of Cylindric Algebras". Bulletin of the American Mathematical Society. 58 (1): 65. doi:10.1090/S0002-9904-1952-09549-5.
  4. ^ For recent work extending Codd's theorem in this direction see Franconi, Enrico; Tessaris, Sergio (2012). "On the Logic of SQL Nulls" (PDF). Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27–30, 2012: 114–128.

References

Read other articles:

Moto2 musim 2012

Grand Prix Sepeda Motor F.I.M. musim 2012 Sebelum: 2011 Sesudah: 2013 MotoGP musim 2012Moto3 musim 2012 Marc Márquez menjadi juara dunia Moto2. Kejuaraan Dunia FIM Moto2 2012 adalah bagian dari musim Kejuaraan Dunia F.I.M. Road Racing ke-64. Stefan Bradl adalah juara bertahan, tetapi tidak bertanding di musim ini karena dia bergabung dengan MotoGP bersama LCR Honda.[1] Ringkasan Musim Marc Márquez memenangkan gelar kejuaraan Moto2 setelah pertempuran sepanjang musim dengan sesama p...

 

 

List of Jewish American mobsters

Main article: Jewish-American organized crime This is a list of Jewish American mobsters and organized crime figures, ranging from the late 19th century to the present day. Name Portrait Life Years active Notes References Hyman Abrams No image available 1920s–1960s Lieutenant of Boston Mobster Charles Solomon during Prohibition. Later financed syndicate Las Vegas casinos with Meyer Lansky, Carl Cohen and Jack Entratter during the 1950s and 1960s. [1][2] Hyman Amberg No imag...

 

 

Yehiel De-Nur

Pour les articles homonymes, voir Dinur. Yehiel De-NurYehiel Dinur et son épouse en 1959.BiographieNaissance 16 mai 1909Sosnowiec (Ujezd będziński (d), Gouvernement de Piotrków, Empire russe)Décès 17 juillet 2001 (à 92 ans)Tel AvivSépulture Cimetière YarkonNoms de naissance יחיאל פיינער, Jechiel FajnerPseudonymes ק. צטניק, קרול צטינסקיNationalités israéliennepolonaiseActivité ÉcrivainPériode d'activité à partir de 1946Enfant Даниэлла (...

تجربة جيلي كلين في محطة الراديو عام 2006

جزء من سلسلة عنرهاب الإسلام قضايا اضطهاد المسلمين الإسلاموفوبيا في وسائل الإعلام الطيران بينما مسلم Airport racial profiling in the United States الصور النمطية للعرب والمسلمين في الولايات المتحدة Islamic scarf controversy in France Head rag tax Minaret controversy in Switzerland مكافحة الجهاد أورابيا تدنيس القرآن الحالة حسب ال...

 

 

Mausoleum

Mausoleum tua di Makam Husain bin Ali di Karbala, Irak. Taj Mahal, di Agra, India adalah mausoleum paling terkenal dan paling difoto di dunia. Mausoleum Jinnah di Karachi, Pakistan. mausoleum Habib Burquibah di Monastir, Tunisia. Istana Matahari Kumsusan, mausoleum Kim Il-sung dan Kim Jong-il di Pyongyang, Korea Utara. Bagian dalam Spring Valley Mausoleum di Minnesota, terdaftar di National Register of Historic Places. Percival Lowell - Mausoleum 2013 at the Observatorium Lowell di Flagstaff,...

 

 

Aktor Utama Terbaik Festival Film Wartawan Indonesia

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Aktor Utama Terbaik Festival Film Wartawan Indonesia – berita · surat kabar · buku · cendekiawan · JSTOR Penghargaan FFWI Aktor Utama Terbaik merupakan salah satu kategori yang diberikan pada ajang pengh...

Efek Droste

Sebuah bentuk visual dari rekursi yang dikenal dengan Efek Droste Efek Droste (pelafalan dalam bahasa Belanda: [drɔstə]), dikenal juga dalam seni sebagai mise en abyme, adalah sebuah istilah yang berasal dari bahasa Belanda yang mengacu kepada gambar rekursi.[1] Gambar yang bercirikan efek Droste memuat gambar yang sama dengan ukuran yang lebih kecil yang berada di posisi yang realistik. Gambar yang berukuran lebih kecil ini kemudian memuat gambar yang sama dengan ukuran yan...

 

 

趙家驤

追晉陸軍二級上將趙家驤將軍个人资料出生1910年 大清河南省衛輝府汲縣逝世1958年8月23日(1958歲—08—23)（47—48歲） † 中華民國福建省金門縣国籍 中華民國政党 中國國民黨获奖 青天白日勳章（追贈）军事背景效忠 中華民國服役 國民革命軍 中華民國陸軍服役时间1924年－1958年军衔 二級上將 （追晉）部队四十七師指挥東北剿匪總司令部參謀長陸軍�...

 

 

Kedutaan Besar Republik Indonesia di Yangon

Kedutaan Besar Republik Indonesia di YangonKoordinat16°47′23″N 96°08′31″E / 16.78973°N 96.142006°E / 16.78973; 96.142006Lokasi Yangon, MyanmarAlamatNo. 100 Pyiudaungsu Yeiktha Road, Dagon TownshipYangon, MyanmarYurisdiksi MyanmarSitus webkemlu.go.id/yangon/id Kedutaan Besar Republik Indonesia di Yangon (KBRI Yangon) adalah misi diplomatik Republik Indonesia untuk Republik Persatuan Myanmar.[1] Daftar duta besar Artikel utama: Daftar Duta Besar ...

Heineken Terbuka 2011

Heineken Open 2011Tanggal10 Januari – 15 JanuariEdisike-36JuaraTunggal David FerrerGanda Marcel Granollers / Tommy Robredo ← 2010 ·Heineken Open· 2012 → Heineken Open 2011 adalah turnamen tenis yang dimainkan di permukaan keras terbuka. Turnamen ini merupakan edisi ke-36 dari penyelenggaraan Heineken Open, dan merupakan bagian dari seri 250 ATP World Tour[1] yang juga merupakan bagian dari ATP World Tour musim 2011. Turnamen ini diselenggarakan di A...

 

 

Climate of Texas

Overview of the climate of the U.S. state of Texas Köppen climate types of Texas, using 1991-2020 c. This image of Texas, obtained by astronauts aboard NASA's Gemini 4 spacecraft, shows a large dark swath attributed to rainfall. Texas' weather varies widely, from arid in the west to humid in the east. The huge expanse of Texas encompasses several regions with distinctly different climates: Northern Plains, Trans-Pecos Region, Texas Hill Country, Piney Woods, and South Texas. Generally speak...

 

 

Menas of Constantinople

Ecumenical Patriarch of Constantinople in the sixth-century This article is about the sixth-century patriarch. For other saints with the same name, see Saint Menas (disambiguation). SaintMenas of ConstantinoplePatriarch of ConstantinopleDied25 August 552Venerated inEastern Orthodox ChurchRoman Catholic ChurchFeast25 AugustControversyThree-Chapter Controversy Menas (also Minas; Ancient Greek: Μηνᾶς; died 25 August 552), considered a saint in the Calcedonian affirming church and by e...

Salat Subuh

Bagian dari seriIslam Rukun Iman Keesaan Allah Malaikat Kitab-kitab Allah Nabi dan Rasul Allah Hari Kiamat Qada dan Qadar Rukun Islam Syahadat Salat Zakat Puasa Haji Sumber hukum Islam al-Qur'an Sunnah (Hadis, Sirah) Tafsir Akidah Fikih Syariat Sejarah Garis waktu Muhammad Ahlulbait Sahabat Nabi Khulafaur Rasyidin Khalifah Imamah Ilmu pengetahuan Islam abad pertengahan Penyebaran Islam Penerus Muhammad Budaya dan masyarakat Akademik Akhlak Anak-anak Dakwah Demografi Ekonomi Feminisme Filsafat...

 

 

Ghapama

Armenian stuffed pumpkin dish This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ghapama – news · newspapers · books · scholar · JSTOR (October 2015) (Learn how and when to remove this message) GhapamaTraditional ghapama, cut and ready to serveTypeStewPlace of originArmeniaMain ingredientsPumpkin, rice, dried f...

 

 

Gereja Duta Injil

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Gereja Duta Injil – berita · surat kabar · buku · cendekiawan · JSTORArtikel ini berisi konten yang ditulis dengan gaya sebuah iklan. Bantulah memperbaiki artikel ini dengan menghapus konten yang diangga...

Langekare

Island in Estonia Map showing Langekare Island Langekare is a small, uninhabited Baltic Sea island belonging to the country of Estonia. Its coordinates are 58°48′21″N 23°09′03″E / 58.80583°N 23.15083°E / 58.80583; 23.15083 [1] Langekare is a 1.2-hectare (3.0-acre) island lying off the eastern coast off the larger Estonian island of Hiiumaa and is administered by Pühalepa Parish, Hiiu County. Along with a number of other small islands and islets, it...

 

 

TMNT (video game)

2007 video game This article is about the cross-platform videogame. For the Game Boy Advance version of the game, see TMNT (Game Boy Advance video game). For other uses, see Teenage Mutant Ninja Turtles (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: TMNT video game – news · newspapers · books...

 

 

Live at Fenway Park

This article is about the Jimmy Buffett album. For the Dave Matthews Band album, see Live Trax Vol. 6. 2005 live album by Jimmy BuffettLive at Fenway ParkLive album by Jimmy BuffettReleasedNovember 15, 2005RecordedFenway Park ballpark, Boston, Massachusetts (10 and September 12, 2004)GenreCountry rockGulf and WesternLabelMailboat2115 (US, 2 CDs + 1 DVD)ProducerMichael Utley Professional ratingsReview scoresSourceRatingAllmusic[1] Live at Fenway Park is a live album by American...

NBC Sports

Division of American broadcast network NBC This article is about the sports division of NBCUniversal. For the former cable channel, see NBCSN. For sports on USA Network produced by NBC, see NBC Sports on USA Network. NBC SportsLaunchedMay 17, 1939; 85 years ago (1939-05-17)[1]Division ofNBCCountry of originUnited StatesKey peopleRichard Cordella (President, NBC Sports)HeadquartersStamford, ConnecticutMajor broadcasting contracts NFL (Sunday Night Football) Olympic ga...

 

 

Philadelphian cricket team

American cricket team This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Philadelphian cricket team – news · newspapers · books · scholar · JSTOR (May 2017) Philadelphia1884 squad of the Philadelphian cricket team as depicted in the Illustrated London NewsTeam informationFounded1878Last matchJune 28, ...