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

Is skipping writing no-op changes serializable?

Is this optimization safe to do in a serializable system? read value from db run it through some pure function that might modify the value if the new value is the same as the one we read, don't write ...
user avatar
0 votes
0 answers
25 views

Where is external sorting used beyond databases?

I am trying to find applications/systems that use external sorting techniques or avoid external sorting by using other methods to achieve a task. I know most relational databases (like PostgreSQL or ...
user avatar
0 votes
0 answers
17 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. ...
user avatar
  • 168
1 vote
2 answers
45 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 ...
user avatar
  • 11
0 votes
0 answers
38 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 ...
user avatar
2 votes
0 answers
31 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 [...]&...
user avatar
0 votes
1 answer
32 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 ...
user avatar
  • 1,871
2 votes
1 answer
33 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 ...
user avatar
  • 1,871
0 votes
0 answers
44 views

Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
user avatar
  • 1,871
0 votes
0 answers
13 views

How do relational algebra query analyzers generate query alternatives?

tl;dr: How does a query analyzer know how to modify a query to find a better one? I would like to implement a distributed database. I have figured out ways of storing data in a normalized form, and ...
user avatar
  • 1,871
0 votes
1 answer
37 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$$\...
user avatar
1 vote
0 answers
30 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 ...
user avatar
  • 13
0 votes
1 answer
30 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 ...
user avatar
  • 3
0 votes
0 answers
34 views

Can a conflict serializable schedule be irrecoverable?

According to this image taken from wiki. If a schedule is at (1) then it is conflict serializable but not recoverable. But according to this blog. All conflict serializable schedules are recoverable. ...
user avatar
1 vote
1 answer
33 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 ...
user avatar
3 votes
1 answer
63 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 ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
1 vote
0 answers
222 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 ...
user avatar
0 votes
1 answer
126 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 ...
user avatar
2 votes
1 answer
50 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 ...
user avatar
0 votes
1 answer
76 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, ...
user avatar
1 vote
1 answer
58 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 ...
user avatar
2 votes
1 answer
74 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 ...
user avatar
  • 21
1 vote
0 answers
376 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 ...
user avatar
0 votes
2 answers
291 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: ...
user avatar
  • 111
0 votes
1 answer
44 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 ...
user avatar
0 votes
1 answer
71 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 ...
user avatar
2 votes
1 answer
70 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 ...
user avatar
  • 121
0 votes
0 answers
47 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: ...
user avatar
0 votes
1 answer
38 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 ...
user avatar
1 vote
0 answers
32 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 ...
user avatar
1 vote
2 answers
33 views

Are joins/pullbacks of bloom filters possible?

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
user avatar
  • 131
1 vote
0 answers
17 views

Why two phase locking requires second phase not able to acquire lock for another object?

I wonder why two phase locking is designed in a way that as long as you release a lock, you cannot acquire any lock anymore, even for a lock on a different database object. Can't the scheme be relaxed ...
user avatar
  • 183
0 votes
0 answers
23 views

Hash tables for storing data in an application that supports partial search

Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is? I would have thought ...
user avatar
  • 143
2 votes
0 answers
25 views

Optional filters in relational database

I'm trying to create a procedure in MySQL/MariaDB with optional filters for each participating table. Assuming the tables are $A, B, C, \ldots$, each table may or may not be filtered, and the result ...
user avatar
1 vote
1 answer
43 views

Data model and database schema

I need to test my understanding of the difference between the data model and database schema. According to my understanding, the data model is a description of how the data will be stored and the ...
user avatar
  • 21
2 votes
0 answers
49 views

Database Access Cost Estimate - Linear Search over non-key attribute

How does one estimate the access cost for the below query given that the data is sorted according to a non-key attribute, that the data is not uniformly distributed across all possible values of said ...
user avatar
  • 123
0 votes
0 answers
52 views

How attributes helps us to allow column interchange in a relational database?

A relation on two sets $A$ and $B$ is defined as the subset of the cartesian product $$A\times B = \{(a,b),\ a \in A, b \in B\}$$ A database is also a relation and each entry is an ordered tuple ...
user avatar
  • 33
0 votes
1 answer
161 views

Relation is in 2NF or not?

Consider a relation R(A,B,C,D,E) and the only FDs, ABD->C BC->D CD->E These are the only 3 FDs. I want to know if the above relation is in 2NF or not. According to the definition of 2NF, a ...
user avatar
1 vote
1 answer
45 views

Resources about implementing a database table

I'd like to understand more how data can be stored on disk so it can be read quickly. I don't want to say database record because I'm not asking how to build a database. My question is closer to how ...
user avatar
  • 113
0 votes
1 answer
238 views

Find number of candidate keys given non-trivial functional dependency X->Y, where X is some set of attributes and Y is some prime attribute

In a relation R, if X is some set of attributes and Y is some prime attribute such that X uniquely determines Y is a non-trivial FD. Then is it true that R has at least two candidate keys? For ...
user avatar
0 votes
0 answers
43 views

External Sorting - Calculate passes with different number of disks

Let suppose that we have a file with n = 10^6 records. The block size is B = 10 records and we have available main memory m = 20 blocks. (Sorting with MergeSort) a) If we have 1 disk find minimum ...
user avatar
0 votes
1 answer
30 views

Is persistence a property of a database?

I was having a discussion in another forum on this topic, and I couldn’t get a satisfactory answer. Originally, a statement was made that a redis data store couldn’t be considered a database because ...
user avatar
0 votes
0 answers
22 views

RDF | If something is a rdfs:subClassOf of :Q can you infer it is also rdf:type :Q?

Given: :P rdfs:subClassOf :Q Can you infer the following?: :P rdf:type :Q I do not think you can, but I am not fully sure. ...
user avatar
1 vote
1 answer
44 views

Why we don't consider cycles in path problems?

I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(...
user avatar
1 vote
0 answers
39 views

What does mean by the independent columns in 4NF normalization?

For a table to satisfy the Fourth Normal Form, it should satisfy the following two conditions: It should be in the Boyce-Codd Normal Form. And, the table should not have any Multi-valued Dependency. ...
user avatar
  • 168
0 votes
0 answers
1k views

Using count() in Relational Algebra

Sell (Bar, Beer) I want a table in which the first column has the name of the beer and the second has the total number of bars which sell that beer, but I have no idea how to use count () in the right ...
user avatar
  • 1
1 vote
1 answer
141 views

Are intersection and union redundant? Possibility to get smaller output without negation?

I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me. ∩ and ∪ (...
user avatar
  • 13
1 vote
0 answers
59 views

In index allocation scheme, what parameters does the maximum size of a file depends on?

My understanding is as follows: ...
user avatar
1 vote
0 answers
38 views

What does the three schema architecture of DBMS refer to?

This architecture contains three layers or levels of the database management system: External level Conceptual level Internal level Can some one explain to me with a practical real example so that ...
user avatar
  • 11

1
2 3 4 5