# Questions tagged [database-theory]

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

269 questions
Filter by
Sorted by
Tagged with
21 views

• 108
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$...
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?
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 ...
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 ...
• 101
1 vote
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 ...
• 13
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 ...
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 ...
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 ...
• 21
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 ...
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. ...
• 176
1 vote
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 ...
• 11
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 ...
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 [...]&...
1 vote
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 ...
• 2,243
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 ...
• 2,243
143 views

• 1,132
1 vote
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 ...
1 vote
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 ...
• 27
1 vote
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 ...
• 129
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: ...
• 111
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 ...
• 1,132
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 ...
• 1,132
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 ...
• 121
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: ...
• 101