Mirror of the Rel4tion website/wiki source, view at <http://rel4tion.org>

[[ 🗃 ^yEzqv rel4tion-wiki ]] :: [📥 Inbox] [📤 Outbox] [🐤 Followers] [🤝 Collaborators] [🛠 Commits]

Clone

HTTPS: git clone https://vervis.peers.community/repos/yEzqv

SSH: git clone USERNAME@vervis.peers.community:yEzqv

Branches

Tags

master :: projects / naya /

math-basis.mdwn

Today, 2014-03-14, I began to go over query editors of issue trackers as part of my attempt to design a query editor UI. While examining Bugzilla’s editor, I asked myself a question: What is the scope of queries? What things can be done by a single query, and what things require that a client program processes the data by itself?

In order to answer this question, I need to understand the full scope of SQL and SPARQL, and understand what the procedural extentions of SQL do which SQL alone cannot. What a query is in the mathematical sense. Before I read, I want to try by myself.

In RDF, a database is a set of triples. A table with three columns: Subject, predicate and object. A query processor takes a query, examines the triple table accordingly and generates a new table, which it sends back to the client. This table doesn’t have to contain triples: It can be of any width. The query result can have a predefined size, i.e. concrete values, or it can have the “all X which satisfy P” pattern, which is variable-size.

The idea behind queries is to just explain what you want to know, and let the database take care of how to get it. A query is therefore a predicate calculus formula 𝜑(x₁, … , xₙ). However the model under which the formula is expressed is not the usual mathematical one, and requires technical definition. First, here is a reminder how things work in predicate calculus.

In order to be able to describe anything, we need a language to work with:

𝓛   = 〈𝓡, 𝓕, 𝓒, 𝜎〉

Each language 𝓛 is therefore a tuple containing the following elements:

Now we can have models under a given language:

𝓜   = 〈𝓦, 𝓡, 𝓕, 𝓒〉

Each language 𝓜 is therefore a tuple containing the following elements:

We can also have formulas under a given language. Each formula can be written using:

Later we will see how SPARQL can be mapped to these formulas, and whether is can be fully mapped. We’ll see which model is stronger in expressive power: SPARQL or formulas. Maybe people already did it while designing SQL or SPARQL - we’ll see. Before all that, I’d like to present the modified formal system made for Smaoin.

In Smaoin there is no single uniform world. Instead, the world is a union of several (disjoint) sets, each representing a different class of elements. These elements are called values and their occurences in formulas and queries are called literals. The sets comprising the world are called types. A type looks like this:

𝓣 = 〈𝓦, 𝓡, 𝓕, 𝓒〉

Where:

Here is an example for the Number type - it’s not necessarily the full canonical definition of Number, but it demonstrates the concepts:

N = 〈ℝ, {⩽, |, is-integer}, {+, *, ^}, {0, 1}〉

Now, although the definition may change later, for now, we can say a Smaoin Type System is simply a set of types with disjoint worlds:

S = {𝓣₁, ..., 𝓣ₙ}

Great. Now let’s examine the full scope of SQL and SPARQL, and see how they were planned and modeled and how the system suggested above performs in terms of expressive power, compared to them.

[See repo JSON]