36
votes
Why must uncommitted transactions be undone in backwards order?
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.
- 865
12
votes
Why must uncommitted transactions be undone in backwards order?
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 ...
- 276
11
votes
Accepted
What is the difference between a R-tree and a BVH?
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 ...
- 1,934
9
votes
Accepted
Confused between 2 phase locking and 2 phase commit
These are two different things that have two different goals.
The two-phase locking protocol is designed to guarantee serializability for transactions that access concurrently a single, centralized ...
- 809
7
votes
Why must uncommitted transactions be undone in backwards order?
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 ...
- 171
5
votes
Accepted
Good snapshottable data structure for an in-memory index
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/...
- 17.6k
5
votes
Accepted
Time Complexity of Sort-Merge Join
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|...
D.W.♦
- 154k
4
votes
Accepted
When should you use the existential and universal quantifiers for Relational Calculus?
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 ...
- 131
4
votes
Who needs linearizability?
First, linearizability and serializability are not directly comparable. As the table below shows, the main difference is that on the left hand side, all individual operations are atomic (like having a ...
4
votes
Accepted
What is the difference between F+ (closure of F) and F* (cover of F) for Functional Dependencies?
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 ...
- 1,934
4
votes
Accepted
Need help with ER diagram
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 ...
- 276
4
votes
Why must uncommitted transactions be undone in backwards order?
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 ...
- 141
4
votes
blockchain database - why so redundant
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 ...
- 263
4
votes
Accepted
Measuring availability from CAP theorem
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 ...
- 106
4
votes
Accepted
Fastest way to search a word in a word list?
Trie might help, it stores your "word list" like this:
...
- 928
4
votes
Accepted
Find candidate keys given functional dependencies
Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the ...
- 809
4
votes
In a DBMS what are the implementation details that make set operations faster than cursors?
Set-based operations are iterative at a "low level", and are not necessarily any faster to execute than cursors under all circumstances.
The main advantage with set-based operations is that ...
- 484
4
votes
Accepted
What is the maximum number of indices one can create on a table with N columns?
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 ...
- 746
3
votes
Is there a fundamental CS problem in ORMs that leads to N+1?
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
...
D.W.♦
- 154k
3
votes
An application where we always delete the oldest object?
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 ...
- 20.6k
3
votes
Accepted
Are there any types of distributed databases which allows untrusted peers, like Blockchain?
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 ...
- 56
3
votes
Accepted
How to evaluate relations in a DAG?
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 ...
D.W.♦
- 154k
3
votes
If we allow a database, what complexity class it is?
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 ...
D.W.♦
- 154k
3
votes
Does 2NF require 1NF?
I will focus on questions 2 and 3, mainly by recalling a little bit of history of the Relational Data Model.
The first foundamental paper on the Relational Model was published in 1970 by the Turing ...
- 809
3
votes
Accepted
Why must a Primary Index be sparse?
Without the context of the excerpt, I found it confusing since it seemed to depend on fairly specific implementation details. This is, in fact, the case. These course notes give a decent overview of ...
3
votes
Is persistence a property of a database?
The databases I've seen are persistent. But rather than trying to figure out the "one true meaning" of the word database, if this aspect matters in a specific context, then I suggest you ...
D.W.♦
- 154k
3
votes
What is the difference between a state machine and a database
State machines and databases are quite different entities, and their usage (or functionality) is very different.
In this answer, I'll just try to separate them with respect to the similarity you ...
- 17k
2
votes
Number of concurrent schedules in database
Number of possible Concurrent schedules are
$$^{m_1+m_2+m_3+...+m_n}C_{m_1}*^{m_2+m_3+...+m_n}C_{m_2}*^{m_3+...+m_n}C_{m_3}*...*^{m_n}C_{m_n}$$
We need to maintain order of operations of an ...
- 21
2
votes
Why isn't there a universal separator character for data files?
We could have a field separator, but we don't, because of historical reasons. Most of the characters are brought from the era of typewriters. So we have line-separator ^M and page-separator ^L, and we ...
- 4,807
2
votes
Accepted
The finer details of Meek's STV
In Meek STV, there is the concept of the quota or threshold that a candidate must exceed to be considered elected. This threshold is changed from round to round in the Meek STV system. The threshold ...
- 296
Only top scored, non community-wiki answers of a minimum length are eligible