Skip to main content
14 votes

What does this definition of a Primary key mean?

Note how $K$ can be a set of columns. Irreducibility means that you have to pick minimal sets of columns. Nota bene: They should require $K \neq \emptyset$. For instance, consider this relation. <...
Raphael's user avatar
  • 72.6k
9 votes
Accepted

Confused between 2 phase locking and 2 phase commit

These are two different things that have two different goals. The two-phase locking protocol is designed to guarantee serializability for transactions that access concurrently a single, centralized ...
Renzo's user avatar
  • 809
8 votes
Accepted

What does this definition of a Primary key mean?

Consider the following table: ...
David Richerby's user avatar
6 votes
Accepted

Can databases use data structures/algorithms to respond to arbitrary queries?

Full disclosure: I've written the sort subsystem for a commercial database server, albeit not a SQL one. Database servers will use every trick you can think of, and a lot you haven't thought of, to ...
Pseudonym's user avatar
  • 22.5k
5 votes
Accepted

Time Complexity of Sort-Merge Join

You are absolutely correct. Wikipedia has an error -- or perhaps, if we are feeling more charitable, we could call it an oversimplification. It is not true that the running time is at most $O(|R|+|S|...
D.W.'s user avatar
  • 162k
5 votes
Accepted

Armstrong's axioms more precisely 'inference rules': what's the distinction?

First, terminologically, "axiom" and "inference rule" are often used as roughly interchangeable as they tend to serve similar purposes. There are technical distinctions, which themselves can vary ...
Derek Elkins left SE's user avatar
5 votes
Accepted

Is "Query Equivalence" decidable?

Suppose the abstract SQL you're considering has support for infinite-precision "big" integers that can store any integer values, and that these support *, ...
Curtis F's user avatar
  • 1,043
4 votes
Accepted

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

This question is related to the very basics of database theory, finite model theory and logics. I would strongly suggest Abiteboul's book on Foundations of Databases, or Libkin's book on Finite Model ...
Heyheyhey's user avatar
  • 131
4 votes
Accepted

Measuring availability from CAP theorem

This is indeed a concern for those building real-world applications - how does one measure "availability" - not the binary property discussed in the CAP theorem, but the experience for users of the ...
Ben Kudria's user avatar
4 votes

Does 1NF require that there can be no duplicate rows?

What was called 1NF in the past is considered nowadays part of the definition of the Relational Data Model itself: each attribute must be a single value, neither composed, nor repeated. When we talk ...
Renzo's user avatar
  • 809
4 votes
Accepted

Did Date and Darwen's "Third Manifesto" have a lasting impact?

Hmm, before some moderator closes this q as being a matter of opinion, not substance ... I think you need to consider whether the first two manifestos (to which TTM was a response) had any impact? I'...
AntC's user avatar
  • 497
4 votes
Accepted

Find candidate keys given functional dependencies

Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the ...
Renzo's user avatar
  • 809
4 votes

Is "Query Equivalence" decidable?

The problem of query-equivalence, and the problem of query-containment (knowing if the result of some query Q1 is a subset of the result of some other query Q2, for any possible instance of the ...
441Juggler's user avatar
4 votes

Is relational algebra a procedural, imperative, and/or declarative language?

The terminology used in the database area calls the relational algebra “procedural” to contrast it with the languages based on “calculus”, since an algebraic expression describes an ordered set of ...
Renzo's user avatar
  • 809
4 votes

What are other alternatives to version control on structured or large and highly volatile data?

With Git, you have to distinguish between three different things: The Abstract Git Object Model which sits at the core of Git. The Storage Format which sits underneath the Object Model. The surface ...
Jörg W Mittag's user avatar
3 votes
Accepted

How to evaluate relations in a DAG?

Excellent question. This is known as the problem of answering reachability queries in a graph, and in particular, in a directed acyclic graph (dag). Basically, you want to know whether y is ...
D.W.'s user avatar
  • 162k
3 votes

What is the difference between "strict schedule" and "cascadeless schedule"?

Definitions from the books by Korth et. al. and Elmasri et al.: Cascadeless schedule A cascadeless schedule is one where, for each pair of transactions $T_i$ and $T_j$ such that $T_j$ reads a data ...
Mahesha999's user avatar
  • 1,773
3 votes

Combine the following IP Addresses into a single block

An ip address has two parts: the address and the netmask. The address is just a 32-bit binary number. E.g. yours: ...
orlp's user avatar
  • 13.7k
3 votes

Does 2NF require 1NF?

I will focus on questions 2 and 3, mainly by recalling a little bit of history of the Relational Data Model. The first foundamental paper on the Relational Model was published in 1970 by the Turing ...
Renzo's user avatar
  • 809
3 votes
Accepted

Meaning of "pushing x down" and "pulling x up" in database query handling

I would normally say "pushing inward"/"pulling outward", but "down"/"up" make sense if you are thinking in terms of syntax trees and, being a computer scientist, your trees grow downward. In (...
Derek Elkins left SE's user avatar
3 votes

Why checking if tuple belongs to join of two tables is NP-complete?

If the claim is: for instance, given a join query $Q$ and a relational database $D$, checking if $Q(D)$ returns a tuple is NP-complete as well the NP-completness is about the decision if that join ...
Renzo's user avatar
  • 809
3 votes
Accepted

How to model references in an ontology

If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification: ...
unor's user avatar
  • 201
3 votes

Is persistence a property of a database?

The databases I've seen are persistent. But rather than trying to figure out the "one true meaning" of the word database, if this aspect matters in a specific context, then I suggest you ...
D.W.'s user avatar
  • 162k
3 votes
Accepted

Using B+Tree to implement index, when the index-key size and the data-block size are of the same order

Note: In what follows, I'm going to use the term "B-tree" to refer to the general idea of B-trees regardless of the variant, and "B+-trees" to refer specifically to B+-trees. You'...
Pseudonym's user avatar
  • 22.5k
2 votes

Clustered index is dense or sparse?

Clustered indexing can be both dense and sparse. Lets see how Quick recap: clustered indexing is done on non key attributes and it is sorted according to that attribute. Idea behind clustered ...
smsubham's user avatar
2 votes

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

I think this problem is interesting. So I want to provide a explanation, and I think it will help me understand it better. The die example Yuval provides is interesting. Because the distribution is ...
user100720's user avatar
2 votes

Finding the Candidate Keys of a Relation Using the FD's

Follow the following steps : 1> Check which attributes are not present in RHS of the Functional Dependencies (FDs).These attributes cannot be derived and have to present in all the candidate keys. {D ...
Sameer Sah's user avatar
2 votes

How is the R-Tree's MBR size determined? Changes to MBR?

First of all, let us have some background. There are variants of Guttman's r-tree that have different splitting heuristics (e.g. Sellis' r+-tree, which involves inserting an item multiple times into a ...
user63211's user avatar
2 votes

Measuring availability from CAP theorem

https://en.wikipedia.org/wiki/CAP_theorem "CAP is frequently misunderstood as if one had to choose to abandon one of the three guarantees at all times. In fact, the choice is really between ...
Soren's user avatar
  • 209
2 votes

Term for incorrect primary key

For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column ...
Klaas van Schelven's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible