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
0answers
27 views

Relational Algebra: set theoretic definitions for typical operations?

Wiki has set theoretic definitions of relational algebra used in databases. The typical set operations are missing and I'm trying to piece them together. Does anyone know how to define the $\cup, \...
1
vote
0answers
6 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 ...
0
votes
0answers
7 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 ...
0
votes
0answers
12 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 ...
0
votes
1answer
23 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$$\...
1
vote
0answers
22 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 ...
0
votes
1answer
19 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 ...
0
votes
0answers
17 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. ...
1
vote
1answer
23 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 ...
3
votes
1answer
58 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 ...
1
vote
0answers
14 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 ...
1
vote
0answers
110 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 ...
0
votes
1answer
56 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 ...
2
votes
1answer
37 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 ...
0
votes
1answer
73 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, ...
1
vote
1answer
53 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 ...
2
votes
1answer
63 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 ...
1
vote
0answers
252 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 ...
0
votes
2answers
279 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: ...
0
votes
1answer
35 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 ...
0
votes
1answer
47 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 ...
2
votes
1answer
56 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 ...
0
votes
0answers
34 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: ...
0
votes
1answer
29 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 ...
1
vote
0answers
31 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 ...
1
vote
2answers
31 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 ...
1
vote
0answers
14 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 ...
0
votes
0answers
21 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 ...
2
votes
0answers
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 ...
1
vote
1answer
38 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 ...
2
votes
0answers
33 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 ...
0
votes
0answers
48 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 ...
0
votes
0answers
59 views

A necessary condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute

I will state the complete question now, since it did not fit in the title. Is the statement given below correct? A necessary condition for a relation to be in 2NF but not in 3NF is that some non-...
0
votes
1answer
105 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 ...
1
vote
1answer
40 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 ...
0
votes
1answer
186 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 ...
0
votes
0answers
41 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 ...
0
votes
1answer
23 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 ...
0
votes
0answers
20 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. ...
1
vote
1answer
43 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(...
1
vote
0answers
27 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. ...
0
votes
0answers
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 ...
1
vote
1answer
100 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 ∪ (...
1
vote
0answers
51 views

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

My understanding is as follows: ...
1
vote
0answers
35 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 ...
0
votes
1answer
66 views

how two phase commit ensure serializability

Two phase commit is used in distributed transaction. For example, a client sends a transaction to two databases with a coordinator. step1: client get a global transaction id from coordinator step2: ...
0
votes
1answer
94 views

Databases and B-Trees: What are Keys and how are they related

I confused about the description & definition of "key" occuring as terminology for databases and b-trees. In first case dealing with theory of databases a key is defined as a choice for ...
3
votes
1answer
562 views

Confused between 2 phase locking and 2 phase commit

I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. ...
1
vote
2answers
1k views
0
votes
1answer
82 views

What is the advantage of Rete algorithm compared to relational database engines?

Per my understanding, the Rete algorithm and relational database engines essentially solve the same problem: answering to a certain query about a (large) set of relational facts. To me, the Rete ...

1
2 3 4 5