# Tag Info

14

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

8

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

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

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

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

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

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

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

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

3

The terminology used in the database area calls the relational algebra “procedural” to contrast it with the languages based on “calculus”, since an algebraic expression describes an ordered set of steps to find the result: simply execute the operations in the correct order to produce the result. In contrast, in an expression of a calculus based language, ...

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

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

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

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

2

I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query ... Why do people persist in this confusion? The semantics of SQL is different to Codd's Relational Model. ...

2

After searching around for paper some more (unfortunately, I found nothing in Ling Liu, M. Tamer Özsu eds. Encyclopedia of Database Systems), I managed to find out that these dependencies are called numerical dependencies. In particular, standard notation for my $\mathcal{A} \rightrightarrows^k \mathcal{B}$ is $\mathcal{A} \xrightarrow{k} \mathcal{B}$, which ...

2

As far as I could understand, there are 3 entities here. Map Road Road Segment And the relationships between them are: Map M:N Road Road 1:N Road Segment Map 1:N Road Segment A map could have multiple roads and a road could in multiple maps. A road could have multiple segments, in each map it is a part of. And a road segment would be related to one map ...

2

You are right, but it doesn't really matter — it still simplifies to $p_1$.

1

The usual form of Division requires that the attributes in B are a subset of the attributes in A. And the result of the Division has just the attributes particular to A -- that is A[X] in your formulation. I'm not sure if you understand that A[X] is a projection. So the Heading of A[X] TIMES B is exactly the Heading of A. So the inner MINUS is dealing with ...

1

I believe that your problem is NP-complete. Showing that it's in NP is easy. To show that it's NP-hard, take any instance of the set cover problem. Add a new unique element to the universe, and add it to each set. Interpreting each set as a table, a solution to the minimum join problem is a solution to the original set cover problem.

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