the analytic study of ways in which information is efficiently and effectively stored to and retrieved from computer systems.

learn more… | top users | synonyms

0
votes
0answers
11 views

Functional dependencies with the same key?

let's consider a table with carID | hireDate | manufactory | model | custID | custName | outletNo | outletLoc I want to evaluate all the functional dependencies ...
0
votes
0answers
17 views

Boyce-Codd Normal form and violation issue

I have the standard problem of BCNF in front of me, in the table hospital we have: ...
0
votes
0answers
24 views

Boyce-Codd Normal Form vs. 3rd Normal Form

Any schema that satisfies BCNF also satisfies 3NF. But how can this be true if BCNF does not necessarily guarantee dependency preservation, whereas 3NF guarantees dependency preservation?
2
votes
0answers
23 views

What is the intuition that 2-phase locking achieves serializability (also known as before-or-after atomicity)?

I am learning 2-phase locking and its unclear to me how it achieves/guarantees before-or-after atomicity (i.e. serilizability). I went to the following notes ...
2
votes
1answer
29 views

Can you reduce a precedence graph or do *all* relevant nodes need to be connected

Let's say we have the following simple transaction-schedule: T1 | T2 | T3 -----+------+----- w(x)| | | w(x) | | | w(x) T1 comes before ...
1
vote
0answers
17 views

How to display distinct rows from single column without using DISTINCT keyword and count() function? [closed]

How to display distinct rows from single column without using DISTINCT keyword and [having count(*) > 1 ] ? My question is can we do this using sub-queries or co-related sub query ? If yes how we can ...
1
vote
1answer
51 views

Clustered index is dense or sparse?

I am confused about clustered index is dense or sparse. I searched for that, sources saying it is sparse, but can be dense also. What is it exactly?
1
vote
0answers
12 views

Multvalued Dependencies [closed]

Suppose we have the following schema: Drinkers(name, addr, phone, beersLiked) Also suppose $\text{name} \twoheadrightarrow \text{phone}$. Consider the following ...
1
vote
2answers
41 views

Functional Dependencies and BCNF

Consider the following schema: Students(Id, Name, AdvisorId, AdvisorName, FavouriteAdvisorId) What are the functional dependencies here? Ir seems that it would ...
1
vote
1answer
80 views

Why is the Mean Time To Failure of multiple disks calculated via division and not multiplication?

I am reading about disk redudancy. I read the following: Suppose that the mean time to failure of a disk is 100,000 hours. Then the mean time to failure of some disk in an array of 100 disks ...
0
votes
0answers
11 views

Formal description of entity relationships and constraints in databases

I came across a slide online that I do not understand and can't find any explanation - or anything similar - on it anywhere. It describes a simple ERD relationship in terms of constraints on the ...
2
votes
0answers
57 views

What happened to Active Databases?

When reading the literature on declarative programming technology. A particular technology that sounded promising is active databases. It essentially allows the programmer to specify rules about data ...
1
vote
0answers
38 views

In database query theory, why do we not want to use a constant that isn't in the dictionary?

A badly explained textbook example asks the following: Suppose we have a definition of the dictionary our database will use (that is, it's relations and constants), defined as: $<R_\le (?, ?), ...
2
votes
3answers
150 views

What is the difference between Transitive Closure and Join?

In database theory, there is a notion of transitive closure over relations. I am wondering if join operator over relations is also a special case of transitive closure?
1
vote
2answers
392 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
79 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
35 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
19 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 ...
22
votes
6answers
2k 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
194 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
49 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 ...
4
votes
1answer
142 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
2answers
274 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 ...
6
votes
1answer
224 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 ...
9
votes
1answer
203 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
86 views

Optimizing a join where each table has a selection

Consider the following query: ...
5
votes
1answer
133 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 ...
5
votes
0answers
30 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
197 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
204 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
234 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 ...
21
votes
3answers
1k 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 ...
13
votes
2answers
318 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 ...