Questions tagged [database-theory]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
393 views

Difference between the Cartesian product in set theory and in relational algebra

What's the difference between the Cartesian product in set theory and in relational algebra? The Cartesian product in set theory is defined as: $$A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\...
0
votes
1answer
34 views

R-Tree multipath search - remember the path?

R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we ...
0
votes
0answers
99 views

Combining Ontology and Relational Databases in Question Answering system

I'm introducing to the Natural Language Processing field and it's application. I'm planning to build a question answering system for a project, but some approaches are making me a bit confuse about ...
1
vote
0answers
65 views

Need help with functional dependencies (Database Theory)

I'm trying to understand functional dependencies in databases. Let's say, there are 3 tuples in an instance of a certain relation S as shown below. I'm trying to determine if a certain functional ...
0
votes
0answers
39 views

Why are the 1st 2nd and 3rd normal forms ignored in some database books/courses?

Why are the 1st 2nd and 3rd normal forms ignored in some Database books/courses? specifically: https://lagunita.stanford.edu/courses/Engineering/db/2014_1/about and https://www.amazon.com/Database-...
2
votes
1answer
153 views

When an ISAM index is built, how is the number of leaf nodes per index node (the “fan-out”) calculated?

I asked this question on DB.SE but it didn't get any traction, so I'll ask it here... The following statement is in the Ramakrishnan text (2nd ed. page 252): (emphasis in bold is mine) The non-...
0
votes
1answer
39 views

Why is a set of attributes X not a key if X → Y holds but there exists a strict subset V of X where V → Y?

Apologies if I butchered the question, I wasn't quite sure how to word it. In the Ramakrishnan text (2nd edition) on page 423 (in the section on functional dependencies) this statement is made: If ...
0
votes
1answer
600 views

How are quantifiers meant to be used in tuple-relational calculus?

(apologies for the incorrect tag, there was no relational-calculus tag) In this lecture video the following tuple-relational calculus formula is given: $\{ P | \exists S \in \text{Sailors} ( S.\text{...
1
vote
1answer
115 views

Ambiguity in choosing the best ER model

I am actually little bit confused when I am reading through the text - Database system concepts by Henry F. Korth and others I won't be able to understand one thing, which one of the following models ...
3
votes
1answer
568 views

How to evaluate relations in a DAG?

To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify. ...
4
votes
1answer
2k views

Time Complexity of Sort-Merge Join

According to this German Wikipedia article, the time required to merge relations $R$ and $S$ is $\in \mathcal{O}(|R| + |S|)$ if both relations are already sorted. [Note: You don't really need to read ...
4
votes
2answers
146 views

Measuring availability from CAP theorem

I wonder how to check availability property from CAP theorem. Consistency check is conceptually easy: if at least once somehow same query at the same time returns different results, then the system ...
0
votes
2answers
42 views

What is this type of consistency called in DataRetrieval?

I am trying to find the name of this feature that is implemented with SQL Databases: Given a Record $R^1$ in table having two values for two different fields, e.g. Let value of field 1 $F_1$ be $V_1$...
0
votes
1answer
487 views

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

The R-Tree creates 'rectangles' to index 2D data. How is their size calculated exactly? What happens to the performance by changing this parameter i.e. the size of this rectangle/MBR? Number of ...
0
votes
0answers
24 views

How many passes does it take to join 2 relations of fixed size with M buffer blocks?

So let's say 2 relations, B(R) = 200,000 and B(S) = 300,000. The memory buffer is M = 400 blocks. How many passes would this take to join? Notation:
3
votes
0answers
81 views

Wikipedia on MVCC

I read about Multiversion Concurrency Control in Wikipedia. They say that every piece of data in DB has a Read Time Stamp (RTS) and If transaction Ti wants to Write to object P, and there is also ...
1
vote
0answers
229 views

Relational algebra for multiple legs of a flight

I'm trying to write the relational algebra for a problem related to this schema: I want to do the following: For each flight list the departure airport code for the first leg of the flight and the ...
1
vote
0answers
160 views

How to find the least optimised database query?

A library uses a relational database to store data about library books, their members and lending (books, which are currently borrowed). The database relations of this system are given below. Lengths ...
2
votes
2answers
150 views

Doubts abouts join implementation

I'm studying advanced database and I can not understand some concepts related to the join. I hope I'm in the right place to post my doubts, otherwise I'm sorry. I realized that to make the equijoin ...
0
votes
1answer
61 views

Finding alternative way of combinatorial counting

The question is related to databases: There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are? I thought if any one of the $(n-...
0
votes
1answer
329 views

Joining tables with minimum number of joins

I am working on a generalized problem where I am given only schema definition of multiple tables that i have. Now i have to retrieve certain columns by joining multiple tables such that number of ...
0
votes
2answers
248 views

Term for incorrect primary key

From a database theory point of view, what term can be used to refer to a key that does not violate the rules of the engine within which it is implemented, but fails to conform to any sort of ...
2
votes
0answers
56 views

How to build a reliable bank transfer? [closed]

I recently came across a problem where I was charged $50 by a merchant with my bank card but there was a communication error, so the money was taken from my account but never arrived in the merchants ...
-4
votes
1answer
512 views

Use examples to identify the need of join dependency

Use examples to identify the need of join dependency. This is what I have gathered from different website's. SQL joins are used to combine rows from two or more tables. A Join Dependency (JD) over a ...
8
votes
3answers
2k views

What does this definition of a Primary key mean?

My text book gives the following definition of a primary key in a relational database, which I don't entirely understand. Help would be greatly appreciated. Let $R$ be a relation. Then the primary ...
1
vote
0answers
215 views

Finding smallest canonical cover from given set of functional dependencies

I did not find any book discussing this but I came across the problem. The given set of FD was: $F=\{B\rightarrow A,D\rightarrow AC,B\rightarrow C,AB\rightarrow D,BC\rightarrow D\}$ Surprisingly the ...
2
votes
0answers
80 views

Are these two definitions of 2NF database normal form equivalent?

I came across following definition of 2NF normal form: A relation schema is in second normal form (2NF) if every nonprime attribute is not partially dependent on any key of R. Then the book ...
3
votes
1answer
6k views

When is relation in 3NF but not in BCNF?

A book by Korth et al. defines BCNF as follows: A relation schema $R$ is in BCNF with respect to a set F of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, ...
0
votes
0answers
38 views

Proof of RAP-derivation sequence for a set of functional dependencies in relational databases

I'm reading David Maier's outstanding but out-of-print book on relational databases (the book,"The Theory of Relational Databases", is available online from the author's website http://web.cecs.pdx....
1
vote
0answers
46 views

How do decompose this relation from 3NF to BCNF?

Given a relation with attributes { A, X, Y, Z } and functional dependencies $AX\rightarrow Y, AX\rightarrow Y, Y\rightarrow A, Z\rightarrow B$, I would think that this would be in 3NF because there ...
4
votes
1answer
97 views

why should I go for logistic regression?

I am a student working on a Database management project with a bit of Python coding involved. The project is about Review Analysis.Basically I am trying to read a review and determine how good or bad ...
2
votes
2answers
54 views

Restricting capabilities of admin role in database schema

Suppose I have to design database for learning management system. Which will going to have user having roles such as admin, teacher, tutor, student etc. In a system student can submit solution for an ...
0
votes
1answer
2k views

Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

schema(author)={name, newspaper} The table contains a list of authors. Each author works for a newspaper. So a single newspaper may employ multiple authors. How ...
1
vote
2answers
145 views

How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the ...
0
votes
0answers
36 views

Fundamental representation of data relationships?

This is an offshoot of this question Which is more fundamental: key-value or subject-predicate-object? Is there any fundamental, hypothetical or practical, representation of data relationships? Both ...
1
vote
2answers
556 views

Which is more fundamental: key-value or subject-predicate-object?

There seems to be two approaches to store data in NoSQL databases: Key-Value - The Key is usually stored in a hash-table referencing a ...
3
votes
1answer
695 views

Keeping a binary search tree by splitting nodes (like a B-Tree)

A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root. Can the same technique be used to keep ...
0
votes
0answers
679 views

What is the difference between physical level and internal level of a database according to ANSI/SPARC?

According to ANSI/SPARC model a database consists of three (or four?) levels. These are internal (and/or physical?), conceptual and external levels. Most information resources say like physical and ...
0
votes
2answers
4k views

What is the difference between F+ (closure of F) and F* (cover of F) for Functional Dependencies?

F+ and F* is defined as follows: F+: closure of F F+ = {fd | F |= fd} Set of all FDs deduced from inference rule (normally: Armstrong axioms) F: cover of F {fd | F |- fd} cover of F Set of all ...
1
vote
1answer
202 views

Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$. The modified algorithm ...
0
votes
3answers
148 views

Relational query for universally quantified formula

My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France. I received the order to formulate the query: "find all users ...
3
votes
0answers
93 views

Describe data structure using equations

Good afternoon. At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing. The input is basically a dataset formed by ...
1
vote
1answer
2k views

Does the conservative two phase locking protocol produce cascadeless schedules?

Let us consider the following schedule : \begin{array}{lcr} \mbox{$T_1$} & \mbox{$T_2$}\\ \\ \mbox{lock-exclusive(a)} \\ \mbox{lock-exclusive(b)} \\ \mbox{read(a)} \\ \mbox{a=a+50} \\ \mbox{...
3
votes
1answer
119 views

State of the art time complexity for getting (tree) descendants by type/attribute

Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only ...
1
vote
0answers
6k views

Difference between conflict serializability and view serializability

In my understanding both of them can be converted to serial schedules. (This helps with consistency by isolation property while also giving the performance boost by concurrency). I'm unable to ...
2
votes
0answers
104 views

how to compute functional dependencies and MVDs after decomposition?

Let's say we have a relation $R$ with a set of functional and multivalued dependencies $F$, and we found a dependency that violates some normal form. Then we decompose $R$ into $R_1$ and $R_2$. How to ...
1
vote
1answer
1k views

A schedule is not conflict-serializable. Is it serializable?

While reading this solved quiz on concurrency control, I got stuck on exercise 2, which reads as follows: 2) Consider the following schedule: S: r1(X), w2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z),...
2
votes
0answers
144 views

Conjunctive Regular Path Queries and Subgraph Isomorphism

How do conjunctive regular path queries and subgraph isomorphism relate to each other? It seems that conjunctive regular path queries are a specialised form of subgraph isomorphism. The follow is ...
3
votes
1answer
111 views

Algorithm for automatic/optimal database joins?

I'm curious if there is existing literature or well known algorithms out there for a problem I am working on. Given a normalized relational database with valid foreign key constraints and a list of ...
7
votes
1answer
610 views

A relational algebra extended to model the full DML (“CRUD”) domain

There are multiple references about the relational algebra for modeling queries (SELECT) but I have found very very little on the expanded algebra that would ...