Skip to main content

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
-1 votes
0 answers
21 views

Is it allowed to embed SELECT condition into Theta Joins?

Consider the following two relations: $\textbf{geoRiver}(River, Country, Province)$ $\textbf{river}(Name, Lake, Sea, Length, Source)$ Is this expression a legal expression in Relational Algeba? $\...
Yuirike's user avatar
  • 29
0 votes
0 answers
13 views

Datastore supporting TTL with range queries

We have a data access pattern in which we need to get users added in the time range say timestamp-1 to timestamp-2 and we don't want to keep older data say max 1 day, so DB should have an inbuilt ...
tusharRawat's user avatar
0 votes
0 answers
9 views

Clustered and Unclustered Indices non-key lookup costs and query plan

So I am working on query plans and understanding the I/O cost model for Clustered and Unclustered (non-clustered) B+-tree indices for database relations. The scenario is I want to do a lookup for a ...
revision's user avatar
0 votes
0 answers
25 views

How does waiting 7ms and atomic clock help GCP spanner create external consistency?

My understanding why distributed transaction need synchronized clock is the following Assume NTP max drift is 250ms ...
olaf's user avatar
  • 101
0 votes
0 answers
6 views

Datalog+- doubt about semantics and complexity

I am reading about Datalog+- (e,g, https://ieeexplore.ieee.org/abstract/document/5571709), and I have a doubt about its semantics, and about the complexity of query answering. In Datalog+-, you write ...
441Juggler's user avatar
0 votes
0 answers
21 views

Restaurant Galaxy schema

I want to make a Galaxy schema of a Restaurant. There are 2 fact tables sales and purchases. sales are related to customer and purchases to supplier of ingredients. Now my question is how can i make ...
MUHMMAD MURTAZA's user avatar
0 votes
0 answers
17 views

This diagram serves to determine the components of a data entry in my database. What is the name of this type of diagram?

To properly insert a data entry in my database, I have to reach the last box in this diagram. A box represents either a flag or a data structure that participates in determining a single entry. What ...
shintuku's user avatar
  • 101
0 votes
0 answers
19 views

Secondary Memory Data Structures and allocation strategies for intermediate query results

Despite a huge amount of literature regarding table representation and indexing in secondary memory (also including database books), I found no information on how relational databases represent ...
jackb's user avatar
  • 101
0 votes
0 answers
54 views

Proof that 2 phase locking produces order preserving Conflict serializable schedules

In the book Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery there is a theorem stating that Gen(2PL) ⊂ OCSR. Can some one help to guide on ...
Abishek0398's user avatar
0 votes
1 answer
110 views

ER model cant understand where I am wrong?

I am studying this ERD: The bank and the customer are obviously strong entities because they are a bank and a person. The bank branch is clearly a weak entity because it depends on the bank ...
Volpina's user avatar
  • 97
1 vote
1 answer
193 views

How are blind writes recoverable in a transaction schedule?

Consider the following schedule - T1 T2 R(A) W(A) R(A) W(A) Commit Commit I understand that this schedule is non-recoverable, because if ...
Kushagr Jaiswal's user avatar
-4 votes
1 answer
66 views

Real world example of complex foregin key references

Give a real world, normalized example where table T1 has primary key (A, B), T2 has primary key (B, C) and T3 has primary key (A, C) and table 4 has a primary key (A, B, C) where (A,B) is a foregin ...
molikto's user avatar
  • 75
0 votes
0 answers
42 views

Surrogate key often break BCNF?

...
mask22kksk's user avatar
0 votes
1 answer
80 views

Can a CPU instruction be split into 2 inputs?

Let's say there was a CPU with an input bus of 4 bits and the 4 bits are the opcode then the next 4 bits are the operand. It would just be an 8-bit instruction split in two. Is this possible and how ...
Thenboy's user avatar
  • 11
-1 votes
1 answer
87 views

2NF decompositions are dependency preserving?

I have read that 1NF, 2NF and 3NF decompositions are lossless and dependency-preserving. Consider this example on a relation $R(A,B,C,D)$ with functional dependencies set as $FD =${ $AB \rightarrow CD,...
Arun Madhav's user avatar
0 votes
1 answer
82 views

Check whether a decomposition is in 3nf

In a database systems course, we have been presented with the following definition for third normal form (3NF): A relation $R$ is in 3NF means: a nontrivial dependency $A_1,\dots,A_n\to B_1,\dots B_m$...
MiddleEasternPrince's user avatar
0 votes
0 answers
25 views

Implement this as Attribute or Entity Set?

I am creating a database on students' interests using the Entity-Relationship Model for a University assignment. Should I implement the circled stuff as attribute, or an entity set?
Suchet Saxena's user avatar
0 votes
1 answer
256 views

Checking if Schedule is recoverable

Consider the following schedule S.Is S conflict–serializable? Append the commit operations of these transactions at the end of the schedule in an appropriate order such that S is recoverable. How many ...
bigstreet's user avatar
0 votes
1 answer
104 views

Efficient storage of overlapping sets

I have a bag of sets which overlap, and I am looking for an efficient (if possible, optimal) way to leverage that overlap to store those sets with minimal space requirements. For example, consider ...
Aegis's user avatar
  • 101
1 vote
4 answers
69 views

How to index a table for fast intersection?

For example (and this is not my use case), imagine there is a set of 50 000 random natural numbers represented in decimal with 8 digits (in the range 00 000 000 to 99 999 999). We could index the set ...
Karl F.'s user avatar
  • 13
-1 votes
1 answer
47 views

How to derive selections from a series of numbers

I am sure this question has been asked, but I was unable to search for it in a manner that would give me the solution. So I will present it here. I seen this in another database years ago, and I want ...
Rick Scorpio's user avatar
0 votes
1 answer
101 views

Way to call and explain: "potentially infinite set of attributes" in databases

This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms. Let's say we have a database in which one ...
Lucas Johnston's user avatar
2 votes
0 answers
32 views

How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?

In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
Heiz's user avatar
  • 21
0 votes
0 answers
32 views

Which normal form is it in and How can we change it to 3rd and BC normal form

There is a relational schema :- person (id, name, phone no, address, email, position) so there will be the following functional dependencies ...
partyHatGuy's user avatar
0 votes
0 answers
23 views

Primary key's all field should contain value or not?

After reading a lot of materials related to the Primary key and Unique key, I am in doubt. Let us consider a primary key (AB) in table R (ABCDE). AB together can not be null as AB is a primary key. ...
A Paul's user avatar
  • 176
1 vote
2 answers
800 views

How do SQL databases query non-indexed columns?

I'm looking for some resources on what happens on the low-level with databases. I've found that indexed data is looked up using b+ trees, but could not find anything on non-indexed columns. Is there ...
seok's user avatar
  • 11
0 votes
0 answers
173 views

Is this decomposition in 3NF?

I have the following question: Consider relation R(A, B, C, D, E, F, H) with the following functional dependencies: A --> D, AE --> H, DF --> BC, E --> C, H --> E Consider three ...
rigidweight's user avatar
2 votes
0 answers
39 views

Primary File Organization in DBMS - Files of ordered records (sorted files)

"Fundamental of Database Systems", 3rd ed. by Elmasri and Navathe, page 136 says: "We can physically order the records of a file on disk based on the values of one of their fields [...]&...
GuestUser's user avatar
1 vote
1 answer
611 views

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

Say you are editing a document like a 1000 page book. There are 20 authors all working furiously to edit the book. Every day they are merging their changes 2 or 3 times with the main branch. According ...
Lance's user avatar
  • 2,243
2 votes
1 answer
204 views

How do distributed joins work in a distributed relational database system?

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
Lance's user avatar
  • 2,243
0 votes
1 answer
143 views

decomposition to BCNF

Given $R$=($A,B,C,D,E,G$), And $F_c$={$A$$\rightarrow$$E$ ,$E$$\rightarrow$$ACD$ ,$BD$$\rightarrow$$E$, $CD$$\rightarrow$$B$} Candidate keys are: $GA, GE, GDB, GCD$ Lets say I pick the FD $A$$\...
Omri Braha's user avatar
1 vote
0 answers
36 views

Advantages to create Male and Female entities separate from User rather than making gender a property in a database?

The screenshot is from Georgia Tech's CS-6400. The instructor was talking about inheritance of Sub-Types and Super-Types. My question is, why are Male and ...
Erin's user avatar
  • 13
0 votes
1 answer
129 views

How does partial word lookup work in an inverted index?

I know that an inverted index is a mapping from words -> documents. In the database I'm using, I'm able to do a search for ...
yrom1's user avatar
  • 3
1 vote
1 answer
111 views

Histogram representation of a database

I'm reading though The Algorithmic Foundations of Differential Privacy and the authors define a database in a mathematically convenient way. Unfortunately I'm a little confused about what the ...
robtimus_prime's user avatar
3 votes
1 answer
99 views

Automated Query Equivalence Solver (MongoDB)

The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...
himself000's user avatar
1 vote
0 answers
152 views

Understanding the behavior of Conflict Serializability and View Serializability with respect to blind writes

I have seen that most standard college textbooks of Database Management Systems use this method to classify whether a schedule is view serializable or not. I know the definitions of Conflict ...
Abhishek Ghosh's user avatar
1 vote
0 answers
815 views

Division in tuple relational calculus

$ \newcommand{\Set}[2]{% \{\, #1 \mid #2 \, \}% }$ I've been trying to find how to express relational division operation in tuple relational calculus. The only thing I found is this presentation ...
tomashauser's user avatar
-1 votes
2 answers
445 views

Intuition for a projection in tuple relational calculus

Let's have a relation $R = (name, surname, age)$. I want to obtain a new relation with only the $name$ attribute. In relational algebra I would simply do $\Pi_{\mathrm{name}}(R)$ but in relational ...
tomashauser's user avatar
2 votes
1 answer
204 views

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

I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a ...
user5721565's user avatar
0 votes
1 answer
171 views

Figuring out the equivalence between two definitions of "transitive functional dependencies" and intuition behind the intended meaning of definition

The definition given below is present in the exercise of the text Database System Concepts by Korth et. al. Let $\alpha$ and $\beta$ be sets of attributes such that $\alpha \rightarrow \beta$ holds, ...
Abhishek Ghosh's user avatar
1 vote
1 answer
98 views

Is this a mistake in the textbook? Fundamentals of Database Systems 7th ed

Aggregation is an abstraction concept for building composite objects from their component objects. ... the possibility of combining objects that are related by a particular relationship instance into ...
thenewboston2's user avatar
1 vote
1 answer
206 views

Order of query execution in the SQL

When a user writes a SQL query it needs to be scanned, parsed and validated. The question is in which order these three operations occurs in the process? Scanning, Parsing, Validation or any other ...
Coreman's user avatar
  • 27
1 vote
0 answers
949 views

Is it possible to convert any relational algebra expression into a relational calculus expression?

Let's for the sake of simplicity only focus on tuple relational calculus. Every relational algebra query can be broken down into the 5 atomic operations - projection, selection, set union, set ...
tomashauser's user avatar
0 votes
2 answers
345 views

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

Let's say that I am interested in discovering the smallest 5 numbers in a set of numbers. In SQL, this would work: ...
Chaos's user avatar
  • 111
0 votes
1 answer
95 views

In database buffering why is it important : no writes to a block (which is to be moved from the disk buffer section of main memory) be in progress?

I was going through the concept of database buffering from the Database System Concepts text by Korth et. al where I came across the excerpt below. The rules for the output of log records limit the ...
Abhishek Ghosh's user avatar
0 votes
1 answer
161 views

WAL rule requires only the undo information in the log have been output to stable storage, and permits the redo information to be written later

I was going through the "write-ahead logging (WAL) rule" from the Database System Concepts text by Korth et. al, where I came across the following excerpt: Strictly speaking, the WAL rule ...
Abhishek Ghosh's user avatar
2 votes
1 answer
104 views

Why does CLRS refer to the disk parts as pages rather than blocks?

I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters: In order to ...
2xMax's user avatar
  • 121
0 votes
0 answers
106 views

How to efficiently search a list of data structures with filtering support

I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like: ...
user3238415's user avatar
0 votes
1 answer
73 views

Is this relation in Boyce-Codd's Normal Form?

I thought I understood BCFN until I bumped into this example from my course slides. A relation in a library database contains what books are currently borrowed by what users. The relation contains ...
user2891462's user avatar
1 vote
0 answers
38 views

Which of the query approaches are more efficient?

There are two relations, registered(participant,topic) and fee(participant,amount). The primary key for registered is (participant, topic) and the primary key for fee is participant. The premise is ...
Swarnabja Bhaumik's user avatar

1
2 3 4 5 6