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

learn more… | top users | synonyms

-1
votes
1answer
58 views

Naive Bayes MapReduce

I have the following question to answer in a MapReduce assignment sheet The Naive Bayes classifier is a widely-used tool for analyzing data. Consider a data set that has $n$ data items, each of ...
0
votes
0answers
11 views

is it possible to combine 2 relation with an entity set for rdbms minimization?

E1 is a weak entity set. E2 and E3 are other two entity sets. E1 is related to E3 via a weak relation R1 cardinality is many to 1 and E1 is connected to E3 via R2 with cardinality many to 1. Now in ...
0
votes
1answer
22 views

When should you use the existential and universal quantifiers for Relational Calculus?

Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus? Given this schema: Hotel(hotelNo, hotelName, city) ...
0
votes
0answers
4 views

Search using LIKE in a table [migrated]

I want to retrieve data of 'Match' and 'Average' columns from the following table if '2' exists using LIKE. I have tried by writing the following query but it failed. SELECT * FROM ...
0
votes
0answers
12 views

What is the difference between Strict 2Phase Locking and 2Phase Locking?

I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides, Two Phase Locking and Strict Two Phase Locking They have ...
2
votes
0answers
55 views

What is a best known algorithm for finding diameter of undirected graph?

What is best known algorithm (approximate or exact) for finding diameter of a large undirected graph? The diameter is defined as longest of shortest paths between any two nodes. I know that naive ...
3
votes
1answer
58 views

Partial order, total order, and version order in transaction histories

In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]: A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the ...
0
votes
2answers
56 views

Understanding transactions

In operating systems, Is a transaction a process? Are they the same concept? Does a transaction have the same meaning in database management systems, as in OS? A database book says A ...
2
votes
1answer
108 views

Can a schedule with cyclic precedence graph still be serialisable?

We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict ...
5
votes
1answer
46 views

Why do relational databases use 2PC for distributed transactions over the likes of Paxos?

Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case ...
1
vote
0answers
18 views

1-serializability theorem in database theory

In the paper "MVCC@TODS'1983 by Bernstein et al.", 1-serializability ($1$-$\text{SR}$) problem is defined as a decision problem: To decide whether an MV (multi-version) log $L$ is $1$-$\text{SR}$. ...
0
votes
0answers
16 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
80 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
29 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
39 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
29 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
28 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
34 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
36 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
108 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
51 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
29 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
55 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
68 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
26 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
32 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
80 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
33 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
109 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?
1
vote
1answer
74 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
123 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
26 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
151 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
13 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
80 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
265 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
61 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
227 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
895 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
95 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
22 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 ...
23
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
190 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
289 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
301 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
214 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
93 views

Optimizing a join where each table has a selection

Consider the following query: ...