# Tag Info

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

13

Let me articulate the Curry-Howard-Lambek correspondence with a bit of jargon which I'll explain. Lambek showed that the simply typed lambda calculus with products was the internal language of a cartesian closed category. I'm not going to spell out what a cartesian closed category is, though it isn't difficult, instead what the above statement says is you ...

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

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

6

Let $R(A,B)$ and $S(B)$ be two relations. Division should find all values of A in R that are connected with all values of B (in S). Think $AB\div B=A$. Question 1: Yes. $R\div S=\pi_A(R)-\pi_A(\pi_A(R)\times S-R)$ Question 2: $\pi_A(R)\times S$ : this contains all possible AB pairs. $R$ : this contains the actual AB pairs. For the values of A that are ...

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

relational databases are among the highest value, most researched applications of computer science James, what do relational databases have to do with the question? And why have you tagged this q with 'relational-algebra'? It seems to me entirely gratuitous. Just because databases are 'relational' does not mean they have much to do with whatever Russell ...

4

In order to prove that $U$ is an equivalence relation, you need to use the definition: prove that $U$ is reflexive, symmetric and transitive. If you try to do that but it doesn't work, you can try to disprove the claim that $U$ is always an equivalence relation by giving a counterexample: equivalence relations $R$ and $S$ such that the corresponding $U$ isn'...

4

You need just two things: new values and recursion/while. New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that. Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE ...

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

Indices must not appear in relational algebra. That is because relational algebra is just a formal language which describes what you must do, but not how you must do it. It is comparable to the multiplication and other operations of the elementary arithmetic. There is a definition of what multiplying is but not of the way how you have to do it. There are ...

3

SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$ In your case, you want the users for which there does not exist a book that they have not borrowed: select * from people p where not exists (select *...

3

The relevant branch of mathematics is graph theory. Your elements are the vertices of the graph and the relationships between them are the edges. The triples you're looking for are known as triangles: sets of three vertices with all possible edges between them. I'm not quite sure what you're looking for in your question. If you just want a list of all the ...

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

2

The correct SQL would be : select co.name, cu.name from consultant co join project pr on co.id = pr.ConsultantID join CustomerCompany cu on cu.id = pr.CustomerId join Invoice i on i.Customer = pr.CustomerId where i.amount between 100 and 200 Converting to relation algebra is straightforward...

2

There are two flavors of outer union: with and without NULLs. Google search readily exibits an example for NULLs version. The cleaner version of relational algebra desn't allow NULLs, and outer union is defined via De Morgan's law: $X \bigcup Y = \overline {\overline X \Join \overline Y}$ Date&Darwen call this operation $\blacktriangleleft OR \... 2 Let's say that there's a [$k$-ary] relation$R$and [$m$-ary] function$f$such that$m>k$. Is$f$a polymorphism of$R$? Maybe, maybe not: it depends on the function and the relation. A given$k$-ary relation may have polymorphisms of arity arity less than, equal to, and/or greater than$k$. In fact, every relation has polymorphisms of all arities.... 2 Hint: to express "the set$S$has size$\ge 1$" in propositional logic (without using the "size" operator), you can write$\exists x . x \in S$. How would you express "the set$S$has size$\ge 2$"? Does that give you any ideas for how to use relational algebra to solve your question? 2 Follow the following steps : 1> Check which attributes are not present in RHS of the Functional Dependencies (FDs).These attributes cannot be derived and have to present in all the candidate keys. {D in this case} 2> Check closure of D. D- {D} D cannot derive all other attributes => not candidate key 3> Start checking closure of pairs of 2 attributes ... 2 You are right to start with the closures of the attributes. Finding the closures will help with finding the candidate keys. There might be more efficient ways to go about this. What works for me at least is to look at the given functional dependencies. If none of them have single attributes on the left-hand side, then don't bother with finding the closures ... 2 You cannot have free variables in your expression, i.e. all variables must either be quantified, or appear in the return tuple. So the answer is - always, unless the variable appears in the output tuple 2 Q 1: Is that True? No. It is the conventional minimal set, based on Codd's 1970 paper "Relational Completeness of Data Base Sublanguages". But Codd was wrong. He left out RENAME. Even to define Natural Join in terms of cross product needs RENAME. (Compare that Boolean Algebra's minimal set is usually taken as Union, Difference, Intersection. To achieve ... 2 The Wikipedia definition merely "opens the parentheses". Using the pure set-theoretic definition, we would expect $$((r_1,r_2,\dots,r_n),(s_1,s_2,\dots,s_m))$$ instead of $$(r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m).$$ Assuming$R,S$are both relations over the same universe$U$, the Wikipedia definition ensures that$R \times S$is an$(n+m)$-ary relation ... 2 The notation is defined on page 17 and 18. The authors define a couple notations and state that they will "freely switch back and forth" between them. This example doesn't seem super-consistent, I'd expect$Q(x,x'):\!\!-\,R(x),S(x,y),S(x',y),R(x')$rather than an equals sign, but presumably it means$Q(x,x') = \exists y.R(x)\land S(x,y) \land S(x',y)\land R(...

2

I'm interested in whether merging relational data has been researched, and what the findings have been. Here are several papers mainly on the tree-to-tree editing problem. A lot of good stuff is related to XML documents. Diffing, Patching and Merging XML Documents The tree-to-tree editing problem The Tree-to-Tree Correction Problem Simple Fast Algorithms ...

2

For the first solution suppose, given $id2$ and $size2$ which $\neg pizza(id2, size2)$ and $size1 < size2$. Although, the first solution said $pizza(id1, size1)$ is not maximum (because it is not true for all $id2$ and $size2$), but it can be false. Because, if $(id1, size1)$ is the only member of the table, it is the maximum. Therefore, the first ...

2

Assume $id1$ belongs to the first set. By definition we get that, for some value of $size1$, we have $$\forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)$$ The above says that, no matter what values we choose for $id2$ and $size2$, we have \$\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \...

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