“Set of Strings” Framework for Big Data Modeling

Abstract

The most complicated task for big data modeling in comparison with relational approach is its variety, being a consequence of heterogeneity of sources of data, accumulated in the integrated storage space. “Set of Strings” Framework (SSF) provides unified solution of this task by representation of database as updated finite set of facts, being strings, in which structure is defined by current metadatabase, which is also an updated set of the context-free generating rules. This chapter is dedicated to SSF formal and substantial description.

1. Introduction

From the three “V’s,” traditionally used for description of big data (volume, variety, velocity) [1, 2, 3, 4, 5, 6, 7], variety is the most difficult for theoretical modeling. The main reason of such difficulty is heterogeneity of sources of data, accumulated in the integrated storage space. By this, data items, passing to the aforementioned storage, have different structures and formats (more or less formalized texts, multimedia, hyperlinked trees of pages, etc.), which makes practically impossible application to such data of well-known relational-originated approaches to database (DB) description, manipulation, and knowledge extraction/application [8, 9, 10, 11, 12]. This obstacle makes hardly achieved the fourth “V” (veracity), which last time is often associated with big data [13, 14, 15, 16, 17], as well as with implementation of data mining over such data storages [18, 19, 20, 21].

Such background makes necessary the alternative approach to data and knowledge modeling. This chapter contains compact consideration of the so-called “Set of Strings” Framework (SSF), developed in order to integrate on the unified theoretical basis capabilities, already used in the relational-like data representations and associated with them knowledge models, with big data immanent property—its variety.

SSF is a result of an attempt to design the aforementioned basis upon the most general representation of elementary data item, which may be stored, transported, received, processed, and visualized. Such representation is string (no matter, symbol, or bit), and SSF combines the best features of classical string-generating formal grammars, developed by Chomsky [22], with string-operating logical systems, proposed by Post [23].

The second section of this chapter is dedicated to the description of string databases (SDB), while the third, - to their interconnections with relational and non-relational DB. In the fourth section, incomplete information modeling within SSF is considered. The main content of the fifth section are the so-called word equations on context-free languages (WECFL), being key element of the SSF algorithmics.

2. “Set of strings” basic equations

The background of the SSF is representation of a database as a finite set of strings:

$$W_t=\left\{w_1,\dots ,w_{m\left(t\right)}\right\}\subset V^{\ast },$$ E1

where $W_t$ means DB at the discrete time moment $t$ and $V^{\ast }$ is a set of all strings in the initial (terminal) alphabet $V$ . Such databases will be called lower, if it is necessary to distinguish them from the other, the set of strings databases. The structure of DB elements $w_i\in W_t$ , named facts, is determined by metadatabase (MDB), in which the current state is denoted by $D_t$ .

Couple

$${\mathrm{\Theta }}_t=<W_t,D_t>,$$ E2

is named data storage (DS). Data storage is in the correct state, if $W_t\in \mathit{W}\left(D_t\right)$ , where $\mathit{W}\left(D_t\right)$ is the set of all correct databases, defined by the MDB.

Access message to DS is triple:

$${\omega }_t=<o,c,x>,$$ E3

where $o$ is the operation, which execution is the purpose of the access (insert, delete, update, query), $c$ is the DS component (DB, MDB) which is the objective of the access, and $x$ is the content of the access, i.e., query body, or DB elements (facts), which are inserted or deleted. For simplicity it is supposed that the answer (reply) to the access is obtained by the user at the moment $t+1$ , next to $t$ , and it is denoted $A_{t+1},\text{if}c=\mathrm{DB},\text{and}{A}_{t+1}^D,\text{if}c=\mathrm{MDB}$ (both sets are finite).

A set of all possible access messages (3) is called data storage manipulation language (DSML).

SSF background is a sequential definition of four interconnected representations of DSML semantics.

Set-theoretical (S)-semantics of DSML is defined by equations on sets, which connect together input data, DB before and after access, and answer (reply) to the access.

Mathematical (M)-semantics follows aforementioned equations but is defined by some well-known and understandable mathematical constructions, being background of DSML.

Operational (O)-semantics is adequate to M-semantics but is represented by algorithms, providing execution of operations on DB.

At last, implementational (I)-semantics is also represented by algorithms, which, in general case, are much more efficient than the previous, in which the main purpose is recognition of algorithmic decidability of answer search (derivation), i.e., possibility of answer generation by finite number of steps.

Let us begin from S-semantics of the DSML segment, addressing DB, called lower, as usually, data manipulation language (DML). The equations, defining DML S-semantics, operate the following sets:

1. $W_t$ (database at the moment of user’s access to DB).

2. $W_{t+1}$ (database after execution of operation, i.e., at the moment $t+1,\text{when answer is accepted}\mathrm{by}\text{the user}$ ).

3. $I_t$ (set, expressing user’s awareness about some fragment of problem area at the moment of access to DB).

4. $A_{t+1}$ (answer to the access).

Basic equations, defining DML S-semantics, are as follows:

$$W_{t+1}=W_t\cup I_t,$$ E4

$$A_{t+1}=W_{t+1}-W_t,$$ E5

for insertion (speaking more precisely, inclusion),

$$W_{t+1}=W_t-I_t,$$ E6

$$A_{t+1}=W_t-W_{t+1},$$ E7

for deletion (exclusion),

$$W_{t+1}=W_t,$$ E8

$$A_{t+1}=W_t\cap I_t,$$ E9

and for query (everywhere “ $-$ ” is subtraction on sets). As seen, Eqs. (4)–(9) fully correspond to the sense of basic operations on DB, inherent to any DML. In Eqs. (6) and (9), set $I_t$ may be infinite.

Example 1. Let database, containing data items from various emergency devices, be as follows:

$$W_t=\{\mathit{\text{AREA GREEN VALLEY IS IN NORMAL STATE}}\mathit{AT}15.03,$$

$$\mathit{\text{AREA BLUE LAKE IS IN NORMAL STATE}}\mathit{AT}15.05,$$

$$\mathit{\text{AREA LOWER FOREST IS SMOKED}}\mathit{AT}15.20\},$$ E10

(due to free use of natural language in facts, it is unnecessary to comment DB content). Equation

$$W_{t+1}=W_t\cup \left\{\mathit{\text{AREA GREEN VALLEY IS SMOKED}}\mathit{AT}15.20\right\}$$ E11

describes insertion of data item, in which the source is device, mounted at the Green Valley, which was detected as smoked since 15.20. When at this moment $t+1$ user accesses DB with query, in which the purpose is to get information about all smoked areas, the infinite set $I_t$ may be as follows:

$$I_{t+1}=\{\mathit{\text{AREA}}A\mathit{\text{IS SMOKED}}\mathit{AT}00.00,\dots ,$$

$$\mathit{\text{AREA}}A\mathit{\text{IS SMOKED}}\mathit{AT}23.59,\dots ,$$

$$\mathit{\text{AREA}}\mathit{AA}\mathit{\text{IS SMOKED}}\mathit{AT}00.00,\dots ,$$

$$\mathit{\text{AREA}}\mathit{AA}\mathit{\text{IS SMOKED}}\mathit{AT}23.59,\dots ,$$

$$\mathit{\text{AREA}}Z\mathit{\text{IS SMOKED}}\mathit{AT}00.00,\dots ,$$

$$\mathit{\text{AREA}}Z\mathit{\text{IS SMOKED}}\mathit{AT}23.59,\dots \}.$$ E12

The answer to the query is

$$A_{t+2}=W_{t+1}\cap I_{t+1}=\{\mathit{\text{AREA GREEN VALLEY IS SMOKED}}\mathit{AT}15.20,$$

$$\mathit{\text{AREA LOWER FOREST IS SMOKED}}\mathit{AT}15.20\}.$$ E13

In expression (12), names of all areas are strings in the alphabet $V=\left\{A,\dots ,Z,0,\dots ,9,.,\right\}$ , so

$$I_{t+1}=\left\{\mathit{\text{AREA}}\right\}\bullet V^{\ast }\bullet \left\{\mathit{\text{SMOKED}}\mathit{AT}\right\}\bullet \left\{00,\dots ,23\right\}\bullet \left\{.\right\}\bullet \left\{00,\dots ,59\right\}.∎$$ E14

Note that definitions (4)–(9) are not unique. For example, in the inclusion definition, elements of $I_t$ set, having place in the DB at moment $t,$ may be included to the answer

$$A_{t+1}=W_t\cap I_t,$$ E15

as well as the answer may be defined as

$$A_{t+1}=\left\{{\mathit{\text{FACT}}}^{"}\right\}\bullet \left(W_t\cap I_t\right)\bullet \left\{{}^{"}\mathit{\text{ALREADY PRESENTS IN DATABASE}}\right\}$$

$$\cup \left\{{\mathit{\text{FACT}}}^{"}\right\}\bullet \left(W_{t+1}-W_t\right)\bullet \left\{{}^{"}\mathit{\text{IS INCLUDED TO DATABASE}}\right\}.$$ E16

So, according to Eq. (16), the answer to the access may be as follows:

$$A_{t+1}=\{\mathit{\text{FACT}} “\mathit{\text{AREA GREEN VALLEY SMOKED}}$$

$$\mathit{AT} 15.20”\mathit{\text{ALREADY PRESENTS IN DATABASE}},$$

$$\mathit{\text{FACT}} “\mathit{\text{AREA LOWER FOREST IS SMOKED}}\mathit{AT}15.20”$$

$$\mathit{\text{IS INCLUDED TO DATABASE}}\}.∎$$ E17

As may be seen, Eqs. (4)–(9) are based on the closed-world interpretation, which defines that the absence of the fact in the database is equivalent to its absence in the real world (problem area).

DML operations do not touch MDB; thus $D_{t+1}=D_t$ .

Let us consider DML M- and O-semantics of DML.

The background of M-semantics of the simplest DML is the representation of the MDB $D_t$ as a set of the context-free (CF) generating rules $\alpha \to \beta$ , where $\alpha$ is a nonterminal symbol (“nonterminal” for short) $\text{and}\beta$ is a string of both nonterminal and terminal symbols. Every nonterminal symbol, from the substantial point of view, is the name of some substring of fact, entering DB; thus $\beta$ represents the structure of $\alpha$ . The only nonterminal symbol ${\alpha }_0$ , which does not enter any string $\beta$ , is the “axiom” in the terminology of formal grammars and “fact” in the terminology of SSF. So MDB $D_t$ unambiguously defines CF grammar

$$G_t=<V,N_t,{\alpha }_0,D_t>,$$ E18

where

$$N_t=\left\{\alpha \right|\alpha \to \beta \in D_t\}$$ E19

is the set of nonterminals (“nonterminal alphabet”) of $G_t$ .

Database $W_t$ is named correct to metadatabase $D_t$ , if

$$W_t\subseteq L\left(G_t\right),$$ E20

i.e., facts, having place in the DB, are words of the CF language $L\left(G_t\right)$ . In other notation,

$$\left(\forall w\in W_t\right){\alpha }_0\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}w,$$ E21

where $\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}$ is used to define that string in alphabet $V\cup N_t$ is generated (or derived) from another one.

Example 2. Let MDB $D_t$ be as follows (nonterminal symbols are framed by metalinguistic brackets):

$$<\mathit{\text{fact}}>\to \mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS}}<\mathit{\text{state}}>$$

$$\mathit{AT}<\mathit{\text{time}}>,$$

$$<\mathit{\text{name of area}}>\to <\mathit{\text{text}}>,$$

$$<\mathit{\text{state}}>\to \mathit{\text{IN NORMAL STATE}},$$

$$<\mathit{\text{state}}>\to \mathit{\text{SMOKED}},$$

$$<\mathit{\text{time}}>\to <\mathit{\text{hours}}>.<\mathit{\text{minutes}}>,$$

$$<\mathit{\text{hours}}>\to <0\mathit{\text{to}}1><0\mathit{\text{to}}9>,$$

$$<\mathit{\text{hours}}>\to 2<0\mathit{\text{to}}3>,$$

$$<0\mathit{\text{to}}1>\to 0,$$

$$<0\mathit{\text{to}}1>\to 1,$$

$$<0\mathit{\text{to}}9>\to 0,$$

$$\dots$$

$$<0\mathit{\text{to}}9>\to 9,$$

$$<0\mathit{\text{to}}3>\to 0,$$

$$\dots$$

$$<0\mathit{\text{to}}3>\to 3,$$

$$<\mathit{\text{minutes}}>\to <0\mathit{\text{to}}5><0\mathit{\text{to}}9>,$$

$$<0\mathit{\text{to}}5>\to 0,$$

$$\dots$$

$$<0\mathit{\text{to}}5>\to 5,$$

$$<\mathit{\text{text}}>\to <\mathit{\text{symbol}}>,$$

$$<\mathit{\text{text}}>\to <\mathit{\text{symbol}}><\mathit{\text{text}}>,$$

$$<\mathit{\text{symbol}}>\to A,$$

$$\dots$$

$$<\mathit{\text{symbol}}>\to Z,$$

$$<\mathit{\text{symbol}}>\to 0,$$

$$\dots$$

$$<\mathit{\text{symbol}}>\to 9,$$

$$<\mathit{\text{symbol}}>\to ˽.$$

Database

$$W_t=\{\mathit{\text{AREA}}\mathit{AW}\mathit{\text{IS SMOKED}}\mathit{AT}15.10,$$

$$\mathit{\text{AREA}}E\mathit{\text{IS IN NORMAL STATE}}\mathit{AT}23.59\}$$

is correct to this MDB, unlike database

$W_t=\left\{\mathit{\text{AREA}}\mathit{AT}\mathit{\text{NORMAL}}\right\}$ . $∎$

Proposed application of CF grammars differs from the classical, in which the main sense is the description of a set of correct sentences of some language (most frequently, programming language). This description is created by its developers or researchers, is based on syntactic categories referred as nonterminals, and is constant through all life cycle of the language (minor changes may be done by reason of language modification or deeper understanding). In the SSF case, CF generating rules are used for description of the DB element (facts) structure, so nonterminals are more semantic than syntactic objects. From the other side, MDB is updated by DS administration and is a dynamic set, in which changes provide immediate changes of DB in order to keep it in the correct state. Such changes may be defined by the following equations, similar to Eqs. (4)–(9):

$$D_{t+1}=D_t\cup I_t^D,$$ E22

$$A_{t+1}^D=D_{t+1}-D_t,$$ E23

$$W_{t+1}=W_t$$ E24

for insertion (inclusion) of new CF rules to MDB,

$$D_{t+1}=D_t-I_t^D,$$ E25

$$A_{t+1}^D=D_t-D_{t+1},$$ E26

$$W_{t+1}=W_t\cap L\left(G_{t+1}\right)$$ E27

for deletion (exclusion) of CF rules, having place in MDB,

$$D_{t+1}=D_t,$$ E28

$$A_{t+1}^D=D_t\cap I_t^D,$$ E29

$$W_{t+1}=W_t$$ E30

and for query to MDB. Here $I_t^D$ is similar to $I_t$ in Eqs. (4)–(9), being a set of CF rules representing knowledge of DS administration about MDB. As seen, Eqs. (22) and (23) provide extension of MDB; thus

$$L\left(G_t\right)\subseteq L\left(G_{t+1}\right),$$ E31

and DB remains correct, because

$$W_t\subseteq L\left(G_t\right)\subseteq L\left(G_{t+1}\right).$$ E32

In Eqs. (25) and (26), where some part (subset) of MDB may be deleted,

$$L\left(G_{t+1}\right)\subseteq L\left(G_t\right),$$ E33

so some facts $w\in L\left(G_t\right)$ may become not satisfying condition (20) of DB correctness to MDB $D_{t+1}$ , because $w\notin L\left(G_{t+1}\right)$ . In Eqs. (25)–(30), it is presumed, that $D_t$ is also SDB, in which MDB defines structure of CF rules, which may be as Example 2.

Let us note that the notion of SDB correctness to MDB is from the substantial point of view weaker than the notion of data storage correctness, because in general case

$$\mathit{W}\left(D_t\right)\subseteq 2^{L\left(G_t\right)},$$ E34

i.e., set of databases in correct storage is the subset of Boolean of $L\left(G_t\right)$ , while SDB correct to MDB is such that

$$\mathit{W}\left(D_t\right)=2^{L\left(G_t\right)},$$ E35

i.e., every SDB, containing facts, being words of CF language $L\left(G_t\right)$ , is correct, which is not true in the reality. DS correctness is the generalization of notion of DB integrity, deeply developed inside relational approach covering the total content of database, i.e., interconnections between its different elements. There are known various tools for integrity criteria declaration and check—first of all, functional dependencies and their multiple modifications [24, 25, 26, 27, 28, 29, 30, 31, 32]. Storage correctness, being SDB analog of integrity, is considered inside SSF on the basis of augmented Post systems (APS).

Let us consider now the application of the described segment of the SSF to the representation of the most frequently used data models. We shall call such application by the term “emulation.”

3. Emulation of the known data models

We shall demonstrate how relational and non-relational databases may be represented on the described higher background. We shall consider relational data model as a full-scope example of databases with symmetric access (DBSA) [8, 9, 10, 11, 12] and a family of asymmetric access (or key-addressed) databases (KADB), which contains, among others, hypertext, page, and WWW- and Twitter-like DB [32, 33, 34, 35, 36, 37, 38, 39, 40, 41].

Let us begin from the relational model of data.

Consider relational database (RDB), in which the scheme is $\left\{R_1\left(A_1^1,\dots ,A_{m1}^1\right),\dots ,R_k(A_1^k,\dots ,A_{\mathit{mk}}^k)\right\}$ , where $R_1$ ,…, $R_k$ are the names of relations and $A_1^1,\dots ,A_j^i,\dots ,A_{\mathit{mk}}^k$ are the names of attributes. Every relation $R_i$ at moment t is the set of tuples

$$R_i\subseteq D_j^i\times \dots \times D_{\mathit{mj}}^i,$$ E36

where $D_j^i$ is the domain (set of possible values of attribute $A_j^i$ ).

We shall define SDB $<W_t,D_t>$ , corresponding to this RDB, as follows. We shall include to the MDB $D_t$ rules

$$\begin{array}{l}<\mathit{\text{fact}}>\to R_1:<A_1^1>,\dots ,<A_{m1}^1>,\\ \dots \\ <\mathit{\text{fact}}>\to R_k:<A_1^k>,\dots ,<A_{\mathit{mk}}^k>,\end{array}$$ E37

where “<” and “>” are the dividers (aforementioned metalinguistic brackets in the Backus-Naur notation) and $R_i$ and $A_j^i$ are the strings, being names of relations and attributes, respectively (dividers provide syntactic unambiguity).

Along with Eq. (36), MDB will include rules such that

$$D_j^i=\left\{b|<A_j^i>\stackrel{\ast }{\Rightarrow }b\&b\in \left\{V-\left\{,\right\}\right\}{}^{\ast }\right\},$$ E38

i.e., these rules provide generation of sets of words in terminal alphabet $V$ , being domains of the respective attributes. For unambiguity we assume that comma “,” does not enter values of attributes $V\in D_j^i$ .

By this, every tuple $\left(b_1^i,\dots ,b_{\mathit{mi}}^i\right)$ of the relation $R_i$ is represented by fact

$$R_i:b_1^i,\dots ,b_{\mathit{mi}}^i\in W_t.$$ E39

Note that representation of facts in the form (37)–(39) is not unique. As seen from Examples 1 and 2, tuples, entering relations, may be represented as any natural language phrases, described by the corresponding rules.

Let us consider now key-addressed databases. Their common feature is that every fact, entering KADB, includes a unique key, which is necessary to select, delete, and update this fact. These DB are associated with NoSQL family of DML [42, 43, 44, 45], which in the last years is considered as a practical alternative to SQL-like DML [8, 9, 10, 11, 12, 46, 47, 48], developed since the introduction of the relational model of data.

We shall represent KADB as set

$$W_t=\left\{k_1=d_1,\dots ,k_m=d_m\right\},$$ E40

where symbol “=” inside angle brackets is the divider, $k_i\in \left(V-\left\{=\right\}\right){}^{\ast }$ is the key, and $d_i\in V^{\ast }$ is the data, corresponding to this key (or identified by it). At every moment $t$ , KADB must satisfy the consistency condition: KADB is consistent, if

$$\left(\forall t\right)\left(\forall k\in \left(V-\left\{=\right\}\right){}^{\ast }\right)\mid \left\{k=\right\}\cdot V^{\ast }\cap W_t\mid \le 1,$$ E41

i.e., set $W_t$ would not include two or more elements with one and the same key.

Content of access to KADB must include key $k$ , so $I_t\subseteq \left\{k=\right\}\cdot V^{\ast },$

and for inclusion $I_t=\left\{k=d\right\}$ . S-semantics of insertion to KADB is as follows:

$$W_{t+1}=\left\{\begin{array}{l}{W}_t\cup \left\{k=d\right\},\mathit{\text{if}}\left\{k=\right\}\cdot V^{\ast }\cap W_t=\left\{\varnothing \right\},\\ W_t-\left\{k=\right\}\cdot V^{\ast }\cup \left\{k=d\right\}\mathit{\text{otherwise}},\end{array}\right.$$ E42

because postulation of fact $k=d$ at moment $t$ is equivalent to the negation of fact $k=d^{\prime }$ , where $d\ne d^{\prime }$ , which was postulated at some earlier moment $t^{\prime }<t$ . So in the case of KADB update is implemented by insertion, and reply to this access may be defined as follows:

$$A_{t+1}=\left\{\begin{array}{l}k=d,\mathit{\text{if}}\left\{k=\right\}\cdot V^{\ast }\cap W_t=\left\{\varnothing ,\right\},\\ \left(W_t\cap \left\{k=\right\}\cdot V^{\ast }\right)\cup \left\{k=d\right\}\mathit{\text{otherwise}},\end{array}\right.$$ E43

thus in the case of update reply contains deleted as well as included fact.

Concerning M-semantics of KADB, we may see, that every known class of such databases is identified by its own structure of keys and techniques of their extraction from the current processed fact.

The simplest approach is implemented in Twitter network, where keys, necessary for access to the descendants of the current element of the hypertext, are bounded by two dividers—“#” from the left and blank from the right.

In the Internet HTTP/WWW service, similar keys are represented as strings of symbols, visualized by other colors in comparison with the rest of the text of the current hypertext page. This is equivalent to splitting terminal alphabet $V$ to two subsets, first including symbols of the ordinary colors and the second symbols of the “key-representing” colors. However, HTTP/WWW hypertexts are organized in a much more complicated manner. First of all, along with the displayed pages, in which the structure is described by hypertext markup language (HTML) or its various later versions (XML et al.), there is another KADB, in which elements contain keys, being the aforementioned strings of another colors, and data are, in fact, unified resource locators (URL), providing direct network access to the subordinated pages. This access is possible, because URL contains string, providing application of the domain name service (DNS) for resolving proper IP address. In fact, HTML is no more than language for the convenient representation of CF rules, which form current metadabase of the WWW KADB.

One of the simplest versions of KADB is the so-called page databases, in which elements are strings of equal length, the first string of the page being key [38, 39]. Thus

$$\left(\forall t\right)L\left(G_t\right)=V^l\left(V^l\right){}^{\ast },$$ E44

where $l$ is the length of the string (in this case divider “=” is redundant). Data may be also string $p:d$ , where “:” is the divider and prefix p before the sequence of l-symbol strings defines the name of the program, called for this sequence interpretation (e.g., visualization). In general case $d$ may be the string of bits, not only string of symbols of alphabet $V$ .

Until now we discussed only S-semantics and start point of M-semantics, being representation of metadabase as a set of rules of CF grammar. Second such point in the SSF is the representation of databases with incomplete information.

4. Representation of databases with incomplete information and sentential data manipulation languages

Let $D_t$ be the metadabase. Then database with incomplete information (for short, DBI or, if it is necessary to underline “set of strings” DBI, then SDBI), denoted $X_t$ , is the finite set of the so-called incomplete facts (N-facts) being sentential forms (SF) of CF grammar $G_t$ :

$$X_t=\left\{x_1,\dots ,x_m\right\}\subseteq \mathit{SF}\left(G_t\right),$$ E45

where

$$\mathit{SF}\left(G_t\right)=\left\{x|a_0\underset{G_t}{\overset{\ast }{\Rightarrow }}x\right\}$$ E46

is the set of all sentential forms of grammar $G_t$ . Obviously, $L\left(G_t\right)\subset \mathit{SF}\left(G_t\right).$

Example 3. Consider MDB from Example 2 and corresponding DBI

$$X_t=\{\mathit{\text{AREA LONELY TREES IS NORMAL}}\mathit{AT}12.31,$$

$$\mathit{\text{AREA LONELY TREES}}<\mathit{\text{state}}>\mathit{AT}12.<\mathit{\text{minutes}}>,$$

$$\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS SMOKED}}\mathit{AT}15.30\}.$$

The first N-fact of the three, entering this DBI, does not contain nonterminals, so it is fact in the sense of S-semantics of DML. The second N-fact contains nonterminals <state> and <minutes>, which correspond to the uncertainty of the state of the area Lonely Trees and time moment, when this state occurs; however, the aforementioned moment enters interval from 12.01 to 12.59. The last N-fact contains information about the same area, which was detected as smoked at 15.30. $∎$

Before consideration of equations, defining M-semantics of operations on DBI, we shall introduce interpretation of relation $\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}$ of the mutual derivability of sentential forms of context-free grammar as relation of mutual informativity of N-facts.

Let $G_t$ be acyclic and unambiguous CF grammar [49]. If so, $\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}$ is the relation of partial order on the set $\mathit{SF}\left(G_t\right)$ [38, 39].

There is maximal element of the set $\mathit{SF}\left(G_t\right)$ —it is axiom ${\alpha }_0$ (“fact”) because for every x $\in \mathit{SF}\left(G_t\right),$ ${\alpha }_0\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}x$ . For every subset $X\subseteq \mathit{SF}\left(G_t\right),$ there exists set of its upper bounds, e.g., sentential forms (“N-facts”) $y\in \mathit{SF}\left(G_t\right)$ , such that $y\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}x$ for all $x\in X$ , and minimal (least) upper bound, $\text{sup}X,$ such that for every other upper bound y from the mentioned set, the relation $y\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}\text{sup}X$ is true. For some $X\subseteq \mathit{SF}\left(G_t\right),$ there may exist set of lower bounds, e.g., sentential forms (“N-facts”) $y\in \mathit{SF}\left(G_t\right),$ such that $x\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}y$ for all $x\in X$ , and maximal lower bound $\text{inf} X$ such that for every other lower bound y, $\text{inf} X\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}y$ is true.

Algorithms of sup and inf generation are described in detail in [38, 39].

Example 4. For DBI from Example 3, $\text{inf} X_t$ does not exist, but

$$\text{sup}{X}_t=\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS}}<\mathit{\text{state}}>\mathit{AT}1<0\mathit{\text{to}}9>.<\mathit{\text{minutes}}>.$$

At the same time,

$$\text{inf}\{\mathit{\text{AREA LONELY TREES IS}}<\mathit{\text{state}}>\mathit{AT}12.30,$$

$$\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS SMOKED}}\mathit{AT}12.<\mathit{\text{minutes}}>\}$$

$$=\mathit{\text{AREA LONELY TREES IS SMOKED}}\mathit{AT}12.30.∎$$

Since now we shall use interpretation of $\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}$ as of the relation of the mutual informativity of incomplete facts. According to this interpretation, $x\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}{x}^{\prime }$ means that N-fact $x^{\prime }$ is not less informative in comparison with N-fact x (if x $\begin{array}{c}+\\ ⟹\\ G_t\end{array}{x}^{\prime }$ , then $x^{\prime }$ is more informative and is called concretization of $x$ ). (This interpretation naturally fits to A. Kolmogorov’s algorithmic theory of information basic postulates, i.e., constructive objects mutual complexity [50]).

Graphical illustration of interconnections between $\text{sup}\left\{x,y\right\}$ and $\text{inf}\left\{x,y\right\}$ is in Figure 1. As seen, $\text{sup}\left\{x,y\right\}{\displaystyle \stackrel{\ast }{\Rightarrow }}x$ , $\text{sup}\left\{x,y\right\}{\displaystyle \stackrel{\ast }{\Rightarrow }}y$ , $x{\displaystyle \stackrel{\ast }{\Rightarrow }}\text{inf}\left\{x,y\right\}$ , $y{\displaystyle \stackrel{\ast }{\Rightarrow }}\text{inf}\left\{x,y\right\}$ , $\text{inf}\left\{x,y\right\}{\displaystyle \stackrel{\ast }{\Rightarrow }}w$ , and $\text{inf}\left\{x,y\right\}{\displaystyle \stackrel{\ast }{\Rightarrow }}{w}^{\prime }$ , where $w\in L\left(G_t\right)$ and $w^{\prime }\in L\left(G_t\right)$ .

Figure 1.

Graphical illustration of interconnection between $\text{sup}\left\{x,y\right\}$ and $\text{inf}\left\{x,y\right\}$ .

Let us consider DBI $X_t=\left\{x_1,\dots ,x_{m\left(t\right)}\right\}\subseteq \mathit{SF}\left(G_t\right)$ . We shall call such DBI nonredundant (NR), if there are no two N-facts x and $x^{\prime }$ entering $X_t$ , one of which is more informative than the other. (It is obvious that if $x^{\prime }\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}x$ , then there is no necessity of storing x ${}^{\prime }$ , because all information, having place in $x^{\prime }$ , presents in x. So $x^{\prime }$ is a redundant N-fact, and DBI, containing such N-facts, is also redundant).

Until the contrary is declared, we shall consider only NR DBI lower. By this, when defining M-semantics of update of NR DBI, understood as inclusion of N-fact $x\in \mathit{SF}\left(G_t\right),$ it is reasonable to suppose, that it contains maximally informative N-facts, which only may be acquired by the system. In this case inclusion of N-fact $x\in X_t$ to DBI may be defined as follows:

$$X_{t+1}=X_t\bigcup \left\{x\right\}-\left\{y|y\in X_t\&\left(x\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}y\bigvee y\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}x\right)\right\}.$$ E47

According to this definition, N-fact $x$ inclusion to DBI $X_t$ causes extraction from DBI of all N-facts, which are more or less informative than x. Such logics provides maintenance of nonredundancy of the DBI. As seen, all N-facts, having place in $X_t$ and being “compatible” with N-fact x by informativity, are eliminated from this DBI.

It is reasonable to define reply to the inclusion of N-fact x as set of N-facts, eliminated from DBI:

$$A_{t+1}=X_t-X_{t+1}.$$ E48

Example 5. If N-fact $x=\mathit{\text{AREA GREEN VALLEY IS SMOKED}}\mathit{AT}15.30$ is included to DBI $X_t$ from Example 3, then

$$X_{t+1}=\{\mathit{\text{AREA LONELY TREES IS NORMAL}}\mathit{AT}12.31,$$

$$\mathit{\text{AREA LONELY TREES}}<\mathit{\text{state}}>\mathit{AT}12.<\mathit{\text{minutes}}>,$$

$$\mathit{\text{AREA GREEN VALLEY IS SMOKED}}\mathit{AT}15.30\},$$

because

$$\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{SMOKED}}\mathit{AT}15.30\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}$$

$\mathit{\text{AREA GREEN VALLEY IS SMOKED}}\mathit{AT}15.30$ . $∎$

As to M-semantics of queries, there may by two different versions, which run out of the new DBI features in comparison with DB.

The first version is obvious:

$$A_{t+1}^y=\left\{x|x\in X_t\&y\stackrel{\ast }{\Rightarrow }x\right\},$$ E49

where $A_{t+1}^y$ is the answer to the query with content $y$ , and all N-facts from DBI $X_t$ , which are no less informative than $x$ , are included to the answer.

As seen, by this we postulate query language to databases (or DB with complete information): it is the set of sentential forms of CF grammar $G_t$ , and in the case of SF $y$ is the content of query ${\omega }_t$ ,

$$I_t=\left\{w|y\underset{G_t}{\overset{\ast }{\Rightarrow }}w\&w\in V^{\ast }\right\},$$ E50

i.e., it is the set of facts, more informative than N-fact $y$ , having place in the query. So combining Eqs. (9) and (49), we obtain

$$A_{t+1}=W_t\cap I_t=\left\{w|y\underset{G_t}{\overset{\ast }{\Rightarrow }}w\&w\in W_t\right\},$$ E51

i.e., the result of access is the subset of database $W_t$ , containing all facts, more informative than $y$ .

The background of the second version is the interpretation of the query as an action, which aim is to check if there are such possible facts $w\in L\left(G_t\right),$ which are more informative than N-fact x, entering $X_t$ , and N-fact y (query content):

$$\left(\exists w\in L\left(G_t\right)\right)x\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}w\&y\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}w,$$ E52

so, while x is not concretization of $y$ , it is sensible to include $x$ to the answer, because there may be facts $w\in L\left(G_t\right),$ which are both $x$ and $y$ concretizations. The set of such facts is the intersection $W_x\cap W_y$ , where

$$W_x=\left\{w|x\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}w\right\},$$ E53

$$W_y=\left\{w|y\begin{array}{c}\ast \\ ⟹\\ G_t\end{array}w\right\}.$$

Finite representation of the aforementioned intersection is, obviously, maximal lower bound of the set $\left\{x,y\right\}$ . For this reason, answer to the query with content y may be set

$${\overline{A}}_{t+1}^y=\left\{x\right|x\in X_t\&\exists \text{inf}\left\{x,y\right\}\},$$ E54

and, as an alternative,

$${\overline{\overline{A}}}_{t+1}^y=\left\{\text{inf}\left\{x,y\right\}\right|x\in X_t\&\exists \text{inf}\left\{x,y\right\}\}.$$ E55

Example 6. Consider DBI $X_t$ from Example 3 and the query with content $y=\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS SMOKED}}\mathit{AT}<\mathit{\text{time}}>$ . The purpose of this query is to get information about all areas smoked. According to Eqs. (49), (54), and (55)

$$A_{t+1}^y=\left\{\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS SMOKED}}\mathit{AT}14.30\right\},$$

$${\overline{A}}_{t+1}^y=\{\mathit{\text{AREA LONELY TREES}}<\mathit{\text{state}}>\mathit{AT}13.<\mathit{\text{minutes}}>,$$

$$\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS SMOKED}}\mathit{AT}14.30\},$$

$${\overline{\overline{A}}}_{t+1}^y=\{\mathit{\text{AREA LONELY TREES IS SMOKED}}\mathit{AT}13.<\mathit{\text{minutes}}>,$$

$\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS SMOKED}}\mathit{AT}14.30\}$ . $∎$

Returning to DB, which DML S-semantics was defined by Eqs. (4)–(9), we may now write its M-semantics equations not only for query but also for insertion and deletion. Namely, if string $w$ is the content of the insertion access, then

$$W_{t+1}=\left\{\begin{array}{l}{W}_t\cup \left\{w\right\},\mathit{\text{if}}w\in L\left(G_t\right),\\ W_t\mathit{\text{otherwise}}.\end{array}\right.$$ E56

Similarly, if string $y$ , containing terminal and nonterminal symbols of CF grammar $G_t$ , is the content of the delete access, then

$$W_{t+1}=W_t-\left\{w|y\underset{G_t}{\overset{\ast }{\Rightarrow }}w\&w\in L\left(G_t\right)\right\}.$$ E57

Data manipulation languages, described in this section, will be called sentential (SDML), because content of any access to DB/DBI, specified with the help of such DML, is a sentential form of CF grammar, which set of rules is current MDB.

Concerning KADB, capabilities of the sentential DML are compatible with the aforementioned NoSQL languages, which provide selection of DB elements, in which keys are specified in the queries.

Of course, it is not difficult to extend SDML by features, providing construction of more complicated selection criteria (including, e.g., number intervals) [38, 39]. But in comparison with SQL and similar relational languages, providing symmetric access to DB, SDML are rather poor. To achieve capabilities of the relationally complete query languages, it is necessary to extend SDML by features, providing comparison of values, having place in different facts. Such features are critically needed also for knowledge representation, extraction, and processing.

To achieve the formulated purpose, we shall use another tool, differing from CF grammars, namely, Post systems (PS), which also operate strings but, due to variables in their basic constructions (productions), have basic capabilities for aforementioned functions. The result of integration of the described “set of strings” databases with PS are augmented Post systems. The intermediate layer between SDB and APS is formed by the so-called word equations on context-free languages, considered in the next section.

5. Word equations on context-free languages

Word equation is a well-known object of discrete mathematics, defined as follows [51, 52, 53, 54, 55, 56].

Word equation is written as

$$s=s^{\prime },$$ E58

where $s$ and $s^{\prime }$ are the so-called terms. Term is a non-empty sequence of symbols of alphabet, which we shall call terminal, presuming it is the same set $V$ , as higher, and variables, which universum is denoted Г. So $s\in {\left(V\cup \mathrm{Г}\right)}^{+},s^{\prime }\in {\left(V\cup \mathrm{Г}\right)}^{+}$ . Domain (set of values) of every variable $\gamma \in \mathrm{\Gamma }$ , having place in any term, is $V^{\ast }$ . Term without any variables is, obviously, word in alphabet $V$ . At least one variable must present in WECFL or just the same in term $s{s}^{\prime }$ (or $s^{\prime }s$ ):

$$s{s}^{\prime }\in {\left(V\cup \mathrm{\Gamma }\right)}^{+}-V^{+}.$$ E59

Set

$$d=\left\{{\gamma }_1\to u_1,\dots ,{\gamma }_n\to u_n\right\},$$ E60

where ${\gamma }_1,\dots ,{\gamma }_n$ are the variables, $u_1,\dots ,u_n$ are the strings in alphabet $V$ , and $\to$ is the divider (which is not occasionally the same as higher in the generating rules $\alpha \to \beta$ , entering metadabases), is called substitution.

Term $s\left[d\right]$ is the result of application of substitution $d$ to term $s$ and is defined as follows. If

$$s=\overline{u_1}{\gamma }_{i1}\overline{u_2}\dots \overline{u_m}{\gamma }_{\mathit{im}}{\overline{u}}_{m+1},$$ E61

where $\overline{u_i}\in V^{\ast }$ and $i=1,\dots ,m+1,$ , then

$$s\left[\delta \right]=\overline{u_1}\overline{{\gamma }_{i1}}\overline{u_2}\dots \overline{u_m}\overline{{\gamma }_{\mathit{im}}}{\overline{u}}_{m+1},$$ E62

where

$$\overline{{\gamma }_{\mathit{ij}}}=\left\{\begin{array}{l}{u}_{\mathit{ij}},\mathit{\text{if}}{\gamma }_{\mathit{ij}}\to u_{\mathit{ij}}\in d\\ {\gamma }_{\mathit{ij}}\mathit{\text{otherwise}}.\end{array}\right.$$ E63

Definitions (62) and (63) cover general case, when some of the variables, entering term $s$ , do not enter the substitution (60).

Substitution $d$ is called terminal substitution to term $s\in {\left(V\cup \mathrm{\Gamma }\right)}^{+}-V^{+}$ , if

$$s\left[d\right]\in V^{+},$$ E64

i.e., result of its application to term is word in the alphabet $V$ . In this case, obviously,

$$\left\{{\gamma }_{i1},\dots ,{\gamma }_{\mathit{\text{in}}}\right\}\subseteq \left\{{\gamma }_i,\dots ,{\gamma }_n\right\}.$$ E65

Terminal substitution to terms $s$ and $s^{\prime }$ is called solution of word equation (58), if

$$s\left[d\right]\equiv s\left[d^{\prime }\right],$$ E66

i.e., result of application of $d$ to terms $s$ and $s^{\prime }$ is one and the same word (here $"\equiv "$ is identity sign).

Returning to SDB and M-semantics of their DML, we may see that set of terms may be the simplest query language to SDB. If term

$$s=\overline{u_1}{\gamma }_{i1}\overline{u_2}\dots \overline{u_m}{\gamma }_{\mathit{im}}{\overline{u}}_{m+1},$$ E67

is query to DB $W_t$ , then

$$I_t=\left\{\overline{u_1}{u}_{i1}\overline{u_2}\dots \overline{u_m}{u}_{\mathit{im}}{\overline{u}}_{m+1}|u_{i1}\in V^{\ast }\&\dots \&u_{\mathit{im}}\in V^{\ast }\right\},$$ E68

and

$$A_{t+1}=W_t\cap I_t=\left\{w|w\in W_t\&\left(\exists u_{i1}\in V^{\ast }\right)\dots \left(\exists u_{\mathit{im}}\in V^{\ast }\right)\overline{u_1}{u}_{i1}\overline{u_2}\dots \overline{u_m}{u}_{\mathit{im}}{\overline{u}}_{m+1}=w\right\},$$ E69

so Eq. (69) is the definition of M-semantics of the term’s query language to SDB; as seen, $w\in A_{t+1}$ , if $w\in W_t$ , and word equation $s=w$ has at least one solution.

Example 7. Consider database $W_t$ , containing three facts:

SENSOR 1 IS AT GREEN VALLEY,

SENSOR 2 IS AT BLUE LAKE,

AREA LOWER FOREST IS SMOKED.

If query $s=\mathit{\text{SENSOR}}a$ , which purpose, as seen, is to select all facts with information about sensor installation, then

$$A_{t+1}=\left\{\begin{array}{lllll}\mathit{\text{SENSOR}}& 1& \mathit{\text{IS}}& \mathit{AT}& \mathit{\text{GREEN VALLEY}},\\ \mathit{\text{SENSOR}}& 2& \mathit{\text{IS}}& \mathit{AT}& \mathit{\text{BLUE LAKE}}\end{array}\right\},$$

and solution of word equations

SENSOR a = SENSOR 1 IS AT GREEN VALLEY

and

SENSOR a = SENSOR 2 IS AT BLUE LAKE

are, respectively,

$$\left\{a\to \begin{array}{cccc}1& \mathit{\text{IS}}& \mathit{AT}& \mathit{\text{GREEN VALLEY}}\end{array}\right\}$$

and

$\left\{a\to \begin{array}{cccc}2& \mathit{\text{IS}}& \mathit{AT}& \mathit{\text{BLUE LAKE}}\end{array}\right\}$ . $∎$

However, the application of the term’s query language to databases with incomplete information, containing sentential forms of CF grammar with scheme $D_t$ , being DS metadabase, is not so simple and needs more sophisticated mathematical background.

Let $G$ be CF grammar, corresponding metadabase D (lower index t for simplicity is omitted). We shall call word equation on context-free language $L\left(G\right)$ couple

$$<s=s^{\prime },\delta >,$$ E70

where the first component $s=s^{\prime }$ is the word equation in the sense (58), called here kernel, while

$$\delta =\left\{{\gamma }_1\to {\beta }_1,\dots ,{\gamma }_l\to {\beta }_l\right\},$$ E71

is the so-called suffix, which defines domains (sets of values) of variables ${\gamma }_1,\dots ,{\gamma }_l$ , entering terms $s$ and $s^{\prime }$ , by means of strings ${\beta }_1,\dots ,{\beta }_l$ , containing terminal and nonterminal symbols of grammar $G$ . Kernel and suffix must satisfy the so-called sentential condition

$$\left\{s\left[\delta \right],s^{\prime }\left[\delta \right]\right\}\subseteq \mathit{SF}\left(G\right),$$ E72

i.e., strings, being the result of application of substitution $\delta$ to terms $s$ and $s^{\prime }$ , must be sentential forms of grammar $G$ . As seen, $\delta$ is the generalization of substitution (60), so it will be called lower SF-substitution.

WECFL (70) may be read “ $s=s^{\prime }$ , where $\delta$ .”

Domain of variable ${\gamma }_i$ is the set of strings in terminal alphabet $V$ , which are generated from string ${\beta }_i$ by application of rules of grammar $G$ . This domain is denoted as

$$\mathrm{V}\left({\gamma }_i,\delta \right)=\left\{u|{\gamma }_i\to {\beta }_i\in \delta \&{\beta }_i\stackrel{\ast }{\Rightarrow }u\&u\in V^{\ast }\right\}$$ E73

(from here we shall use $\stackrel{\ast }{\Rightarrow }$ in the sense ${\displaystyle \underset{G}{\overset{\ast }{\Rightarrow }}}$ ).

Suffix $\delta$ defines set of terminal substitutions to terms $s$ and $s^{\prime }$ , denoted

$${\sum }_{\delta }=\underset{\begin{array}{l}{u}_1\in V\left({\gamma }_1,\delta \right)\\ \cdots \\ u_l\in V\left({\gamma }_l,\delta \right)\end{array}}{\cup }\left\{\left\{{\gamma }_1\to u_1,\dots ,{\gamma }_l\to u_l\right\}\right\}.$$ E74

As it is easy to see, direct consequence of the sentential condition (72) and definition (74) is

$$\left\{s\left[d\right],s^{\prime }\left[d\right]\right\}\subseteq L\left(G\right),$$ E75

for every $d\in {\sum }_{\delta }$ .

If terminal substitution $d$ is such that

$$s\left[d\right]\equiv s\left[d^{\prime }\right],$$ E76

it is called solution of WECFL (70). Set of solutions of WECFL (70), which is infinite in general case, is denoted $D\left[s=s^{\prime },\delta \right]$ .

Function V may be applied to every term, so

$$\mathrm{V}\left(s,\delta \right)=\left\{s\left[d\right]|d\in {\sum }_{\delta }\right\}\subseteq L\left(G\right),$$ E77

$$\mathrm{V}\left(s^{\prime },\delta \right)=\left\{s^{\prime }\left[d\right]|d\in {\sum }_{\delta }\right\}\subseteq L\left(G\right).$$ E78

Example 8. Let metadatabase be the same as in Example 2, and WECFL is

$$\begin{array}{l}<\mathit{\text{AREA\hspace{0.17em}GREEN\hspace{0.17em}VALLEY\hspace{0.17em}IS}}a=b\mathit{AT}15.00,\\ \{a\to <\mathit{\text{state}}>\mathit{AT}<\mathit{\text{time}}>,\\ b\to \mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS}}<\mathit{\text{state}}>\}>.\end{array}$$

As seen, this equation satisfies sentential condition, because

$$\begin{array}{l}s\left[\delta \right]=\mathit{\text{AREA}}\mathit{\text{GREEN}}\mathit{\text{VALLEY\hspace{0.17em}IS}}<\mathit{\text{state}}>\mathit{AT}<\mathit{\text{time}}>\in \mathit{SF}\left(G_t\right),\\ s^{\prime }\left[\delta \right]=\mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS}}<\mathit{\text{state}}>\mathit{AT}15.00\in \mathit{SF}\left(G_t\right).\end{array}$$

According to Eq. (73),

$\mathrm{V}\left(a,\delta \right)=\left\{\mathit{\text{IN\hspace{0.17em}NORMAL\hspace{0.17em}STATE}}\mathit{AT}\right\}\cdot T\cup \left\{\mathit{\text{SMOKED}}\mathit{AT}\right\}\cdot T\mathrm{V}\left(b,\delta \right)=\left\{\mathit{\text{AREA}}\right\}\cdot S\cdot \left\{\mathit{\text{IS\hspace{0.17em}IN\hspace{0.17em}NORMAL\hspace{0.17em}STATE}}\mathit{AT}\right\}\cup \left\{\mathit{\text{AREA}}\right\}\cdot S\cdot \left\{\mathit{\text{IS\hspace{0.17em}SMOKED}}\right\}$ , where $T$ is the set of strings, explicating time ( $00.00,00.01,\dots ,23.58,23.59$ ), while S is the set of names of the monitored areas.

Terminal substitution

$$\begin{array}{l}s=\{a\to \mathit{\text{SMOKED}}\mathit{AT}15.00,\\ b\to \mathit{\text{AREA}}\mathit{\text{GREEN}}\mathit{\text{VALLEY\hspace{0.17em}IS\hspace{0.17em}SMOKED}}\}\end{array}$$

is the solution of the presented WECFL. $∎$

As seen, in general case the set of solutions of WECFL may be infinite, and the problem is to find finite representation of this set.

Let us consider two sentential forms $x$ and $x^{\prime }$ of unambiguous and acyclic CF grammar $G$ . Each of them defines generated (derived) from it set of strings, being words of language $L\left(G\right)$ :

$$W_x=\left\{w|x\stackrel{\ast }{\Rightarrow }w\&w\in V^{\ast }\right\},$$ E79

$$W_y=\left\{w|y\stackrel{\ast }{\Rightarrow }w\&w\in V^{\ast }\right\}.$$ E80

And therefore SF $x$ and $x^{\prime }$ are finite representations of sets $W_x$ and $W_y$ , both being subsets of language $L\left(G\right)$ . This obstacle serves as background for the following statement, representing necessary solution.

Statement 1 [51]. If

$$W=W_x\cap W_{x^{\prime }}\ne \left\{\varnothing \right\},$$ E81

then there exists SF y such that

$$W=\left\{w|x\stackrel{\ast }{\Rightarrow }y\&x^{\prime }\stackrel{\ast }{\Rightarrow }y\&y\stackrel{\ast }{\Rightarrow }w\&w\in V^{\ast }\right\}.∎$$ E82

Verbally, non-empty intersection of sets $W_x$ and $W_y$ is the subset of language $L\left(G\right)$ , in which words are generated from $\mathit{SF}y$ , which itself is generated from $\mathit{SF}x$ and $x^{\prime }$ simultaneously.

Example 9. Consider SF $s\left[d\right]$ and $s^{\prime }\left[d\right]$ from Example 8. As seen, $\mathit{SF}$

$$y=\mathit{\text{AREA}}\mathit{\text{GREEN}}\mathit{\text{VALLEY\hspace{0.17em}IS}}<\mathit{\text{state}}>\mathit{AT}15.00$$

is the finite representation of intersection $W_{s\left[d\right]}\cap W_{s^{\prime }\left[d\right]}$ . $∎$

Thus SF y from Eq. (82) is nothing else than required finite representation of the non-empty intersection (81).

This finding is a basis for constructing the set of solutions $D\left[s=s^{\prime },\delta \right]$ . Let us begin from the case where all variables, having place in WECFL (or, just the same, in term $s{s}^{\prime }$ ), enter it once, i.e., there is no more than one occurrence of any variable in $s{s}^{\prime }$ .

Obviously, if

$$W=\mathrm{V}\left(s,\delta \right)\cap \mathrm{V}\left(s^{\prime },\delta \right)=\left\{\varnothing \right\},$$ E83

then WECFL (70) does not have a solution, i.e.,

$$D\left[s=s^{\prime },\delta \right]=\left\{\varnothing \right\},$$ E84

and if $W\ne \left\{\varnothing \right\}$ , then, since $s\left[\delta \right]$ and $s^{\prime }\left[\delta \right]$ are sentential forms of CF grammar $G$ , there exists finite representation of set $W$ , being SF y generated (derived) from $s\left[\delta \right]$ and $s^{\prime }\left[\delta \right]$ simultaneously.

From this place it is clear, that finite representation of the set $D\left[s=s^{\prime },\delta \right]$ is set

$$\overline{\delta }=\left\{{\gamma }_1\to {\overline{\beta }}_1,\dots ,{\gamma }_l\to {\overline{\beta }}_l\right\},$$ E85

such that

$$W=\{w\mid s\left[\overline{\delta }\right]=s^{\prime }\left[\overline{\delta }\right]=y\&y\stackrel{\ast }{\Rightarrow }w\&w\in V^{\ast }\}.$$ E86

It is easy to verify that ${\overline{\beta }}_1,\dots ,{\overline{\beta }}_l$ are strings, containing terminal and nonterminal symbols, and being generated from strings ${\beta }_1,\dots ,{\beta }_l$ , respectively, by $s\left[\delta \right]\stackrel{\ast }{\Rightarrow y}$ and $s^{\prime }\left[y\right]\stackrel{\ast }{\Rightarrow y}$ .

Set $\overline{\delta }$ will be named unifier of WECFL (70). In accordance with Eqs. (54) and (55), we shall consider lower so-called maximal unifiers, corresponding to

$$y=\text{inf}\left\{s\left[\delta \right],s^{\prime }\left[\delta \right]\right\},$$ E87

where $y$ is the maximal lower bound of the considered two-element set.

Example 10. Let metadatabase be the same as in Example 2, and WECFL is

$$\begin{array}{l}<\mathit{\text{AREA}}a\mathit{\text{IS\hspace{0.17em}SMOKED}}\mathit{AT}t=b\mathit{AT}15.00,\\ \{a\to <\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>,\\ t\to <\mathit{\text{time}}>,\\ b\to \mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS}}<\mathit{\text{state}}>\}>.\end{array}$$

As seen,

$$\begin{array}{l}s\left[\delta \right]=\mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS\hspace{0.17em}SMOKED}}\mathit{AT}<\mathit{\text{time}}>,\\ s^{\prime }\left[\delta \right]=\mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS}}<\mathit{\text{state}}>\mathit{AT}15.00,\\ y=\text{inf}\left\{s\left[\delta \right],s^{\prime }\left[\delta \right]\right\}=\mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS\hspace{0.17em}SMOKED}}\mathit{AT}15.00,\end{array}$$

and thus

$$\begin{array}{l}\overline{\delta }=\{a\to <\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>,\\ t\to 15.00,\end{array}$$

$b\to \mathit{\text{AREA}}<\mathit{\text{name\hspace{0.17em}of\hspace{0.17em}area}}>\mathit{\text{IS\hspace{0.17em}SMOKED}}\}.∎$

Now we may return to DBI and introduce the so-called term data manipulation language (TDML), being the set of the so-called augmented terms $<s,d>$ , where $s$ is the term and $d$ is the SF-substitution. M-semantics of this language is similar to Eqs. (49), (54), and (55) and is obtained by replacement of $\mathit{SF}y$ by couple $<s,d>$ :

$$A_{t+1}^{s,d}=\left\{x|x\in X_t\&s\left[d\right]\stackrel{\ast }{\Rightarrow }x\right\},$$ E88

$${\overline{A}}_{t+1}^{s,d}=\left\{x|x\in X_t\&\exists \text{inf}\left\{s\left[d\right],x\right\}\right\},$$ E89

$${\overline{\overline{A}}}_{t+1}^{s,d}=\left\{\text{inf}\left\{s\left[d\right],x\right\}|x\in X_t\&\exists \text{inf}\left\{s\left[d\right],x\right\}\right\}.$$ E90

Moreover, from now we may use augmented terms or even their sets as N-facts. Corresponding equations, which describe M-semantics of TDML, much more useful from the practical point of view, are as follows:

$$A_{t+1}^{s,d}=\left\{<\overline{s},\overline{d}>|<\overline{s},\overline{d}>\in X_t\&s\left[d\right]\stackrel{\ast }{\Rightarrow }\overline{s}\left[\overline{d}\right]\right\},$$ E91

$${\overline{A}}_{t+1}^{s,d}=\left\{<\overline{s},\overline{d}>|<\overline{s},\overline{d}>\in X_t\&\exists \text{inf}\left\{s\left[d\right],\overline{s}\left[\overline{d}\right]\right\}\right\},$$ E92

$${\overline{\overline{A}}}_{t+1}^{s,d}=\left\{D\left[s=\overline{s},d\cup \overline{d}\right]|<\overline{s},\overline{d}>\in X_t\right\}.$$ E93

As may be seen, the last definition provides the most informative reply, containing maximal unifiers of WECFL, each corresponding N-fact, entering BDI.

The concerned reader may find the detailed consideration of WECFL, DBI algorithmics (including N-facts fusion), and key theoretical issues of SDB/DBI internal organization, providing associative access to the stored data as well as their compression, in [38, 39, 40].

All the said about TDML is sufficient for consideration of already mentioned knowledge representation, called augmented Post systems, being core of the deductive capabilities of “Set of Strings” Framework. APS are described in the separate chapter of this book.