14

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. A B C 1 4 4 2 4 6 3 6 6 Let us investigate all possible keys. A -- unique and irreducible. B -- not unique. C -- not unique. A,B -- reducible ...


8

A syntax of aggregate operation in relational-algebra (according to [1]) is as follows : $G_1,G_2,...,G_n \hspace{2 mm}\textbf{g}\hspace{2 mm} F_1(A_1),F_2(A_2),...,F_m(A_m)(E)$ where $E$ is any relational-algebra expression; $G_1,G_2,...,G_n$ constitute a list of attributes on which to group; each $F_i$ is an aggregate function; and each $A_i$ ...


8

Consider the following table: FirstName LastName Pet FavColour ----------------------------------- Alice Jones dog red Alice Smith dog green Bob Smith cat blue A key is any set of attributes: any subset of {FirstName, LastName, Pet, FavColour}. The uniqueness property says that no two records can have the same values for ...


7

Think of it this way. A single disk fails on average after $100,000$ hours. Now you have $100$ disks. How long before one of them fails? It will almost certainly take much less than $100,000$ hours for the first to fail, and much more than $100,000$ hours for the last to fail. (This of course depends on the distribution of failures, which is assumed to be ...


6

On a cascadeless schedule a transaction $T_2$ cannot read a value $a$ if a transaction $T_1$ wrote $a$ before that and didn't commit. On a strict schedule $T_2$ also wouldn't be able to write $a$ after $T_1$ wrote it (even if it read $a$ before $T_1$ wrote it). If you read carefully, the definition of strict says "not read or overwritten". That's the ...


6

XML is nothing more than a well-defined way to store trees of strings. Since even plain strings can encode everything you can encode in practice (i.e. countable sets), yes, XML can "model" everything. But that's nothing special. The popularity of XML is probably due to it being standardized and the amount of tool support that has developed. There is no ...


6

Excellent question, and since you referred to us ("jOOQ developers", which I am - working for the company behind jOOQ), I feel qualified to give a partial answer. A bit of historic context first Since the very beginning of software, there had been: Theory (which is what "Computer Science", i.e. this Stack Exchange subsite is about) Practice (more like ...


6

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 speed up operations such as sorting. But it can only do so much if you give it an overly complex query. Query optimisers are not magic, any more than compilers ...


5

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 slightly, but outside the study of formal logic or related systems, these distinctions aren't that important. In the context of formal logic, an axiom is a formula ...


5

Suppose the abstract SQL you're considering has support for infinite-precision "big" integers that can store any integer values, and that these support *, +, and = in WHERE clauses. Fix the schema as $k$ such integer values columns called x_1, ..., x_k. Query equivalence in this schema is undecidable by a reduction to the satisfiability of Diophantine ...


4

Yes it is necessary. According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$ is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation in $T_j$. It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $...


4

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 Theory. Very roughly stated, a database is a collection of facts, and a query is a logical formula, which is used to specify certain patterns to be matched ...


4

Closure and cover are two completely different things. The closure of a set of attributes or a functional dependency $f$ is a set of relation schemes that can be implied by $f$. In order to find the closure, we can expand the FD or the set of attributes based on the given set of FDs by replacing each relation with the ones inferred by it. For example, $$X ...


4

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 system. There is industry agreement around this concern, and a standardized method of measuring it applicable to all systems. (Note: as stated in the comments, ...


4

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 about relations we assume implicitly this fact, since structures with non-flat attributes are not considered proper relations. Note, however, that there exists ...


3

You are right to start with the closures of the attributes. Finding the closures will help with finding the candidate keys. There might be more efficient ways to go about this. What works for me at least is to look at the given functional dependencies. If none of them have single attributes on the left-hand side, then don't bother with finding the closures ...


3

I agree with you. The distinction is pretty weak. I think the rationale is that transparent is supposed to mean "invisible", or "you don't even know it's there." Abstraction means that you don't see the implementation of something, but you know that it's there. Example: Consider Linux. There's one command, cp <srcfile> <destfile> for ...


3

One of the reasons is the message complexity. For N nodes, 2PC will require 3N to be exchanged whereas Paxos requires 4N. Also, Paxos adds sequence numbers to each message which adds a significant overhead to the overall execution.


3

Pragmatically, You are correct that when you declare something as a primary key, that it must correspond to one tuple. Databases will not allow you to store a tuple in a table if the primary key already exists for a tuple in the table. Theoretically, If $R$ is a relation with the following set A of attributes $\{a_1, a_2,..., a_n\}$, then a primary key on ...


3

SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$ In your case, you want the users for which there does not exist a book that they have not borrowed: select * from people p where not exists (select *...


3

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|)$. For instance, if we consider the case where the value of attribute $a$ is 42 for all elements of $R$ and $S$, we output $|R| \times |S|$ tuples. It is ...


3

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 reachable from x by following edges in the graph -- that's known as a reachability query. (And symmetrically, you also want to know whether x is reachable from y -- ...


3

An ip address has two parts: the address and the netmask. The address is just a 32-bit binary number. E.g. yours: 00010000.00011011.00011000.00000000 00010000.00011011.00011000.01000000 00010000.00011011.00011000.10000000 However, these addresses are very precise, and without any further information point to exactly one address. But we want to be more ...


3

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 Award Edgar F. Codd, Codd, E. F. “A Relational Model of Data for Large Shared Data Banks.” Communications of the ACM 13, no. 6 (June 1, 1970): 377–87. (...


3

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 (classical) logic there are rules like De Morgan's rule which says $\neg(P\land Q)\equiv(\neg P)\lor(\neg Q)$ and many others that allow you to move negation either ...


3

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 operation returns an empty set or not (for instance because the join condition is not satisfied by any pair of tuples). So, if this hypothesis is true, the ...


3

If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification: @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> . @prefix voc: <https://example.com/vocabulary#> . @prefix : <https://example.com/instances#> . :Triple42 rdf:type rdf:Statement . :Triple42 rdf:subject :...


3

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 following one: { A B C → D A B C → F D E F → A D E F → C D → B } From these dependencies we can see that E must belong to all the candidate keys, since it ...


3

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 steps to find the result: simply execute the operations in the correct order to produce the result. In contrast, in an expression of a calculus based language, ...


3

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 just be explicit about how you are using the word. That's probably best in any case if this is critical. A rose by any other name would smell as sweet. (...


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