15
votes
Accepted
Is there an isomorphism between (subset of) category theory and relational algebra?
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 ...
7
votes
Accepted
Expressing division in relational algebra in terms of other operations
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(...
- 186
5
votes
Accepted
Smallest set of features that would make relational algebra Turing complete
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. ...
- 186
5
votes
Type Theory and Principia Mathematica Part IV "Relation Arithmetic"
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 ...
- 477
4
votes
Relational algebra and indexes
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 ...
- 148
4
votes
Accepted
When should you use the existential and universal quantifiers for Relational Calculus?
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 ...
- 131
4
votes
Is relational algebra a procedural, imperative, and/or declarative language?
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 ...
- 809
3
votes
Relational query for universally quantified formula
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 ...
- 1,274
3
votes
Accepted
Combinations of elements with mutual relationships
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:...
- 81.4k
2
votes
Finding the Candidate Keys of a Relation Using the FD's
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 ...
- 31
2
votes
Accepted
Can a $k$-ary relation have polymorphisms of arity greater than $k$?
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$...
- 81.4k
2
votes
Accepted
Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }
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$"? ...
D.W.♦
- 156k
2
votes
Accepted
What do the commas separating atomic events in a Relational Calculus formula means?
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 ...
2
votes
Accepted
Difference between the Cartesian product in set theory and in relational algebra
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,...
- 275k
2
votes
Accepted
Max() in Domain Relational Calculus
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 ...
- 14.4k
2
votes
Max() in Domain Relational Calculus
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 ...
- 3,562
2
votes
Automatically merging relational data
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 ...
- 2,163
2
votes
Relational calculus to SQL
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 ...
- 477
2
votes
Expressing division in relational algebra in terms of other operations
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 ...
- 477
2
votes
"Functional dependencies" with cardinality constraints
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 ...
- 171
2
votes
Are entities in a many-to-many relation related individually?
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 ...
2
votes
Accepted
How to simplify the query qualification?
You are right, but it doesn't really matter — it still simplifies to $p_1$.
- 275k
1
vote
Whether same output is obtained for the two queries
where Eid field is empty.
What do you mean by "empty"? Perhaps you mean 'null'?
What words exactly does your "solution manual" use? "empty" or "null"?
If the Eid ...
- 477
1
vote
Accepted
Normal form of relation R
If you bring the functional dependencies of R in a canonical form, you can have only dependencies in which the right part is constituted only by a single attribute, which is prime, so we are sure that ...
- 809
1
vote
Use of existential quantifier in tuple relational calculus
Something like { c.name | ... } is shorthand for something like
{z : (name) | (∃c) (z.name = c.name ^ ...) }.
As described ...
1
vote
How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities
Firstly $\Pi_{i_1, i_2}(\sigma_{i_1\leq i_2}{(\rho_{c_1(i_1, s)}People\times \rho_{c_2(i_2, s)}People)})$ gives all possible permutations of ID pairs in the form $(a, b)$ with $a\leq b$.
By $\Pi_{i_1,...
- 88
1
vote
What is the equivalent form of full outer join in relational algebra?
Full outer join returns null in the columns of rows from one table that don't match the other table -- that's a description of SQL.
Standard Relational Algebra doesn't have nulls. Here explains what ...
- 477
1
vote
Accepted
relational algebra to get unique pairs
You need more carefully defined $\theta$-join and then set difference:
$$R1 := \rho_{name1/name,hobby1/hobby}(Person)$$
$$R2 := Person \bowtie_{(hobby=hobby1) \land (name \neq name1)} R1$$
$$R3 := \...
- 3,048
1
vote
Accepted
Is Datalog negation and the built-in predicate $ \neq $ similar?
There was a misunderstanding in regards to the evaluation algorithm/minimal model.
The derivation of new values is atomic e.g.:
step 1:
p = {}
q = {}
step 2:
p = r
q = r
In step 2 p and q only ...
- 815
1
vote
SQL, optimizing a select statement in relational algebra
I suspect this is a homework question.
Edit: OK, you're trying to invent your own homework. Well done for trying. You might have bitten off too much.
We need first to sort out the headings of your ...
- 477
Only top scored, non community-wiki answers of a minimum length are eligible