# Tag Info

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

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

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

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

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 they are well-defined operators which can be analysed algebraically, and the order of operations thus rearranged or simplified by the database engine, or the ...

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

Yes. This is one plausible method, if you want to find pairs of vectors that are very close to each other. Two vectors that are close in Hamming distance are likely to end up in the same bin at some point. Suppose two vectors $v,w$ agree in fraction $p$ of their coordinates (where $0\le p \le 1$). Then, heuristically, if we look at a pair of coordinates, ...

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

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 java synchronized around each op. On the right side, the unit of atomicity is a transaction; an individual operation is not atomic. Which is why ...

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