This paper analyzes the fatal drawback of the relational calculus not allowing relations to be domains of relations, and its consequences entrenched in SQL. In order to overcome this obstacle we prompousletitable index - an easily implementable upgrade to an existing data storage, which enables a revolutionary change in the field of data languages - the demotion of relational calculus and “tables”. We propose a new data languapgreawgmithatic typisation where types represent domain knowledge but not memory management. The language handsleets of tuples as first class data objects and supports set operation and tuple (de)composition operations as fluently as basic arith. And it is equally suitable for building-into a general purpose language as well as querying a remote DB (thus removing the ubiquitous gap between SQL and “application”).
• imperative DDL; • impossibility of relations between relations (which leads to non-homogeneous representation and undermines the relation abstraction itself, lowering the level of programming) • separation of the data language from the application layer language (which results in the development of a complete duplicate data scheme that exists outside the relational database and sufers all the drawbacks that the relational database tried to solve in the first place, besides doubling the development labour while adding nothing)
The proposed language aims to integrate with a general purpose language used for describing an application layer, in order to keep the relational data representation throughout all processing stages as the primary and the only data-model for a given program, accessible as first-class data-objects in a general purpose language (i.e. participating as arguments in native expressions).
The proposed language abandons surrogate and foreign keys (thus making the level of abstraction higher than SQL). The proposed data language is capable of dealing with relations between relations uniformly, by utilizing the proposed mechanism of multitable index, that in turn eliminates the need forjoins.
We have no choice but to focus on SQL, since it is the uncontested data language nowadays. SQL is a huge, unbelievable success. It is the most successful non-imperative algorithmic language ever existed [12]. Apparently, due to the lack of competition, but the fact had to be stated. For the same reason SQL remains basically unchanged, keeping initial imperfections and adopting only minor improvements (aka “features”). We witness the lack of meaningful development in the entire field of data-languages both within and outside SQL. SQL retains all its prime imperfections, and these are not implementation imperfections nor any quantitative deficiency, SQL contains fundamental mistakes in its very design stemming from its theoretical foundation, which turned several pathological use-cases of the language into a necessity of life. So much so it will be dificult to explain the severity of the pathology due to its prevalence in the population.
The apparent stagnation and growing malpractices gave rise to so called “noSQL” movement. Which is a destructive cult founded on pure frustration and the lack of positive insight, of which the very name is telling. If your data language is unsatisfactory, then by throwing it away you only solve the problems it created, but you do not solve the problem of accessing your data, that you have BEFORE the adoption of the data language. Nevertheless, this motion metastasized into the heart of SQL – ISO sanctioned XML contamination6[], efectively creating a rivaling alternative to SQL within SQL – an apparent sign of decay.
informative way of visualizing data structure.
A very typical approach to database design is Entity-Relation diagrams. It is very intuitive and
In the example above we have two entities and one relation between them. Let us map them into a relational database. The entities will be mapped as tables, and the relation will be mapped as a foreign key. Note, we are doing the most typical design procedure “by the textbook”.
_
By the same textbook, tables are supposed to represent relations! From the perspective of relational algebra (or relational calculus – at this point the distinction does not show up). thaend are relations. So, we have three relations: Category, Item, and the relation between them.
Why do we represent two of them properly (as it meant to be) and at the same time simulate the third one by programming a foreign key? Is there a real need for a non-homogeneous representation? Is the relatio n − − − any worse or better than or ? Can we define coherently a distinction between them?
For this particular disturbance of the representation we pay by lowering the level of programming (as in “low-level programming”). Foreign keys are very low-level relatively to tables. Compare a table representing a relation versus a foreign key representing a relation:
Here you simply declare: these two attributes constitutes a relation. You do not care how the association between them will be built and maintained. You can freely manipulate (p, a)irs and apply relational operations to the relation .
Here you have created a fake attribu.te . You have defined its type which have no correspondence to the domain knowledge – it is a surrogate type – whereas the domain knowledge is “item belongs to category”, it is not integer. Then you command your RDBMS to check your input in order to keep obvious garbage out (in other words, t h is directive defines a subset of the integer, making the type of this fake attribute more relevant). Thus you have manually created a relation! You involve yourself in the very internals of its representation. The maintenance in principle is up to you, although the machine agrees to assist by means of directive, the interpretation, however, is entirely up to you – the system does not recognize this relation as a relation. You can not apply relational operations to it.
A join creates a relation from existing relations. At first glance, it looks a reasonably useful operation. But the decades of practice reveal that a resulting relation does always pre-exist its formal “creation” by joining. Let us select something from the first example ⟶ :
This “newly created” relatio(n., .) was already hidden inside our database behind the foreign key (underlined). It is not new information created inside the database, this information had been put inside the database on purpose. Every pair of tables you ever join, you manually MADE JOINABLE! The join operator merely legalizes a hiddfoerneign-key relation as a first-class relation. A join is nothing more than A CONVERSION between these two ways of representing a relation.
But this trivial operation comes with nontrivial cost. First it takes a significant part of programmer’s labor to make all joins precisely predictable. A programmer must make sure all joins will result in a set of relations that are meant to be stored, and no join will ever reveal any new information. Then a programmer is forced to codify the conversion routine itself for many relations separately. And ifnally, in runtime, join is a resource consuming operation, perhaps the heaviest operation in any typical usecase.
Multiply the runtime price for the amount of times you access thojosiens, because the results are being thrown away every time. So you need to pay the price of join every time you access such relation. You keep converting your hiddefnoreign-key relations time and again.
And to add insult to injury, those costly results are already known to you! Your database has been designed this way that you know what comes from a join. You pay repeatedly for something you already have and always has had!
All this time ajoin solves a technicality problem that has nothing to do with the domain knowledge. Some minor inconvenience of internal representation of relations somehow became a significant part of supposedly high-level programming and legally consumed a lion share of runtime.
Because foreign keys are not capable of representing many-to-many relations, there is another alternative representation for relations: link-tables. It is also a low-level simulation of relations, that compromises the idea of RDBMS, and it imposes some extra cost. Here is the simplest case of a relation many-to-many: _ The most recommended mainstream way to represent it in terms of tables is a link-table: ...
Let us select genres of a book X:
_ , the dimension (,
) bigger search space than needed!
Nothing unusual, all three tables properly joined according to the foreign keys provided. But, look, is a relation on the Cartesian product of and . We need to perform a search of . What do we do in the select above? We produce a Cartesian product of , and _ itself. And then we perform a search of the dimensio(, n) 2 – twice What have we done?! We represented a relat ion _ as THREE formally independent relations.
One proper table-relation plus two foreign-keys, that require special costly treatment to be accessed at all. And this is formally the best practice, because it is the only way to describe such a relation in terms of relations as implemented in SQL. There are of course other methods,asrarayys, that result in non-relational methods of querying data, thastelaect does not cover.
Please note that in this representation the foreign keys on their own do not represent any domain knowledge relation. It is semantically a diferent role of a foreign key – not all your foreign keys correspond to a relation, and you must be aware of that – do you have a facility in SQL to distinguish these important usecases? Ah! Sweet confusion piles up!
Some RDBMSes introduce subclasses and inheritanc9e].[Needless to say that a subclass is a relation on a class, therefore, we have another rival representation. How many have you counted already?
Some RDBMSes introduce complex types, arrays, collections (a.k.a. “nested tables” N11B]!)w[hich are relation representations too. Take a look at oracle documentation: ---- a collection is defined as:
e_name VARCHAR2(53), s_sec VARCHAR2(11), addr VARCHAR2(113) ); ---- You can create a table with this object
This is a relation, no more and no less. So far we have SEVEN alternative representation for relations, of which only one enjoys availability of relational operations provided by so called RDBMSes.
Which representation to choose for a particular relation? Is there any method to choose representations from this multitude? Why so many representations after all?
The “why” question has an easy and obvious answer: because the notiontaobfle was never satisfactory for the role of a relation. All those “improvement” eforts had to be strongly motivated by the need to represent relations – shoultadble sufice, collections would never be born.
A typical RDBMS suggests the following mappin g:→ ; → . Note that a table can not adopt another table as an attribute. Therefore, there simply is no room for relations between relations. Taking in account that a typical domain knowledge contains a whole hierarchy of relations with the majority of them being relations between relations, with tables we can represent only SOME of relations for any given facet of knowledge. Once we represent a relation with a table we prevent table representations for all relations that includes the current one in their domain, and all that are included in the current one’s domain. The representation of the former takes link-tables and foreign-keys. The representation of the latter takes complex types and collections.
This is why we are stockpiling alternative representations. And it is not a solution at all. An RDBMS controls relations represented as tables, which are a mere part of a data model, which consists of many more relations having alternative representations, so that our data model resides partially (and mostly) outside a system designed for proper maintenance of the data-model.
At this point the very name “RDBMS” loses its meaning.
Any facet of real life knowledge is not a plain set of relations, it is always a hierarchy of relations. Only a minority of relations are leaves of this hierarchy. Typically a majority of relations adopt other relations as domains. For a meaningful system of managing a relational data model, first of all, we must make possible relations between relations.
Our language must contain the following closure (for definitions we use intuitive BNF-like notation
[
This is very important from the standpoint of the set theory that a relation (being a set) might play a
role of a domain. Exactly this is missed in relational calculus and relational algebra as defined by Codd
in [
Let’s say we have a binary relati onbetween sets and : 2 3 8 9
Assuming we already have sets , somehow represented, we need to represent the legs of the graph. Apparently the relation graph’s legs comprise a finite set, and any finite set can be represented as a set of integers, so we can represent our relation graph as:
Nothing is easier than creating an index for a finite set of integers: 25
75 12; 13 48 49; 73 99
This index (by-design) represents the graph of the relatio.nAt the same time it is merely a regular featureless index, like any other index in your RDBMS. Wher eaissa “horrible” many-to-many relation. And it is being represented by a single trivial index.
From an alternative vantage point, the primary purpose of a relation graph is to answer the question: whether a tuple is a member of the relation – this question an index is supposed to answer too. A graph and an index share the purpose and share representation. For all practical intents and purposes: a
But we did not impose any restrictions on the domai ns and – these are just sets (we merely enumerated them with integer keys) – therefor e, can be relations.
Thus we have created a many-to-many relation between relations that does not require neither link-tables nor joins but a SINGLE INDEX. An index that possesses no single feature impossible for any relation graph IS an index.
RDBMS to maintain this index.
Nothing prevents this index from holding data-storage node references. Nothing prevents your normal RDBMS. “multitable index”.
The only special feature of this index is that it has to hold two storage-node references at each leaf – nothing more. Generally these references point to diferent tables, so we called this type of index
Introduction of such index makes all the diference in the world for almost no price. A multitable index allows to store relations between relations, treat them as first-class relations, access them without joining (it basically stores the informationjoain re-calculates at every call). At this point the restriction for indexes to be limited to a single table looks ridiculously artificial and unjustified.
The language practices of SQL madrelations so strongly associated witthables that the notion of relation is totally replaced btayble. You sayrelation you mean table. The wordrelation has become a geeky euphemism for tables. It is grossly wrong, for all the reasons exhaustively described above.
Therefore, a huge mental paradigm shift is required, in order to reflect the mathematical reality inside a properly built RDBMS:
Indeed in PostgreSQL indexes internally ARE relations, already. Somewhat special, but nothing should prevent you from using them as described above, since an index is capable of storing all the information you demand from a very heavy join of two tables together with a link-table.
We need a language to be pure, simple, and coherent. Its notation must be clear, unambiguous, and intuitively human readable (but not mimicking a human language, in fact resemblance of a human language does only complicate understandin3]g).[Ideally, similar objects must be described by similar sentences of the language, while dissimilar ones be described by easily distinguishable sentences. Also, we want to keep a number of keywords and unique syntax constructs to the bare minimum. Since everything has been already invented, we will try to stick with s-expressi4o]nasn[d follow the functional style.
No more human language mimicking. Contrary to the creators’ intent, decades of human language mimicking, did not not make a single layman fluent in SQL. This handicap should not be carried any farther.
Relational operations to be written separately. We do not want to mix projection with other operation, and defer all the and up to the output formatting phase. Hopefully it will make the notation of data manipulation cleaner, at the same time the output formatting richer (as being freed from the limitations imposed by the data manipulation context).
Declutter the notation. We will keep the notation free from meaningless variety of separators – a space is enough. For example, if we want to construct a triple, we have to provide triple members (and optionally their order), like th(i1s,:2, 3) . The question is what information the comma symbol adds to this notation? The only right answer is: void. Because of this, we simply discard the garbage, so we got: (123) . This seemingly superficial change in fact is a very significant improvement to the syntax. It efectively removes the whole idea of “in between items”, which ordinarily causes whole series of tiny annoying problems (particularly nasty in machine generated scripting (beginning with “duplicate separator” (is a duplicate separator an error? could it have a meaning?))).
Make basic types and relations interchangeable. This is the pivot point of the language. It makes the language capable of expressing relations between relations.
Introduce variables and assignments. SQL does not provide a room for assignments, they are totally alien to the SQL’s structure, yet strongly demanded (recently intro ducedclause is a counter-intuitive assignment in essence). Our variables will be IMMUTABLE, will have a single transaction lifespan and visibility, will be interchangeable with relations in every context except for data definition, and will represent only sets of tuples. Perhaps, assignments have no need to be calculated immediately.
Make DML returning value. Since we have explicit output operations, and separated relational operations, and we have assignments, then we can avoid t h e clause altogether by making DML return afected rows. And since we may utilize a return value only explicitly, then we can just discard it by not utilizing it.
Respect the fact that a relation is a function of its primary key. Indeed we can treat them as functions all the way long and that gives us an opportunity to create a procedural language around the data sublanguage.
Keep types as few as possible. The epoch of counting bytes is over. There is no need in keeping several diferent types for integers, also we do not see any high level application for bitwise operations and related stuf. We now want computers to count their bytes (if they are concerned). On the other hand we provide a useful tool for constructing complex types of arbitrary complexity, namely relations – we do not need to anticipate all possible user’s wishes by maintaining a library of fancy peculiar types which will be rarely known and never used (because user’s wishes always prove themselves more peculiar than our wildest anticipation).
The language is completely NULL-free. The only known legitimate usecase of NULLS is an optional foreign key. But our language does not have foreign keys.
The language contains the following predefined basic types:
, , , , , is “infinite” as is a norm nowadays, no bytes counting, and such int efectively replaces fixed points, so we don’t even bother about fixed point types.
is a floating point type, and it approximates real numbers, sometimes this distinction matters, and you need a type that is not precise. So that the minimal set of numeric types is still two very diferent types, which diference goes beyond hardware limitations and software implementations.
is “infinite” (as in PostgreSQL [
is an arbitrarily rounded reference to a point in time expressed in units of currently standard calendar. The closest comparison is the PostgreSQL ’s [10], however, our is much better. Postgres loses the timezone information and it does not respect the fact that absolutely all timestamps are always rounded. Natural timestamp input is typically rounded coarser than an internal representation of a and the information of the user requirement for timestamp granularity is lost for Postgres.
Unlike Postgres, we preserve the timezone information, and we preserve the timestamp granularity. Our stores thetime, the timezone it was originally inputted in, and igtrsanularity – when it is “a year 1984” it does not become “1984-01-01 00:00:00.000000”, it remains “a timestamp given to the accuracy of a whole year”.
is analogous to PostgreSQL ’ s [10], but better – it does NOT share a lexeme with text constants (see5.2).
A calendar arithmetic should be stolen from Postgres because it is so far the only proper implementation of our calendar in the entire software industry.
In addition to these basic types one complex type could be useful enough to define him in the core language:
Where is a pair(, ) treated as a number by all numeric operations. Given our “infinite”
integers, a rational arithmetic covers literally all the holes b e tweaennd , because [
Such type poses a question though: Shall we throw out completely, in favour of , since can do everything with the same precision? 5.1.1. Automagic: mapping, flaetning, tuple simplification
The language is thoroughly relational – all data objects in the language are (they “are” in the sense of their treatment, you can safely assume a scalar is a set containing a single tuple of a single element, but it does not mean we actually implement all the overhead internally) sets of tuples, all of them. From that follow certain decisions: • The availability and the role and the appearance of Cartesian products and 5u.n3i.3o.ns • Automagicalmapping of functions [14]: a function (that is not defined as a folding function) if given a set of arguments applies to each element producing a set of results. • Automagicallist flattening , if a set is inserted into another set as an element a concatenation takes place instead, which fact is not even hidden from a user, since the only constructor of sets is the operation. A set of sets has no meaning in a relation context – if it does, there is a relational solution: tuples – a set contains tuples and tuples can contain sets, no flattening is called for (see example below). • Automagical tupledepth reduction: if a tuple contains a tuple as a single element the inner tuple is consumed the depth is reduced (see example below). Otherwise, tuples can contain tuples as elements, it is meaningful, no flattening occurs. • Operations of aggregation/grouping and their opposites should be defined. A result of aggregation/grouping is still a valid relational data object enjoying all the rights and opportunities. Example list flattening
Apparently the following two sets: [1 2 3 4] [[1 2] [3 4]] contain diferent information, even the amount of information difers (easy check: how many permutations are allowed in each case). But what is a semantic of this distinction?
When using these sets you have to imply some meaning into the very fact of their nestedness – meaningless structures are not allowed.
On the other hand, a relational language gives you means to write your ideas explicitly, by extending the members of the set, for example: [ {"shots" [1 2]} {"misses" [3 4]} ] now the inner sets can not be flatten with the outer set; not technically, nor semantically; members of inner sets difer in type from the members of the outer set.
Nevertheless a meaningful analogue of flattening is still possible, we can expand this “aggregated” set into: [{"shots" 1} {"shots" 2} {"misses" 3} {"misses" 4}]
Thus both flat and compact forms are legal and all the meaning is preserved (“despite” prohibition of sets of sets). In this light the abstract set of sets seems a mere artefact of a language, nothing more than a distinction between a NULL pointer and an empty array
Example depth reduction
Apparently nested tuples can express important meaning (as structuring a datum) in this example the dates member in diferent tuples – they are dates of diferent things, say a birth date and a nomination date.
Opposite to that, there exists meaningless configuration of nested tuples: {"John Doe"} {{"John Doe"}} {{{"John Doe"}}}
Adding depth without adding attributes does not add any new information to the original tuple. Therefore we perform automatic reduction of depth in this easily detectable case. In return this simplification gives us two neat features: • We can extract (with projection) individual elements (say a scalar) from deeply nested relations, loosing the depth information (i.e. a scalar will appear as a scalar regardless of the depth it was extracted from. • We can re-use the tuple constructor for type casting, since enveloping a datum into a tuple does not increase the depth, we can re-envelop a tuple into a tuple of diferent type to the efect of type casting (see5.3.2). 5.2. Lexic 5.2.1. Literals
The language is based on the following 11 lexemes: 7 literals, 4 pairs of brackets; and 2 separators.
Spaces and linebreaks are separators. Brackets separate lexemes too. A lexeme, unless quoted, can not contain separators or brackets. Beginning of an operator terminates the previous lexeme. No other separators exist.
Identifiers aka names, are used to designate types (among which are all relations (among which are all functions)). They are classical names with lowercase initials.
Nominators (formerly known as variables) to designate named data objects. They are classical names with uppercase initials.
NAME = [a-z][a-zA-Z0-9_]* VAR = [A-Z][a-zA-Z0-9_]*
Numerals, that represent constants of numerical types. They traditionally bear digit initials. Underscores are allowed to group digits.
NUM_DECIMAL = [0-9.][0-9._]*
NUM_BASE2TO9 = [
Text literals in double quotes with traditional backslash escapes.
TEXT = "[^"]*" // with backslash escapes (not shown here)
Date, time, and interval literals, in “graves” without escaping. Easily distinguishable from both numerals and texts by the leading character. The use of a quotation technique allows for spaces to be used in date-time formats.
TIME = `[^`]*` // `1984` // it is now a year not an integer // `456BC` // `+ 2days 7hours 11minutes` // `2021-02-20 18:41`
The temptation was strong to avoid keywords completely, still there are two words that are absolutely reserved forever and ever: BOOL = true | false
Operators are brief cryptic names for frequently used functions. They must have a non-alphanumeric initial that is not a quote-mark nor a bracket, they might contain letters, but not digits. This distinctive shape allows them to appear on a non-leading position in a s-expression, without being confused with arguments.
OPERATOR = [!@#\$\%\^\&\?~*+=<>:;,|\\/-][a-zA-Z_!@#\$\%\^\&\?~*+=<>:;,|\\/-]*
In order to focus on the data sublanguage we omit for now the definition of a program in the proposed language. Defining that, including the command grouping and structuring into transactions and routines would be premature at this point, since the big picture of the workflow is not complete yet.
On the other hand we attempt to define as clear as possible how does the language specify data structures and data access. Keeping in mind that all these “constructs” should be equally applicable to remote and local data, and equally palatable for a language with shared state data objects, as well as a language without state sharing.
Typographic Convention: We will type literal value of terminals in ”doublequotes”.
We will type names of terminals UPPERCASE, if their value is variable.
We will give lowercase names for non-terminals.
For brevity of lists definitions we extend our BNF-like notation with symbol:s::=... and ::=0... meaning arbitrary repetition of right-side, at least 1 or at least 0 times respectively. 5.3.1. Data definition definition ::= "relation" { NAME domains } definition ::= "domain" { NAME domains } domains ::=... domain domain ::= NAME:type // you can give names to domains domain ::= type // domains may bear type-names type ::= BASIC_TYPE_NAME type ::= RELATION_NAME
There are three classes of relations: ordi nary , , – all of them are first-class relations in every respect. A always contains all its possible tuples, similarly to a user-defined type in procedural languages, although from our vantage point a is also a user-defined data type of equal rights and opportunities, the only diference is that represents a user-defined subset of its type (i.e. requires a set of tuples to be ) and contains only those tuples that were by a user.
A is a relation that contains only tuples defined by the given expression (i.e. calculated). The additional diference is that you can explicitly specify its co-domain to be some arbitrary projection of the complete domain – i.e. a function represents a “shorter” type (The explicit split of the formal “relation domain” into “argument type” and “result type” also reflects the fact that in general a function specified as a computation procedure can not be reversed, thus making regular “selects” (potentially retrieving values of “arguments”) impossible, whereas the “result” alone retains full “selectability”), similarly to “return type” of a function in a procedural language. For the sake of completion, here is how we define functions: definition ::= "function" { NAME domains -> domains } heads definition ::= "fold" { NAME domains -> domains / init} heads definition ::= "operator" { OPERATOR FUNC_NAME } heads // to be defined later init // to be defined later
A that receives a set of its arguments automatically “maps” itself, producing a set of results. To cover the opposite behaviour a is introduced. A “folding” function (although enjoying equal rights and opportunities) if given a set of arguments always folds this set and produces a single result. are to be used in aggregates. Th e condition contains a definition and an initial value of the accumulator that passes the fold state between iterations. It is not supposed to be accessible from a call to a , a participates in a program as a with the specified domain and co-domain.
An open question is: (a) do we make a function’s domain type accessible by a name derived from the function name? (b) do we require explicit names for the domain and co-domain types to be defined prior to the function definition, so that a function always refers to named types (for an example usecase of type names see5.3.2)?
Example Let there be a tiny library: _ ℎ
The definition of this library will look like: domain {name first:text middle:text last:text} relation {book title:text ISBN:text} relation {writer name:text birthdate:time} relation {genre text} relation {department text} relation {author book writer} relation {book_genre book genre} relation {available book department}
Now let us illustrate another usecase for
definition: domain {point2d x:real y:real} domain {circle radius:real center:point2d} relation {my_circle circle}
In the example above circle is a set of all possible circles. Domains play a role of complex types. While my_circle is a set of user defined circles –- a user himself controls which tuples belong to the set. 5.3.2. Constructors
We construct a tuple simply by listing all its components in special brackets designating this is a tuple. constructor ::= { tuple } tuple ::=... value value ::= expression value ::= label:expression label ::= TYPE_NAME label ::= NAME expression // to be defined later
Tuples are allowed to have explicitly or implicitly named elements – exactly the same as in a definition of a relation. Elements will be referred to by their labels, either arbitrary names or their respective type names, for the purpose of unification (as in Prolog15[] and Erlang, but greatly enhanced with the tuples having named elements). This allows us to abandon all traces of positional referencing in all contexts. Tuples are still ordered but this order only manifests in its useful aspect: establishing correspondence between elements of two tuples, and this is achieved with the aidof – the rest of the information that an order of elements contains is not important for a user, and removed out of sight.
In addition to that, you can ensure “compatibility” of a newly constructed tuple with a predefined type: constructor ::= { TYPE_NAME tuple }
If the given tuple fails to unify with the given type the constructor returns an error. Apart from type assurance this form adds human readability in certain cases.
On top of it (due to automatic depth reduction) you can use the same type assuring tuple constructor for type casts: A := {int 1984} B := {text A} // result "1984" C := {time B} // result `1984`
The second necessary constructor is a set. We construct a set by simply listing its elements in brackets designating a declaration of a set. constructor ::= [ set ] set ::=0... expression
Our sets are relations, so that they imply that all their elements are of the same type. In order to make this requirement more clearly visible we allow type assurance for sets as well. This constructor will apply the type assurance to each element of the given set: constructor ::= [ TYPE_NAME set ]
Counter-example
Let us highlight the importance of explicit tuple constructors by looking at SQL, which is built around tuples but lacks syntax for constructing tuples. This situation leads to queries like that:
it says: x over w, y over w, z over w
because there is no way to say: {x y z} over w 5.3.3. Basic set operations product ::= { expressions } union ::= [ expressions ] expressions ::=... expression
A relational language can not survive without the basic set operations: Cartesian product and union – being as easily available as arithmetic operations.
We use the same brackets here, respectively. [A] designates a set. A{} designates a tuple. It must be obvious from the definition that the similarity goes beyond the syntax: a tuple constructor performs Cartesian product of its elements, and a set constructor performs a union of its elements – there is no need so far to invent any distinctions. Of course you can specify type assurance too. 5.3.4. Unification
The type assurance, and function calls, and the pattern matching in selections5.(3se.6e), are based on . Our unification procedure utilizes both labels and types of the tuple, ignoring the order, and in some cases ignoring arity. domain {name first:text middle:text last:text} // unifies with: {first:"John" middle:"Enoch" last:"Doe"} {first:"John" last:"Enoch" middle:"E."} {first:"John" middle:"Enoch" "Doe"} // the last is implied {"Doe" first:"John" middle:"Enoch"} // the last is still implied domain {point x:real y:real name:text} // unifies with {x:10 {real "19"} "point 10;19"} // type matters {x:"10" y:"19" "point 10;19"} // but labels take precedence // abbreviations are allowed {name f:"John" l:"Doe"} // is valid // as long as abbreviations are unambiguous
Label abbreviations are possible because of the very narrow scope of the labels, ambiguity is easily detectable. Since labels are used profusely, this feature becomes extremely time-saving. At the same time it allows to avoid abbreviating “field names” at the definition phase. You can aford names as verbose as necessary without cluttering the text of a program referring to verbose names.
The unification algorithm
Elements are consumed in the order from the highest to lowest priority: Label and Type match exactly Label match exactly and type casts Label abbreviates and Type matches Label abbreviates and Type casts Label empty and Type matches to a single element Label empty and last element and Type casts to the last remaining element.
Error is thrown: more elements in the given pattern than in the target a label in the pattern does not match nor abbreviate any target a label matches and the type fails to cast 5.3.5. Nominators
Giving names to subselects is a massive convenience, so much so SQL is developing this aspect for its entire history up to the “WITH” control structure. We decide from the start to structure the language is such a manner that a sequence of “assignments” is legal without any special tricks excusing such “assignments” from a context that prohibits them. assignment ::= NOMINATOR := expression
Example MYlist := [1 9 8 17] MYtuple := {"John" "Doe"} B := (book title:"1984") // B now represents this selection
After these assignments (within their visibility scope) you can treat the nominato rs , , as the objects they represent and put them in any appropriate context.
An assignment sentence DOESNOT necessitate execution of the right-side expression! The compiler knows if and when the assignment is used, keeping in mind the transactional context of the runtime, the necessity to execute anything occurs at well defined moments.
For purely aesthetic purposes, in case programs in our language eventually grow a habit for large multiline expressions, we must keep in mind the possibility to add postfix assignments: postfix_assignment ::= expression =: NOMINATOR
In a lengthy statement such assignment allows to put t h e it is most relevant for reading the text right below. case of a very lengthy expression that itself could be a control structure that returns a result and you want this result to be named and by the time you finished reading this expression the variable name it is assigned to goes far above...
INSTEAD on the very last line where you can provide this name right AFTER the present expression exactly at the moment when you finished learning the result of this expression and so timely you learn the name too end-case =: MYresult B := (foo MYresult) 5.3.6. Selection
When you write:
What information exactly does this sentence contain? The right answ er: – nothing else. In this sentence you point to a certain relation by name (the result could be directed to the output or another select, but this information is not contained within the sentence itself)
Since we know the information content of this sentence, we know how to say it in our language: (book)
This is how you access a relation – you simply call it by its name. Parenthesis here makes it an expression that is a data object as opposed to a type object. selection ::= ( NAME ) selection ::= ( NAME pattern ) pattern ::=... filter filter ::= conjunction filter ::= disjunction filter ::= value filter ::= func value ::= LABEL:expression value ::= expression func ::= LABEL:curry curry ::= (FUNCTION args) args ::=... value conjunction ::= { pattern } disjunction ::= [ pattern ]
A pattern attempts to match against the elements of the relation. If a value is provided it matches with the corresponding field if equal. If a function is provided it matches if computes to true, but this function must be curried down to the arity 1, and return boolean result. A set of filters matches as “OR”. Whereas a tuple of filters matches as “AND”.
example Dawkins := (writer {first:"Richard" last:"Dawkins"}) John_OR_Mary := (person first:["John" "Mary"]) Elder_J_OR_M := (John_OR_Mary birthdate:(earlier than:`1990`)) // same as Elder_J_OR_M := (person first:["John" "Mary"] birthdate:(earlier than:`1990`)) X := (person [{first:"John" birthdate:(earlier than:`1990`)} {first:"Mary"}]) //same as X := [(person first:"John" birthdate:(earlier than:`1990`)) (person first:"Mary")] // provided a predefined BIF function {earlier x:time than:time -> bool} ( ( x - than ) < 0 )
A must represent a volume in the domain space of the given relation. A selection expression returns all the elements that happen inside this volume. The simplest form o f a (apart from the empty pattern) is a tuple. A tuple-pattern unifies with some elements of relation, these elements will be returned. A complete tuple of the relation-type represent a point in the domain space and unifies with 1 or 0 elements. A tuple of a single element represents a hyperplane. A tuple of multiple elements represents an intersection of hyperplanes. Whereas a set within a pattern represents a disjunctive match (analog of SQL’s: “OR“, “IN”).
An important class of shapes can be expressed by means of adding up and intersecting such volumes – those boundaries can utilize indexes. It is huge class covering almost all usecases of a typical bureaucratic database, However, it is far from being complete, for example this selection can not express a half plane on a real plane that is bounded b+y = . This problem is still solvable, because there is no compulsion to put everything inside a “where” clause. You can define a function that computes + = (or any other hyperplane for that matter) taking the entire relation as an argument. relation {plot x:real y:real} function {foo p.plot -> plot c:real} {p (+ p.x p.y)} F := (foo (plot)) HALFPLOT := (F c:(greater than:0)) 5.3.7. Data management command ::= "add" content command ::= "remove" content command ::= "abolish" content command ::= "update" content replacement content ::= constructor content ::= selection replacement // to be defined later
This weird triviality comes from the fact that a constructor specifies type – so that the relation to which the command is issued is known from the type. In case a given tuple (say, passed from some previous routine) is not labeled with a type, it is always possible to do inline by wrapping it into a type-assuring constructor. Therefore the syntax of the command itself does not need to mention the type, it is either known or can be made known by treating the argument of the command.
And of course, a set is acceptable argument.
And of course, a command returns a result: the afected subset of the afected relation. B := add {book title:"1984" isbn:"094885858"} G := add [genre {"fiction"} {"sci-fi"} {"memoir"} {"documentary"} {"bore"}] PEOPLE := [{first:"George" last:"Orwell"} {first:"Richard" last:"Dawkins"}] W := add {writer PEOPLE} // adds all people as writers A := add {author B (W last:"Orwell")} S := add {book title:"The Selfish Gene" isbn:"098765"}
Similarly, a command needs to know “which records”, and since there is no preference as to how exactly they must be specified, as long as the provided datum unifies with the relation... The most straightforward way is to specify a selection.
TRACE := remove (author (name [first "Mary" "Jane"])) // removes all authors with first names "Mary" OR "Jane"
ℎ is a recursive version of members, instead of throwing an error.
The is exceptionally cluttered and burdensome with all its referen ces taond . By no means the proposed syntax is final. Please consider it as a suggestion.
. It removes members of relations referring to removed command ::= "update" content replacement replacement ::= constructor replacement ::= expression_with_special_namespace
Example update (writer {name last:"Dawwkins"}) {name last:"Dawkins"} // only the unified elements get replaced // referring "old" update (writer birth:(earlier than:1500)) {writer birth:(+ `13 days` <birth old>)} 5.3.8. Projections
Projections are also brackets. In the simplest case: projection ::= < fields expression > fields ::=... field field ::= NAME // where expression is typically a selection
Unlike other brackets, unlike selections themselves, the subject expression enters a projection at the last position. Is it inconsistency? No! In a selection the first word within its bracket designates the type of the result. Same with constructors, the type enters in the first position. A projection efectively alters the type of the subject expression, and the formulation of this new type is written i n the clause. So that in the proposed syntax of projections the type again is the leading member within the bracket. That adds some regularity for the reader, a human reader.
B := (book title:"1984") W := <writer (author book:B)> N := <name W> // the type is now {name first middle last} T := {x:10 y:19 name:"point" ref:`1546-12-12AD`} P := <x y name T> // dropped the "ref" field // nesting F := <first <name <writer (author book:B)>>> // more complex K := {name f:"J" m:"J" l:"Doe"} Q := {x:10 y:19 who:K} // type is {real real {text text text}} // let's extract x and m (from name) Mpart := <m <who Q>> Xpart := <x Q> R := {x:Xpart m:Mpart} // pretty complicated projection ::= < fields expression > fields ::=... field field ::= NAME field ::= NAME.field // where expression is typically a selection
In order to fight this complication it is enough to allow t h e specifications within projections to refer to subtype labels:
So the last example (that explicitly flattens a nested-tuple type) will look like: K := {name f:"J" m:"J" l:"Doe"} Q := {x:10 y:19 who:K} R := <x name.m Q>
There is nothing wrong with the dot-notation for nested namespaces. Also we allow abbreviations in this context too. 5.3.9. Grouping and aggregation
If you aggregate something in SQL and forget to “GROUP” unaggregated fields, it will very precisely report an error: “the fields x y z are not aggregated and should be grouped”. It knows exactly what ifelds must be grouped!!! Therefore, we must pursue some aggregation and grouping notation that does not demand this redundancy from a user.
It turns out, grouping snugs comfortably into the projection context. grouping ::= < fields \ fields expression >
We simply specify two subsets of fields: first those being grouped, then those that group them. From the information content perspective, we specify a subset of fields (same as in projection) plus a single split among them. The question which part of the slit should come first in the notation is open. domain {my_book title:text year:int author:writer} [my_book {t:"a book 1" 2021 (writer "Dawkins")} {t:"a book 4" 2024 (writer "Dawkins")} {t:"a book 5" 2025 (writer "Orwell")} ] =: B G := <title year \ author.name.last B> // [ // { [{t:"a book 1" 2021} // {t:"a book 1" 2024} // ] "Dawkins" // } // { [{t:"a book 5" 2025} // ] "Orwell" // } // ]
Since we successfully grouped certain projections into sets, and we already have folding functions, then an aggregation is merely an application of a folding function to certain elements of a grouping result. It can be done by means of regular function calls and does not require any special syntax. 5.3.10. Connections
Instead of useless joins, we ofer so called – a way of writing a selection from a whole hierarchy of relations, without explicitly mentioning each of them. The opportunity stems from the fact that the data scheme already contains all the information how relations relate to each other, how they are connected. connection ::= ( RELATION -><- selection )
It results in a subset of the given relation, but the selection criteria are formulated for another relation (implied in the given selection). The system scans the data scheme to find a path between two relations involved. And then connects the elements of the given selection with the elements of the queried selection along the found path.
W := (writer -><- (genre "bore")) // all writers connected to the given genre // same as G := (genre "bore") B := <book (book_genre G)> // projecting book_genre on book A := (author B) // author is a relation between book and writer W := <writer A> 5.3.11. Expressions
Finally. For a good closure. expression ::= CONST expression ::= NOMINATOR expression ::= selection expression ::= projection expression ::= connection expression ::= constructor expression ::= arith expression ::= funcall 5.3.12. Composite types
On one hand, having strictly typed functions makes perfect sense in a language where all data objects are strictly typed. When we query a book: we know the record type we got – the same knowledge of the type when querying a function is convenient. On the other hand a function does not always return a result, could be an error. Setting aside the exceptions (which remain an open question), we still need some means of handling nonexceptional results...
Since our functions return tuples, it is always suficient to return a type such as domain {foo_result result:int error:text} Although being suficient and very convenient in certain cases of error-prone function calls, such as calls to a filesystem that potentially return plentiful non-exceptional errors, this solution entails the burden of repetitive projections, e.g. always extracting the actual result from a return-tuple <result (foo arg)> a return-tuple can not be used in its raw form.
For example Erlang (despite the capability of returning tuples!) utilizes untyped functions for returning error values: a function can return a result of some known type or an error of another distinct type, the type of the result tells the fact of error.
Without forcing our users to adopt either strategy we may make both of them implementable in our language, by introducincgomposite types, a type that represents a union of several other types. Such a type represents a compromise between strict typisation and the Erlangish approach. Such a disjunctive type remains strict, it predicts exactly the variety of expected results, still it allows to transcend pre-existing types. type ::= "domain" {NAME domains} // a tuple of its domains type ::= "domain" {NAME [ domains ]} // either one of the domains domains ::=... domain domain ::= TYPE domain ::= LABEL:TYPE
For example a value of the typ e
can be either a 2D or 3D point: domain {point2d x:real y:real} domain {point3d x:real y:real z:real} domain {point [point2d point3d]}
In a less abstract venue, it allows us cater to some very practical usecases: domain {birthdate [date text]} // date OR text relation {person name:text birthdate} add {person "John Doe" `1976-01-01`} add {person "Ali ibn Hattab" "the user refused to reveal his birthdate"}
Although this example puts another important nail in the NULL’s cofin, still more practical usecases are possible: relation {prose_genre text} relation {poetry_genre text} domain {literature_genre [prose_genre poetry genre]}
This example strikingly resembles PostgreSQL’s inheritan9c]e. [Although in Postgres it is defined in reverse order, a supertype first. You can clearly see that a composite type can be a supertype in the exact same sense as in Postgres. And thus it covers all the legitimate usecases for Postgres’s inheritance and subtypes. And we only assumed here that Postgres along with Oracle share some strong meaningful real-life motivation to invent supertypes and squeeze them into their existing RDBMs.
We have got a world’s first language withpragmatic typisation – the types represent your domain knowledge, and refuse to represent memory management – a choice of a type is solely dictated by a given problem but not the implementation of the data storage.
The language handlessets of tuples as first class data objects (as “variables” in archaic terms) and supports set operation as fluently as arithmetic operations. The operations of tuple composition and decomposition can be expressed in the same manner (basic arith). And to achieve that we cleansed the language from any traces of positional referencing – all tuple entries are named.
Let’s summarize the secondary features of the language so far described.
• Full utilization of the information provided by the data scheme (see 5.3.10) • Concise formulations of queries • Textual compatibility of relational data manipulations with general purpose functional languages • Higher-order relations not requiring any special treatment, nor causing any confusion • Comfortable and straightforward laziness • Bare minimum of syntax constructs: re-using and re-using “homomorphic” structures for “homomorphic” purposes • Bare minimum of basic types • Comfortable handling of types of arbitrary complexity • Named parameters, free from positional references, name abbreviations • Same full toolbox for querying and constructing “Local” and “Temp” data, using the predefined data scheme • The SQL’s basic operations decomposed into more basic parts and reorganized more logically • Several improvements were made in general readability (see postfix assignments)
Many questions remain open. Is there a way to economize bracket types and reduce the zoo by one animal? Perhaps a bracket role can be unambiguously told by the first member class (e.g. a type as opposed to a nominator, etc)? There is room for ambiguity in unification of patterns containing curried functions. We have not defined any control structures, not even decided about grouping of commands. There must be subprograms, call them procedures or routines, or “saved transactions” if you will, as opposed to already defined functions that are pure. The type of the connection operation is not yet settled, it could be anything from the type of the queried relation to the Cartesian product of all types along the connecting path. [10] PostgreSQL documentation, ”Date And Time Types”, URL: https://www.postgresql.org/docs/9.1/datatype-datetime.html [11] Oracle documentation, ”Collections”,
URL: http://docs.oracle.com/cd/B10501_01/appdev.920/a97269/pc_18col.htm [12] TIOBE index, URL: https://www.tiobe.com/tiobe-index/ [13] The Definitive Glossary Of Higher Math Jargon, ”A Relation: Formal Definition”, URL: https://mathvault.ca/math-glossary/#relation [14] Infogalactic, ”Map (A Higher-Order-Function)”, URL: https://infogalactic.com/info/Map_(higherorder_function) [15] ”Unification in Prolog”, URL: https://cse3521.artifice.cc/prolog-unification.html