36

Original transactions: Insert record $r$. Update some field $f$ of $r$. Forward undo: Delete record $r$. Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.


12

To add to DylanSp's answer, trying to update a field in a non-existing record will fail, but the result will still be the expected result: record r does not exist. However, consider a situation where deletion of a record actually will fail: Insert Order O. Insert Orderline L. Let's assume, not unrealistically, that every OrderLine must be related to an ...


11

This insight was made at least as far back as 1886, by Alfred Kempe. In fact, he observed that any set of relationships (not just those that are already relations) can be captured as a binary relation. At the time this seems to have come as a shock to Charles Sanders Peirce, who had built his relation algebra on the idea that any relation can be captured ...


11

I've reread Herlihy and Wing many times over the past 15 years. It is a very difficult read. And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable. In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering ...


11

The largest 12 digit number in base 10 is $10^{12} - 1$. In general the largest $n$ position number in a base $b$ is $b^{n} - 1$. So in your case you need a base large enough that $b^{9} - 1 > 999,999,999,999$ $(10^{12} - 1).$ Solving for $b$: $$b^{9} - 1 > 10^{12} - 1$$ $$b^{9} > 10^{12}$$ $$b^{9/9} > 10^{12/9}$$ $$b > 10^{12/9}$$ $$b >...


8

A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set for the sort of operations we're talking about), but is most commonly used to implement a map (ditto for java.util.Map). So let's just look at maps for a moment. If you think about a linguistic dictionary, it's ordered by "word",...


7

Let's go by analogy: say you're going out for dinner. Put socks on. Put shoes on. Stand up. Walk to door. Then you get a phone call. Dinner plans cancelled. Take socks off. Take shoes off. Sit down. Walk away from door. Something goes wrong in there. You may trip and hurt yourself. Or more likely, you'll realize that some actions can't be undone ...


6

(1) Duplication When you create tables in a database, you may want to create duplication: CREATE TABLE user (name TEXT, id INTEGER); CREATE TABLE friends (name TEXT, friend_of_id INTEGER); Here you would duplicate the name of the user in both tables. That way when you display the list of friends, you do not have to access the user table to read the name. ...


6

Excellent question, and since you referred to us ("jOOQ developers", which I am - working for the company behind jOOQ), I feel qualified to give a partial answer. A bit of historic context first Since the very beginning of software, there had been: Theory (which is what "Computer Science", i.e. this Stack Exchange subsite is about) Practice (more like ...


6

Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is useful. However, bounding-volume hierarchy is a very general notion. When designing a bounding-volume hierarchy data structure in practice, it is extremely ...


5

Consider the design of concurrent, wait-free (or lock-free, which is weaker) data structures. In this scenario, linearizability is generally required, even though in some cases, performance and scalability can be improved by satisfying a weaker correctness condition. Whether an implementation satisfying such a weak condition is useful is usually application-...


5

About your definitions: The basic idea of Serializability ($\textsf{SR}$) is correct. However, it does not have to constrain itself on the your assumption that each (process) executes a transaction: Every process can issue as many transactions as they want. Your understanding of Linearizability ($\textsf{LR}$) is quite wrong. First, for both $\textsf{SR}$ ...


5

Use any kind of persistent/immutable (i.e., functional) tree-based data structure. The key is getting the locking right, as @Raphael pointed out in the comments. The nice thing about functional/persistent tree-based data structures, is that you get "snapshots" for free. Let's suppose you use a treap (randomized binary search tree) for your data structure. ...


4

This question is related to the very basics of database theory, finite model theory and logics. I would strongly suggest Abiteboul's book on Foundations of Databases, or Libkin's book on Finite Model Theory. Very roughly stated, a database is a collection of facts, and a query is a logical formula, which is used to specify certain patterns to be matched ...


4

Closure and cover are two completely different things. The closure of a set of attributes or a functional dependency $f$ is a set of relation schemes that can be implied by $f$. In order to find the closure, we can expand the FD or the set of attributes based on the given set of FDs by replacing each relation with the ones inferred by it. For example, $$X ...


4

Since you have a 1-1 relationship between DisasterEvent and People now, you can not distinguish any relation between People and Place. If several Places are related to a single DisasterEvent, all those places are related to the same instance of People. If you want to map the People affected by the Event at a Place, you should relate People to Place instead ...


4

See https://en.wikipedia.org/wiki/Blockchain_(database)#Decentralization, which states that "Every node in a decentralized system has a copy of the blockchain. This avoids the need to have a centralized database managed by a trusted third party." This is as true of 10 computers as it is of one. It's not about redundancy from this perspective, though that ...


4

This is right because transactions are built on top of each other and the outcome of a transaction is very much dependent on the situation before it was committed. Let's look at financial transactions: (at the beginning, before transactions a owes me 100 USD) a owes me 100 USD (now total debt 200) a receives 10% discount on what he owes me. (now total ...


4

This is indeed a concern for those building real-world applications - how does one measure "availability" - not the binary property discussed in the CAP theorem, but the experience for users of the system. There is industry agreement around this concern, and a standardized method of measuring it applicable to all systems. (Note: as stated in the comments, ...


4

Trie might help, it stores your "word list" like this: a / \ [a] a / \ [a] h \ e \ [d] And you can query by some operation like trie['a']['a']['h']['e'], which is just array index operation. It takes ...


4

I assume you mean the following: given $N$ columns, there are $N$ single columns, giving $N$ different indices $N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different indices $\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices and so on. This ...


3

No, it is not. Transitive closure is the closure of composition on binary relations; composition can be expressed as a rename (to make join operate on the right attributes), followed by a join, followed by a project to remove the common attributes. So composition can be expressed in terms of join, but (as Erwin Smout says) its transitive closure can not, ...


3

select * from R1 Where B=1 You don't have any index on a search field (B), hence you have to do a full table scan. It means that you fetch all relation's blocks one by one and take the records which satisfy the condition B=1. (Cost - 200000/200 = 200 blocks) select * from R2 Where C=1 There is not enough information - you have to know(at least ...


3

I agree with you. The distinction is pretty weak. I think the rationale is that transparent is supposed to mean "invisible", or "you don't even know it's there." Abstraction means that you don't see the implementation of something, but you know that it's there. Example: Consider Linux. There's one command, cp <srcfile> <destfile> for ...


3

There are plenty such applications. To give some examples: (windowed) data streams: Assume a sensor that sends new data every second. You want to know the average of the last minute. You keep the latest 60 elements. Every time you get a new element, the 61-st old element belongs to the previous minute, and you then delete it. queue: when each elements is a ...


3

Challenge #1: Imperative code You've shown code that is in a nicely functional form. But in many languages, in many cases, the code won't be in that nice form. Imagine if instead of var filtered = scores.Where(x => x.Article.Title != "trash").ToList(); the code is instead var filtered = new List(); for (x in scores) if (x.Article.Title != "trash"...


3

Distributed Hash Tables (DHT) are key value stores that work in a P2P manner, which is basically a database. There are implementations that don't rely on trust between peers. Obviously this can only be achieved by strong replication and consensus on the current value to a given key. So you face similar problems as with a blockchain. The Wikipedia Article ...


3

You are absolutely correct. Wikipedia has an error -- or perhaps, if we are feeling more charitable, we could call it an oversimplification. It is not true that the running time is at most $O(|R|+|S|)$. For instance, if we consider the case where the value of attribute $a$ is 42 for all elements of $R$ and $S$, we output $|R| \times |S|$ tuples. It is ...


3

Excellent question. This is known as the problem of answering reachability queries in a graph, and in particular, in a directed acyclic graph (dag). Basically, you want to know whether y is reachable from x by following edges in the graph -- that's known as a reachability query. (And symmetrically, you also want to know whether x is reachable from y -- ...


3

You can say anything you want, if you define your terms and your notation and make it clear what you are saying. In this case I would not expect someone to know what you mean by $M/f(n)$ or by $A \in M/f(n)$. Something like $P/\text{poly}$ is well-understood, but $P$ is a complexity class, and $M$ is a specific machine. Rather than risking confusion, just ...


Only top voted, non community-wiki answers of a minimum length are eligible