the analytic study of ways in which information is efficiently and effectively stored to and retrieved from computer systems.
1
vote
1answer
69 views
“At least one” clause in Relational Algebra
I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause.
Example: I have:
a table with books (listing the title, year ...
4
votes
1answer
56 views
Computing number of block reads given relational algebra statement
So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and ...
1
vote
0answers
26 views
Is this protocol suitable for transaction services?
The paper Eventually-Serializable Data Services (PODC'96) presented an eventually-serializable data service.
In the abstract, it says：
… and generalizes their algorithm (in the related work Lazy ...
0
votes
1answer
12 views
VAR autoincrement with constant space consumption for super large tables
Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs ...
16
votes
6answers
396 views
What use are groups, monoids, and rings in database computations?
Why would a company like Twitter be interest in algebraic concepts like groups, monoids and rings. https://github.com/twitter/algebird
All I could find is:
Implementations of Monoids for ...
0
votes
0answers
62 views
Bond energy and vertical partitioning to get a vertical fragmentation in distributed dbms
Can anybody please solve the following problem step-by-step with explanations, using bond energy and vertical partitioning to obtain a vertical fragmentation of the set of attributes.
I need to ...
0
votes
0answers
24 views
adjustment and tuning in database [closed]
"It is well known that design and development activity of any kind is an ongoing
process requiring constant monitoring and periodic adjustment and tuning."
What is adjustment and tuning in database ...
0
votes
0answers
34 views
In DDBMS, What meaning of corresponding sites?
The last step in the design process is the physical design, which maps the local conceptual schemas to the physical storage devices available at the corresponding sites.
What meaning of corresponding ...
0
votes
0answers
52 views
Top-Down Design Process in Distributed Databases
"There is a relationship between the conceptual design and the view design. In one
sense, the conceptual design can be interpreted as being an integration of user views.
Even though this view ...
4
votes
1answer
110 views
What is OUTER UNION and why is it partially compatible
I am trying to understand how a OUTER UNION $∪^✳$ works, and why it is only partially compatible.
I am aware this operation was created to take union of tuples ...
0
votes
1answer
226 views
Decomposition of a relation to 3NF
Given a relation $R(A, B, C, D, E, F)$, with the following functional dependencies:
$\{A \rightarrow BC, CD \rightarrow E, B \rightarrow D, E \rightarrow A\}$.
The objective is to decompose $R$ into ...
5
votes
1answer
127 views
Measuring entropy for a table (e.g., SQL results)
We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
7
votes
1answer
193 views
Can joins be parallelized?
Suppose we want to join two relations on a predicate. Is this in NC?
I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
6
votes
2answers
79 views
5
votes
1answer
108 views
Compare-and-Swap in an RDBMS for custom locks and lock escalation
I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level.
The Resource table ...
4
votes
0answers
27 views
Uni-directional synchronization and locking issues
Suppose there are two databases, $D_1$ and $D_2$. Let's further assume $D_1$ is always up and $D_2$ can be down sometimes. When it goes up again, it has to restart.
$D_1$ is filled by say a dozen ...
10
votes
1answer
165 views
About Codd's reduction algorithm
Codd's Algorithm converts an expression in tuple relational calculus to Relational Algebra.
Is there a standard implementation of the algorithm?
Is this algorithm used anywhere? (It seems that the ...
3
votes
1answer
155 views
How to determine if a database schema violates one of the less known normal forms?
In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely ...
13
votes
3answers
211 views
Extension of SQL capturing $\mathsf{P}$
According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe ...
20
votes
2answers
397 views
Do subqueries add expressive power to SQL queries?
Does SQL need subqueries?
Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL ...
12
votes
1answer
253 views
Does the 'difference' operation add expressiveness to a query language that already includes 'join'?
The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases ...
