# Tag Info

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

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(... 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. ... 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 ... 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 ... 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 ... 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 ... 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 ... 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:... 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 ... 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... 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"? ... 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,... 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 ... 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 ... 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 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 ... 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 ... 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 ... 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. 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 ... 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 ... 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,... 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 ... 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)} R1R3 := \... 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 ...
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 ...

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