Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Derek Elkins left SE's user avatar
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(...
dimm's user avatar
  • 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. ...
david.pfx's user avatar
  • 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 ...
AntC's user avatar
  • 487
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 ...
Elastic Lamb's user avatar
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 ...
Heyheyhey's user avatar
  • 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 ...
Renzo's user avatar
  • 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 ...
KWillets's user avatar
  • 1,274
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 ...
Sameer Sah's user avatar
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$...
David Richerby's user avatar
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.'s user avatar
  • 160k
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 ...
Derek Elkins left SE's user avatar
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,...
Yuval Filmus's user avatar
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 ...
AntC's user avatar
  • 487
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 ...
chi's user avatar
  • 14.6k
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 ...
OmG's user avatar
  • 3,572
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 ...
Lance's user avatar
  • 2,233
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 ...
AntC's user avatar
  • 487
2 votes

Is it possible to encode logical expression and interpret it with SQL?

Using disjunctive normal form (DNF) representation. The following 3 tables arrangement seems to solve the problem (NB: using better names for tables, not same as in the question): ...
Roman Susi's user avatar
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 ...
Kristóf Marussy's user avatar
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 ...
TheCommonEngineer's user avatar
2 votes
Accepted

How to simplify the query qualification?

You are right, but it doesn't really matter — it still simplifies to $p_1$.
Yuval Filmus's user avatar
1 vote
Accepted

Doubt regarding foreign key and referential integrity

In general the “referential integrity constraint” is a constraint that states that a foreign key must always be equal to some primary key of a tuple in the referred relation (so establishing a ...
Renzo's user avatar
  • 809
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 ...
AntC's user avatar
  • 487
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 ...
Renzo's user avatar
  • 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 ...
Derek Elkins left SE's user avatar
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,...
Wenzel's user avatar
  • 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 ...
AntC's user avatar
  • 487
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 := \...
HEKTO's user avatar
  • 3,088
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 ...
Milton Silva's user avatar

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