Skip to main content

Questions tagged [relational-structures]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers

How to prove the independence of difference in relational algebra?

The five basic operator select, project, cartesian product, union and difference in relational algebra are independent of each other. But how to prove the independence of difference in relational ...
gentillii's user avatar
2 votes
1 answer

What is the computational complexity of Acyclic Joins?

I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is ...
SagarM's user avatar
  • 716
3 votes
0 answers

Decomposition of rectangular relations

Let $\alpha$ be a binary relation from $\gamma$ to $\chi$ and $\beta$ a binary relation from $\chi$ to $\rho$. If both $\alpha$ and $\beta$ are rectangular, i.e., they satisfy $\alpha \alpha^{-1} \...
delete000's user avatar
  • 828
11 votes
2 answers

Does the first order theory of a finite structure have bounded quantifier rank?

Let $\mathfrak{A} $ be any finite structure. Does its first order theory $ \mathfrak{T} := \mathfrak{TH}(\mathfrak{A}) $ have bounded quantifier rank, in the sense that there is a $ q\in\mathbb{N} $ ...
D. Rusin's user avatar
  • 207
24 votes
1 answer

Is there a relationship between relational algebra/calculus and category theory?

I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory. Is there any relationship between these ...
Chill2Macht's user avatar
2 votes
1 answer

Upper bound on the size of a Concept Lattice (Galois Lattice)?

A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ ...
Luz's user avatar
  • 427
-1 votes
2 answers

What are the most fundamental metrics (criterions) of database performance?

I'm a student working on my thesis in database theory and looking for some research in the field of formal models of database performance and couldn't find any works in this area. I'm interested: what ...
MainstreamDeveloper00's user avatar
4 votes
0 answers

Residual for transitive hull

I work in the algebra $R$ of reflexive, transitive relations over some set $S$, ordered by subset inclusion. This is a complete lattice, with intersection as g.l.b. and transitive hull as l.u.b., i.e. ...
Uli Fahrenberg's user avatar
2 votes
2 answers

What is DDL (Data Definition Language)?

As a part of my curriculum, I am studying principles of DBMS from the book by Silberschatz and Korth. A part of it is about Data Definition Language (DDL). I ...
An SO User's user avatar
8 votes
1 answer

Complete axiomatization of relation algebras without ${}^-$ and $\top$

I'm working on a more thorough algebraic treatment of delta modeling. Briefly, deltas are syntactic entities that can modify products (as in 'software products'). They actually represent relations on ...
mhelvens's user avatar
  • 231
5 votes
1 answer

Relation between Kleene star, union and difference in relation algebra

So I'm wondering about some finer points of relation algebra, a field in which I'm not an expert: Given relations $A$, $B$ and $C$ over the same set $S$, is it always true that $A^*\subseteq (B\cup C)...
Uli Fahrenberg's user avatar
0 votes
1 answer

Euclidean transitive relations

I am currently looking at relations that are both transitive and Euclidean, but not necessarily symmetric, hence not necessarily equivalence relations. I have found nothing about this kind of ...
BastienMob's user avatar
7 votes
0 answers

Relational model for data structure reasoning

I am trying to find out if there is any work on applying the Codd's relational model (underlying relational databases) for reasoning about linked data structures. Any connections with UML models and ...
Uday Reddy's user avatar
  • 4,796
1 vote
1 answer

Theory of user control systems?

TL;DR: I am looking for theoretical sources about the different manners to implement user access control. Long version I have almost finished all the stand-alone tools needed in my CMS. I am not ...
Xananax's user avatar
  • 129
4 votes
2 answers

Canonical forms for relational algebra expressions

I'm looking for whatever work may exist, or thoughts people have, on the question of whether/to what extent there exist(s) one or more canonical form(s) to which relational algebra expressions may be ...
Doug McClean's user avatar
12 votes
3 answers

What are recent advances in relational databases?

I'm wondering what are recent advances in relational database theory and related domains? I'm interested in new approaches, query languages (alternatives to SQL and/or extensions to it), products (...
andreypopp's user avatar
0 votes
1 answer

How to automatically generate indexes and preaggregations from queries

This question might be a little ill-specified, but the idea I want to explore is: User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-...
Andy's user avatar
  • 1
5 votes
1 answer

Definition of a hereditary relation

Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307: Given a tree $S$, define … $\#$ is ...
beroal's user avatar
  • 557
15 votes
6 answers

Global properties of hereditary classes?

A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal. Classes of graphs that exclude a minor have nice ...
András Salamon's user avatar