We’re rewarding the question askers & reputations are being recalculated! Read more.
35

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.


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

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 >...


11

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 ...


10

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 ...


7

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",...


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

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 ...


6

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 ...


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

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 ...


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

When an SQL statement is turned into an execution plan, several optimization techniques are used. The use of indices allow to efficiently (without a full scan) select tuples that agree with a selection condition. Another technique in use is semantic optimization, id est, to turn a query into an equivalent one with better behaviour. To do so, identities of ...


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

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}$ ...


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 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 ...


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

There are different schools of thought. The prevailing wisdom, originated with System R, is calculate cost of every execution strategy and select the minimal one. This leaves you at the mercy of optimizer calculating/guessing statistics and costing everything properly. Some people believe that this is almost never done reliably for any query of moderate ...


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

From Wikipedia: 1NF: The table faithfully represents a relation and has no repeating groups. 2NF: Non-prime attributes are non functionally dependent on a proper subset of a candidate key. 3NF: Non-prime attributes are non-transitively dependent on every candidate key in the table. BCNF: Every non-trivial functional dependency is a ...


3

One of the key differences between the different paradigms for data management is the underlying structure used to bind pieces of data together. IMHO, the difference between structured, unstructured, semi-structured is not precise enough : the point is that the underlying structure may be more or less flexible. This formal structure is used to define the ...


3

Wikipedia has a list of database models: http://en.wikipedia.org/wiki/Database_model


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

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 ...


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