Name: Foundations of databases
ISBN: 9780201537710

Foundations of databases

Over the past two decades, the theory concerning the logical level of database management systems has matured and become an elegant and robust piece of science. Foundations of Databases presents indepth coverage of this theory and surveys several emerging topics. Written by three leading researchers, this advanced text presents a unifying and contemporary perspective on the field. A major effort in writing the book has been to highlight the intuitions behind the theoretical development.

What Hacker News says

janmNov 2008

Transaction Processing: Concepts and Techniques (Jim Gray & Andreas Reuter) isn't just one of the best database textbooks, it is one of the best computer science textbooks. It is an Important Work.

On the other books, it depends on what you want. Alternatives to Date include Jeffrey Ullman, "Principles of Database and knowledge-base Systems" and "Foundations of Databases" by Abiteboul, Hull and Vianu.

As an introductory book, I like Database: Principles, Programming, Performance by Patrick O'Neil.

For more on transaction processing, as well as Jim Gray there is Philip Bernstein, eg "Principles of Transaction Processing".

Following the references is a lot of fun; see where you end up.

thread

nyrikkiJul 2025

From [0] which is Codd justifying it explicitly.

> The term relation is used here in its accepted mathematical sense. Given sets S_1, S_2, ..., S_n (not necessarily distinct), R is a relation on these n sets if it is a set of ntuples each of which has its first element from S_1, its second element from S_z , and so on.’ We shall refer to S_i as the jth domain of R.

Note the "(not necessarily distinct)" part and how he uses a table to describe it on the same page.

From what is called the "Alice book" Foundations of Databases - Abiteboul, Hull, Vianu[1] the seminal textbook in database theory.

> In the 1970s, Codd’s relational model revolutionized the field. In this model, humans view the data as organized in relations (tables), and more “declarative” languages are provided for data access.

Unfortunately I can't find chapter 3, where the relational model is described in detail online.

But for more concrete SQL as defined in ISO/IEC 9075-2:1999 (E)[2]....calls them "tables"

Outside of didactic simplifications or domain specific conventions I am not finding anything.

I could be convinced otherwise...but as every real world practical RDBMS has to impose order of often multple tables to scale, through logs, cache etc...and as what everyone agrees is SQL has to support various transaction isolation levels which ensures that on a concrete implementation detail, that rows aren't unique, but that the special case of a membership function, expressly being an 'element' is supported in them all. Plus you only get DISTINCT with a candidate key, and by default SQL is using bags/multisets anyway...there is just to much undefined behavior with indistinct rows and so we avoid them but they are allowed.

In fact, while useful for teaching and day to day use, you are actually violating the axiom of pairing, which is also used to construct the singleton's in modern ZFC.

In fact AC is called the well-ordering axiom by some, expressly because it allows it.

I think you are possibly confusing the absence of ordering from the users perspective?

Either way I have provided actual cites and would appreciate the same, because I would rather learn where I am wrong than prove myself right.

[0] https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf [1] http://webdam.inria.fr/Alice/pdfs/Chapter-1.pdf [2] https://web.cecs.pdx.edu/~len/sql1999.pdf

thread

kragenJun 2025

Datalog always supports N-ary relations! It's not an extension.

The Wikipedia article recommends https://search.worldcat.org/title/30546436 "Foundations of Databases" by Abiteboul, Hull, and Vianu, from 01995, and https://archive.org/details/logicdatabases0000symp/page/n5/m... "Logic and Data Bases [sic]" by Gallaire and Minker from 01978. Some poking at Google Scholar also turns up, in rough order of how promising they look (without having read them that I can recall):

https://dl.acm.org/doi/pdf/10.1145/6012.15399 "Magic Sets and Other Strange Ways to Implement Logic Programs", Bancilhon, Maier, Sagiv, & Ullman (yes, that Ullman), 01985 (15 pp.)

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d... "What You Always Wanted to Know About Datalog (And Never Dared to Ask)", Ceri, Gottlob, and Tanca, 01989 (21 pp.)

https://web.cecs.pdx.edu/harry/earley/datalog.pdf "Optimizations to Earley Deduction for DATALOG Programs", Porter, 01985 (12 pp.)

https://dl.acm.org/doi/pdf/10.1145/308386.308420 "Optimizing Existential Datalog Queries", Ramakrishhnan, Beers, & Krishnamurthy, 01988 (14 pp.)

https://dl.acm.org/doi/pdf/10.1145/298514.298542 "On the Expressive Power of Datalog: Tools and a Case Study", Kolaitis & Vardi, 01990

https://dl.acm.org/doi/pdf/10.1145/93605.98724 "A Framework for the Parallel Processing of Datalog Queries", Ganguly, Silberschatz, & Tsur, 01990

https://deepblue.lib.umich.edu/bitstream/handle/2027.42/3116... "Datalog vs First-Order Logic", Ajtai & Gurevich, 01993

https://lat.inf.tu-dresden.de/teaching/ss2014/Seminar/Papers... "Equivalence of Datalog Queries is Undecidable", Shmueli, 01993

It also turned up "Portability of Syntax and Semantics in Datalog" which turned out to be an unrelated NLP AI system called Datalog.

Bancilhon, Maier, Sagiv, & Ullman give as their reference for Datalog "Maier and Warren [1985]", which turns out to be "D. Maier and D. S. Warren [1985]. Introduction to Logic Programming, unpublished memorandum, Oregon Graduate Center," which I can't find a copy of easily. But given that Maier is a shared author we can probably trust their summary of what Datalog is.

Ceri, Gottlob, and Tanca reference "[120], [15], [16]," which are respectively:

J. D. Ullman, “Implementation of logic query languages for databases,” ACM Trans. Database Syst., vol. 10, no. 3, 1985

F. Bancilhon and R. Ramakrishnan, “An amateur’s introduction to recursive query processing,” in Proc. ACM-SIGMOD Conf., May 1986.

-, “Performance evaluation of data intensive logic programs,” in Foundations of Deductive Databases and Logic Programming, J. Minker, Ed. Washington, DC, 1986.

The Ullman paper is https://dl.acm.org/doi/pdf/10.1145/3979.3980, "Implementation of Logical Query Languages for Databases", ACM Transactions on Database Systems, Vol. 10, No. 3, September 1985, Pages 289-321 (33 pp.). Ceri, Gottlob, and Tanca screwed up the title. https://dl.acm.org/doi/10.1145/971699.320000 probably isn't it; the journal name, volume number, and issue number don't match, although it's the right author and year. That seems to be the oldest published Datalog paper, although the word "Datalog" hadn't been invented yet and doesn't appear in the paper.

I think I'm going to read the Bancilhon, Maier, Sagiv, & Ullman paper first, because it's shorter and has a more readable-sounding title, and then maybe Ceri, Gottlob, and Tanca, and then maybe Ullman, and then maybe a relevant chapter or two of Gallaire and Minker.

thread

mmarxMay 2019

> The thing with "Datalog" is that it is really a level of functionality that is implemented in various database query systems and not a well-defined language in and of itself. 15 years ago I remembered searching for papers about it and did not find so many, now it is hot.

Datalog as a language is really just one very specific form of rules (first-order horn implications containing just constants and variables, where each variable in the conclusion also occurs in the premise), and every Datalog program (i.e., every set of rules) is guaranteed to have a finite, universal model.

[0] Ceri, Gottlob, Tanca. (1989) What you always wanted to know about Datalog (and never dared to ask). IEEE TRANSACTIONS KNOWLEDGE AND DATA ENGINEERING. [1] Abiteboul, Hull, Vianu. (1994) Foundations of Databases: The Logical Level. Pearson.

thread

cgrand-netOct 2018

Datalog is a subset of Prolog syntax and logical semantics, but not of its operational semantics, so in practice the link is tenuous.

I like the honest words of Serge Abiteboul (co-author of Foundations of Databases http://webdam.inria.fr/Alice/) on this topic:

This is back to the advantages of “declarative programming”. The first scam was Prolog: The language is not really declarative. The second scam was Datalog: It is declarative, but there is not much you can do with it.

Datalog is simple and beautiful – Horn clauses. We theory guys had a ball with it. There were beautiful results to obtain even at the cost of further simplifications (e.g., monadic to be able to decide containment). But the scam is that if you want to do anything serious beyond your stupid positive first-order queries, you need more.

There was no fix that I know of for Prolog. There were fixes for Datalog. Extend the language. And this was done during the last 30 years

(http://abiteboul.blogspot.com/2012/08/datalog-revival-for-da...)

thread

cgagJan 2014

This looks cool, I'll have to check this book out. For people who are interested, this is from Foundations of Databases (http://www.amazon.com/Foundations-Databases-The-Logical-Leve...) and is available for free at the root url from jamii's link.

edit: realized it's a referral link, it's not mine, it's because I got there through Rich Hickey's list of books that influenced clojure: http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH

thread