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
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
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.♦
- 164k
5
votes
Accepted
Fastest way to search a word in a word list?
Trie might help, it stores your "word list" like this:
...
- 960
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
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
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
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
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
Did Date and Darwen's "Third Manifesto" have a lasting impact?
Hmm, before some moderator closes this q as being a matter of opinion, not substance ...
I think you need to consider whether the first two manifestos (to which TTM was a response) had any impact? I'...
- 497
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 ...
- 592
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 ...
- 752
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.♦
- 164k
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
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.♦
- 164k
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 ...
- 12.1k
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.♦
- 164k
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 ...
- 17.4k
3
votes
In database buffering why is it important : no writes to a block (which is to be moved from the disk buffer section of main memory) be in progress?
First off, let's remember the ACID of transactions:
Atomicity means that either the transaction happens or it does not happen. The transaction never partly happens.
Consistency means that a ...
- 23.1k
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 must uncommitted transactions be undone in backwards order?
Assume there is a table T with one column only.
Assume that the "undo log" is a database file containing uncommitted
transactions, and that the "redo log" is a database file containing
both ...
- 121
2
votes
How does NULL behaves with distinct keyword?
You will get 2 records, with value 2 and null
NULL is still a value when it comes to distinct, but it is not included if you do a count, so
...
- 209
2
votes
Measuring availability from CAP theorem
https://en.wikipedia.org/wiki/CAP_theorem
"CAP is frequently misunderstood as if one had to choose to abandon one of the three guarantees at all times. In fact, the choice is really between ...
- 209
2
votes
How is the R-Tree's MBR size determined? Changes to MBR?
First of all, let us have some background. There are variants of Guttman's r-tree that have different splitting heuristics (e.g. Sellis' r+-tree, which involves inserting an item multiple times into a ...
- 41
2
votes
Accepted
How large would a database containing perfect knowledge of chess be?
Claude Shannon indicated that the State Space Complexity (number of legal positions reachable from the initial position in chess) has a lower bound of approximately $10^{43}$. If each entry consists ...
- 313
2
votes
What are the essential differences and similarities among "data", "Information" and "knowledge" in the context of Computer Science?
All are main topics in Information Science.
Information
a) needs Human Being, without Human Being no Information
b) Information can be stored in Data for Computer
Data
a) stored Information
b) makes ...
Only top scored, non community-wiki answers of a minimum length are eligible