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.
DylanSp's user avatar
  • 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 ...
oerkelens's user avatar
  • 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 ...
orezvani's user avatar
  • 1,944
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 ...
Renzo's user avatar
  • 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 ...
Joel's user avatar
  • 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.'s user avatar
  • 159k
5 votes
Accepted

Fastest way to search a word in a word list?

Trie might help, it stores your "word list" like this: ...
ice1000's user avatar
  • 940
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 ...
orezvani's user avatar
  • 1,944
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 ...
Sriram Srinivasan's user avatar
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 ...
Heyheyhey's user avatar
  • 131
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 ...
oerkelens's user avatar
  • 276
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 ...
Robert Harvey's user avatar
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 ...
thebeancounter's user avatar
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 ...
Ben Kudria's user avatar
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 ...
Renzo's user avatar
  • 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 ...
Steve's user avatar
  • 494
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 ...
Glorfindel's user avatar
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 ...
very's user avatar
  • 56
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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.'s user avatar
  • 159k
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 ...
Renzo's user avatar
  • 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 ...
Derek Elkins left SE's user avatar
3 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'...
AntC's user avatar
  • 487
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.'s user avatar
  • 159k
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 ...
Shaull's user avatar
  • 17.2k
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 ...
Madhav Kumar's user avatar
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 ...
Sarvottamananda's user avatar
2 votes

Restricting capabilities of admin role in database schema

Audit trails can provide a mean to accomplish that kind of security-related objective (individual accountability / reconstruction of event). Users (not only administrator) are less likely to attempt ...
manlio's user avatar
  • 2,052
2 votes
Accepted

Restricting capabilities of admin role in database schema

Generally, you cannot prevent administrators from making any change they want to the database. Many administrator actions require privileges that give them a lot of control over the database. For ...
D.W.'s user avatar
  • 159k

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