# Tag Info

18

Categorical approaches to query languages is a bit of a niche interest, but I think it's a very interesting niche! Two of the key figures in this area are Peter Buneman and Torsten Grust. Obviously, they didn't do all the work, but if you start with their papers and trace out the citation graph, you'll get pretty good coverage of the area. The central ...

9

There are many research areas both in the theory and practice of distributed databases. One of the main practical challenges is that of implementing efficient concurrency control mechanisms for distributed and geo-replicated databases. In order to execute transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which ...

7

2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key." 1.44 bits per element is optimal. See "Hash, displace, and compress" "Improved Bounds For Covering Complete Uniform Hypergraphs" Data Structures and Algorithms , Vol. 1: ...

5

You did not say why you want a formalization, but presumably you want to do things with it, for instance prove properties of dictionaries and operations on them. In fact, your question can be understood in two ways: you want a mathematical description of dictionaries, or you want a computer formalization of dictionaries. For a computer formalization have a ...

5

Even testing whether $n$ elements are distinct is known to require $\Omega(n \log n)$ time on a model with some pretty reasonable restrictions. See, for example, Anna Lubiw, András Rácz: A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991).

4

It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the $2^n$ blow-up is unavoidable, just because you need to store all these values. However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the ...

4

To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.

4

1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times more expensive than 1.79 bits per key!

4

Here's a more reality-concerned version of tigreen's answer from the point of a person who actually makes heavy use of (relational) databases: The whole point and complexity of their application is to structure them in a way they'd require as little amount of joins for each and every ever-needed query as possible and that's why they actually Do Work. In ...

3

Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem: The problem $D\cup\Sigma\models Q$ is being reduced to a problem $D\models Q_\Sigma$. Several noteworthy things are happening here. The original problem is ...

3

I guess $((AB)(CD))$ is actually two ways, because you could do either $(AB)$ or $(CD)$ first.

3

Your problem is known to be NP-hard. See for instance Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge: "Exploiting hidden structure in selecting dimensions that distinguish vectors." Journal of Computer and System Sciences 82, pp 521-535 (2016).

3

The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible. To this end, it first decomposes SI into four properties: Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$ where, $ACA$: avoiding cascading aborts;...

2

There's a lot to unpack here and I don't know about Goguen's institutions. But perhaps I can give a partial answer to your question. Let's start with "simple interpretations" of RDF, as defined by the spec, forgetting about richer languages like RDFS or OWL. If we ignore IRIs and literals, as in the first part of your question, then an RDF model is a simple ...

2

Operations on a database are divided into DDL and DML. DDL are operations that alter the structure of the database. This includes creating/dropping tables, constraints, indexes, packages, views, dblinks, adding or removing columns to a table, changing object names and so on. DML are the operations that alter the data stored in the database. This includes ...

2

[in the article] there seems to be a confusion between dependency and functional dependency. The article is using "dependency" in the sense of 'Dependence Logic' here or here. As @Mark R points out. Specifically it's talking about the 'branching or Henkin quantifier'. Yes those are nothing to do with database theory Functional Dependencies. (They might be a ...

1

A co-Relational Model of Data for Large Shared Data Banks by Erik Meijer and Gavin Bierman, http://queue.acm.org/detail.cfm?id=1961297 Good article describing SQL and No-SQL databases as categorical duals.

1

It is common wisdom that database field is firmly grounded in the two math disciplines: predicate logic and set theory. However, this is very fuzzy observation, and reality is more subtle. The structure of the basic building block - relation - is described in set language, but that's about it. This is not really very insightful, because the whole ...

1

Some of the performance-related things you can objectively compare between different databases: IO complexity and computational complexity of different queries. E.g. there are different ways to do joins, sorting, different kinds of indices (including "no indices"), with objectively different asymptotic complexity. There are also column-oriented and row-...

1

Answer my own question: I am not sure with the ideas below. Both comments and answers from experts are highly appreciated. Any references are also welcome. I think the confusion arises from the fact that the two definitions of serializability ($\textrm{SR}$, for short) adopted in [Lin et al@TODS'2009] and [Berenson et al@MSR-TR'1995] are different. The SR ...

1

John Sowa (probably the foremost expert on knowledge representation) gives a thorough discussion of the subject here: Sowa

1

You are probably speaking about something like a process ontology. Lately, that research has focused (moved?) on semantic workflows, e.g. to model processes in science, related with reproducibility. Similarly, we can also find the application of ontologies to business processes. For more classical (lower level?) approaches, you may be interested in the ...

1

There is a distinction between LSM-Tree and Log-Structured Storage: Log-Structured Merge Tree (LevelDB, SQLite4, Apache Cassandra, and others). Log-Structured Storage (Berkeley DB Java Edition)

1

As a complement to Janoma's answer above: it's 'very good'--- from the point of view of implementation --- because given a FO-rewritable language, we can use the powerful engines (for evaluating queries directly against a database without dependencies) that are available. That's basically reducing the problem to evaluation of SQL queries.

Only top voted, non community-wiki answers of a minimum length are eligible