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

learn more… | top users | synonyms

0
votes
0answers
33 views

Idempotence when replaying committed transactions

I'm trying to understand recovery mechanisms in transaction management. When a failure occurs then committed transactions are redone. Why is this required? How is this done repeatedly without ...
0
votes
0answers
20 views

How do I represent an outer join in tuple relational calculus?

I know how to make an outer join in relational algebra but not in relational calculus. let's say I have R1(A, B, C) and R2(D, E) how can I make an outer join between R1 and R2 with the condition A = D ...
0
votes
0answers
25 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....
0
votes
0answers
10 views

Entity relationship with two relationships between entities

I came across this slide and was very confused. This is the case of two relationships between the entities which are the opposite direction. This ERP for me seems to mean that all Staff manage ...
1
vote
0answers
13 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 ...
3
votes
1answer
55 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 ...
0
votes
0answers
9 views

Grouping operator in DBMS (Ɣ) is duplicate impervious. Why?

I'm reading Database Systems by Ullman where its mentioned that Ɣ is duplicate impervious. I dont understand why a simple group operation should cause elimination of duplicates. Aliter, Duplicate-...
2
votes
2answers
31 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
34 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 ...
0
votes
0answers
19 views

Is D join lossless with the given FD's?

If I have a relation schema R=ABCDE and the set of functional dependencies F = {B -> E, A -> D, D -> E}, and the decomposition of R into D={ABC, BD, ADE}. What is the way to go about answering this ...
1
vote
2answers
47 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
22 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
62 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
42 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
41 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
74 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 ...
0
votes
0answers
82 views

convert query to relational algebra

I have the following relational database schema: and I want to convert the following into relational algebra: List the names and phone numbers of the bidders who are not always affected by ...
1
vote
1answer
30 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
90 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
50 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
54 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{...
0
votes
1answer
29 views

How can I solve this Functional Dependency?

Consider R(A, B, C) with FDs F ={A→B, B→C, A→C} Prove or disprove F |= C → A There are 7 inference rules from Armstrong's Axiom. Which one is to use here?
3
votes
1answer
65 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
940 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
65 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 ...
0
votes
1answer
97 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
44 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 ...
1
vote
0answers
19 views
3
votes
1answer
71 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 ...
5
votes
1answer
409 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 ...
0
votes
1answer
42 views

Does XML covers the representation of any structured data and knowledge

I see nowadays XML is used to structure any file or data. It can represent the flat and hierarchical relations. It even can be used to show the parse tree of a sentence in a natural language. I am ...
2
votes
1answer
2k views

What is the difference between “strict schedule” and “cascadeless schedule”?

In database transactions theory, what is the difference between a strict schedule and a schedule that is merely secured against cascade aborts? Could you give an example of a schedule that is ...
0
votes
1answer
70 views

Database normalization impractical

After third form normalization, extra tables shall be created. And the functional determinant are used as primary key in the new table, as foreign key in the modified old table. My question is that ...
0
votes
1answer
2k views

What is the difference between a prime attribute and a proper subset of the candidate key? [closed]

I am taking DBMS classes and am currently studying the various normal forms. The following is the definition of a Prime Attribute I learned in class: ...
0
votes
0answers
52 views

Algorithm to test dependency preservation

Is there an algorithm to test whether the decomposition of relation $R$ into relations $R_1,\dots,R_n$ is dependency-preserving? In more detail, I am given a relation $R(x_1,\dots,x_m)$ on $m$ ...
1
vote
0answers
74 views

two phase locking and a contest question?

In 2PL (two phase locking), what advantage(s) does the rigorous model have over the strict model? I) There is no advantage over the strict model. II) In contrast to the strict model, it ...
0
votes
1answer
48 views

How can I formalize key value stores with set theory?

I'm currently developing a simple key-value NoSQL store and want to build its formal model. I found article about key value formalisation with category theory, but I'm interested are there some works ...
3
votes
0answers
133 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
3
votes
1answer
138 views

Rollback and Timestamp Ordering in Database

If we use the Timestamp Ordering for concurrency control in following scheduling: My TA says T2,T3,T5 is Run and T4,T5 is Rollback. I think it's false. any expert could help us?
2
votes
1answer
2k views

Finding the Candidate Keys of a Relation Using the FD's

I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below ...
0
votes
1answer
32 views

Can there be a strict transaction that is not 2Phase?

I am confused about the definition of a strict transaction. What is the difference between a transaction that is strict and a transaction that is both strict and 2 phase?
-1
votes
1answer
198 views

Naive Bayes MapReduce

I have the following question to answer in a MapReduce assignment sheet The Naive Bayes classifier is a widely-used tool for analyzing data. Consider a data set that has $n$ data items, each of ...
2
votes
2answers
317 views

When should you use the existential and universal quantifiers for Relational Calculus?

Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus? Given this schema: Hotel(hotelNo, hotelName, city) ...
1
vote
1answer
2k views

What is the difference between Strict 2Phase Locking and 2Phase Locking?

I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides, Two Phase Locking and Strict Two Phase Locking They have ...
3
votes
1answer
258 views

Partial order, total order, and version order in transaction histories

In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]: A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the ...
0
votes
2answers
62 views

Understanding transactions

In operating systems, Is a transaction a process? Are they the same concept? Does a transaction have the same meaning in database management systems, as in OS? A database book says A transaction ...
3
votes
1answer
390 views

Can a schedule with cyclic precedence graph still be serialisable?

We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict ...
5
votes
1answer
148 views

Why do relational databases use 2PC for distributed transactions over the likes of Paxos?

Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case ...
1
vote
0answers
44 views

1-serializability theorem in database theory

In the paper "MVCC@TODS'1983 by Bernstein et al.", 1-serializability ($1$-$\text{SR}$) problem is defined as a decision problem: To decide whether an MV (multi-version) log $L$ is $1$-$\text{SR}$. ...
0
votes
1answer
454 views

BCNF Decomposition: Confusion regarding given answer

I encountered the following question: Given a relation R(A, B, C, D) with the following functional dependencies: A -> B, C -> D, B -> C. The BCNF Decomposition of R is: A) {(A,B), (C,D), (B,C)} B) {...