27

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity). By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid). By using Rings, we can do ...


16

To translate your statement into the relational algebra, I think it asks: Can we rewrite $\sigma_A(A)\bowtie \sigma_B(B)$ as $\sigma_A(\sigma_B(A\bowtie B))$? (Where $\sigma$ is select and $\bowtie$ is join.) The answer is "Yes," and it's a standard query optimization. To be honest, I'm not sure how to prove this in a non-question-begging manner - it's ...


14

In relational algebra, we shall first provide an informal definition of left (outer) join, and proceed to prove that it, renaming, selection, join and projection can construct difference, as well as that difference, selection and union can be used to construct left (outer) join. Actually, we'll end up doing it in the reverse order: we'll show how to ...


14

Note how $K$ can be a set of columns. Irreducibility means that you have to pick minimal sets of columns. Nota bene: They should require $K \neq \emptyset$. For instance, consider this relation. A B C 1 4 4 2 4 6 3 6 6 Let us investigate all possible keys. A -- unique and irreducible. B -- not unique. C -- not unique. A,B -- reducible ...


11

Monoids are ubiquitous in programming, just that most programmers don't know about them. Number operations like addition and multiplication. Matrix multiplication. Basically all collection-like data structures form monoids, where the monoidal operation is concatenation or union. This includes lists, sets, maps of keys to values, various kinds of trees etc. ...


9

There is some terminology confusion; the query block within parenthesis SELECT t1.name, t2.address FROM table1 JOIN (SELECT id, address FROM table2 AS t3 WHERE t3.id = t1.id) is called inner view. A subquery is query block within either WHERE or SELECT clause, e.g. select deptno from dept where 3 < (select count(1) from emp ...


8

This reduction is the constructive proof technique to show that a subset (named safe) Tuple Relational Calculus (TRC) is less expressive than Relational Algebra (RA). The other way being true too, Safe-TRC and RA have equivalent expressive power. See Theorem 5.3.10 for instance. The syntactic "safety" restriction ensures the domain independent property of ...


7

One important problem in distributed file systems (DFS) is to generate files from distributed blocks. The area of Erasure code from information theory and Algebra (groups, rings, linear algebra,...) is used extensively in distributed fault tolerant file systems for example in HDFS RAID (Hadoop Based File System). Social network and Cloud companies are ...


7

A syntax of aggregate operation in relational-algebra (according to [1]) is as follows : $G_1,G_2,...,G_n \hspace{2 mm}\textbf{g}\hspace{2 mm} F_1(A_1),F_2(A_2),...,F_m(A_m)(E)$ where $E$ is any relational-algebra expression; $G_1,G_2,...,G_n$ constitute a list of attributes on which to group; each $F_i$ is an aggregate function; and each $A_i$ ...


7

Consider the following table: FirstName LastName Pet FavColour ----------------------------------- Alice Jones dog red Alice Smith dog green Bob Smith cat blue A key is any set of attributes: any subset of {FirstName, LastName, Pet, FavColour}. The uniqueness property says that no two records can have the same values for ...


6

Think of it this way. A single disk fails on average after $100,000$ hours. Now you have $100$ disks. How long before one of them fails? It will almost certainly take much less than $100,000$ hours for the first to fail, and much more than $100,000$ hours for the last to fail. (This of course depends on the distribution of failures, which is assumed to be ...


6

If your question is What are examples of groups, monoids, and rings in computation? then one example I can think of off-hand is for path-finding algorithms in graph-theory. If we define a semiring with $+$ as $\min$ and $\cdot$ as $+$, then we can use matrix multiplication with the adjacency matrix to find all-pairs-shortest-path. This method is ...


6

On a cascadeless schedule a transaction $T_2$ cannot read a value $a$ if a transaction $T_1$ wrote $a$ before that and didn't commit. On a strict schedule $T_2$ also wouldn't be able to write $a$ after $T_1$ wrote it (even if it read $a$ before $T_1$ wrote it). If you read carefully, the definition of strict says "not read or overwritten". That's the ...


6

XML is nothing more than a well-defined way to store trees of strings. Since even plain strings can encode everything you can encode in practice (i.e. countable sets), yes, XML can "model" everything. But that's nothing special. The popularity of XML is probably due to it being standardized and the amount of tool support that has developed. There is no ...


5

As for your main question, I recommend this short survey by Martin Grohe. Are the queries that are needed in practice usually simple enough that there is no need for a stronger language? I'd say this holds most of the time, given the fair amount of extensions added to common query languages (transitive closure, arithmetic operators, counting, etc.). This ...


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

First, terminologically, "axiom" and "inference rule" are often used as roughly interchangeable as they tend to serve similar purposes. There are technical distinctions, which themselves can vary slightly, but outside the study of formal logic or related systems, these distinctions aren't that important. In the context of formal logic, an axiom is a formula ...


4

The set of all words over some finite alphabet together with concatenation forms the free monoid $(\Sigma^*, \cdot)$. Therefore, the whole field of formal language can be viewed through the algebraic lense, and it is sometimes taught like this. In return, considerations on formal languages have yielded the Earley parser which can be extend to parse on ...


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

Yes it is necessary. According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$ is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation in $T_j$. It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $...


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

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

What was called 1NF in the past is considered nowadays part of the definition of the Relational Data Model itself: each attribute must be a single value, neither composed, nor repeated. When we talk about relations we assume implicitly this fact, since structures with non-flat attributes are not considered proper relations. Note, however, that there exists ...


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

I have math background but I'm not computer scientist. It would be great to have "real-world" uses of monoids and semi-groups. These are normally considered useless theoretical constructs, and ignored in many abstract algebra courses (for lack of anything interesting to say). There is rather too much interesting to say. However, it's more a topic of ...


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

The Prevent race conditions across multiple rows on Stackoverflow seems to be relevant. Also, I would urge you to use SQL server locks instead of your own lock column (which it sounds like you're doing). And it looks like doing hierarchical locks is kind of clumsy in SQL, so if you're finding this to be a huge bottleneck you could try a locking service ...


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

First, the expressive power of SQL is less clear-cut than it seems. The aggregate, grouping, and arithmetic features of SQL turn out to have quite subtle effects. A priori, it seems feasible that by some encoding of algebraic operators using these features, one could actually express reachability in SQL. It turns out this isn't actually the case for SQL-...


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