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
10 views

Isomorphism of the cores of two symbol universes implies equivalence

We know that an isomorphism exists between two symbol universe of CQ expressions $\psi$ and $\phi$, $A_\psi$ and $A_\phi$ and $symb(\psi) = symb(\phi)$ iff $\psi \equiv \phi$. But given only that ...
0
votes
1answer
45 views

BCNF Decomposition: Confusion regarding given answer

I encountered the following question: Given a relation R(A, B, C, D) with the following functional dependencies: A -> B, C -> D, B -> C. The BCNF Decomposition of R is: A) {(A,B), (C,D), (B,C)} B) ...
1
vote
1answer
22 views

Applying Brewer's theorem (CAP) to a single node

I'm going through Brewer's theorem and its proof by Nancy Lynch and Seth Gilbert. But the paper left me with one question. What prevents the theorem from being applicable to a single node? I haven’t ...
0
votes
1answer
35 views

Composition for Functional Depedencies

Suppose I have the following Functional Dependencies for a Relational Model: $A \to C$ $B \to C$ According to the composition rule for functional dependencies we have: ...
-2
votes
1answer
18 views

How 3NF and BCNF are different in terms of candidate key?

The original definition of third normal form (3NF) was inadequate in some situations. It was not satisfactory for the tables: - that had multiple candidate keys - where multiple candidate keys were ...
0
votes
0answers
24 views

Difference between parallel and concurrent buffering?

In double buffering there are two terms Concurrent buffering. Parallel buffering. What is the difference between them, answer with example will be appreciated.
1
vote
0answers
23 views

Does 4NF imply BCNF?

Wiki says: 4NF is the next level of normalization after Boyce–Codd normal form, but I can not see how the definition of 4NF implies BCNF. Consider the relation with 3 attributes: Country, ...
1
vote
1answer
30 views

A relationship in a UML class diagram

I am investigating a small database in a paper: Each line is a selling record. For instance, Line 2 expresses that ...
0
votes
1answer
55 views

Use count() in relational algebra

Person(name, phone) Mike 456-789 Mike 123-456 John 230-785 $\dots \dots$ How to get those people who have more than one phone numbers with relational algebra? This sounds simple, but I am ...
0
votes
0answers
28 views

convert domain relational calculus with two same tuples to relational algebra

Given two relations $R(A, B)$ and $S(A, C)$. I can understand the early part is the projection of attribute $A$ from $S$, which could be written as $π_a(S)$, but later part is confusing and not ...
0
votes
0answers
27 views

Definition of 3NF

We've been studying relational database design in the last semester, and I was missing a lot of lecturers, so I decided to stick to the course's book, Database Systems; The Complete Book, to make up ...
2
votes
1answer
53 views

What actually is the concept of transparency? Why not call it Abstraction?

I searched this over Google few times but ended up with articles on transparency rather than an answer. With relation to distributed database study(or distributed OS), what is the concept of ...
0
votes
1answer
56 views

Automatically generate meaningful queries for a data table

My field of research is not Database or AI. But I have some problems to solve, and would like to know which branch this kind of problems belong to, and what are the results. The main question is: ...
2
votes
1answer
31 views

Can A still be a key if two tuples are the same

I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key. What if 2 tuples are exactly the same, can we still say A is ...
0
votes
0answers
23 views

1NF to 2NF, do the functional dependencies remain?

When decomposing from 1NF to 2NF, is there a guarantee that the functional dependencies don't change in regards to the original relation? Example: ...
1
vote
1answer
29 views

Functional Dependencies in Relations

I'm currently reading about functional dependencies. I've read Armstrong's axioms about: Relexivity: $if$ $B\subseteq A$ $then$ $A\to B$ Augmentation: $if A\to B$ $then$ $AC\to BC$ Transitivity: ...
0
votes
1answer
77 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
30 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
1answer
84 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
1answer
60 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
2answers
83 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
25 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 ...
0
votes
1answer
90 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
76 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
178 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 ...
2
votes
0answers
59 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
40 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
202 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
750 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
92 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
37 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
21 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
3k 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 ...
4
votes
1answer
169 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
283 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
271 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
212 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
92 views

Optimizing a join where each table has a selection

Consider the following query: ...
5
votes
1answer
154 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
32 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
215 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 ...
4
votes
1answer
250 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 ...
14
votes
3answers
241 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
2k 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 ...
14
votes
2answers
346 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 ...