A Formal Language Perspective on Factorized Representations

The principles of databases can be studied in the named perspective and the unnamed perspective, which are slightly different mathematical definitions of the relational model [6, Chapter 2]. Let us provide a bit of background on both, since the difference between them is important in this paper.

Let $\mathrm{𝖵𝖺𝗅}$ and $\mathrm{𝖠𝗍𝗍}$ be two disjoint countably infinite sets of values and attribute names. In the named perspective, a database tuple is defined as a function $t:X\to \mathrm{𝖵𝖺𝗅}$, where $X$ is a finite subset of $\mathrm{𝖠𝗍𝗍}$. Such functions $t$ are usually denoted as $⟨A_1:a_1,A_2:a_2,\mathrm{\dots },A_k:a_k⟩$, to say that $t(A_i)=a_i$ for every $i\in k$. Notice that tuples are unordered in the sense that $⟨A:a,B:b⟩$ and $⟨B:b,A:a⟩$ denote the same function. The arity of $t$ is $|X|$. A database relation is a set of tuples that are defined over the same set $X$. A schema in the named perspective assigns a finite set of attribute names to each relation $R$ in the database. The semantics is that each tuple in $R$ should then be a tuple over the set of attribute names assigned by the schema.

A path in a graph is usually an ordered sequence. (Sometimes containing only nodes, sometimes only edges, and sometimes nodes and edges depending on the concrete definition of the graph or multigraph.) Such paths can therefore be seen as ordered tuples of the form $(u_1,\mathrm{\dots },u_n)$, where $u_1,\mathrm{\dots },u_n$ are objects in the graph.

In the unnamed perspective, a ($k$-ary) database tuple is simply an element of ${\mathrm{𝖵𝖺𝗅}}^k$. A database relation is a finite set of tuples of the same arity. We define schemas in the unnamed perspective a bit differently from the standard definition [6, Chapter 2], in order to be closer to the named perspective. (In the standard definition, a schema simply assigns an arity to each relation name $R$. The semantics is that each tuple in $R$ should have the arity that is assigned by the schema.)

For defining unnamed factorized relations (uFR), we follow the intuition that factorized relations are relational algebra expressions that can use names to re-use subexpressions [55]. We also follow [55] in disallowing unions of $\mathrm{\varnothing }$ with non-empty relations. Let $X\subseteq \mathrm{𝖭𝖺𝗆𝖾𝗌}$ be a finite set of expression names and let $\mathrm{𝑎𝑟}:X\to \mathbb{N}$ be a function that associates an arity to each name in $X$. A relation expression that references $X$, or $X$-expression for short, is a relational algebra expression built from singletons, products, unions, and names from $X$. We inductively define $X$-expressions $E$ and their associated arity $\mathrm{𝑎𝑟}(E)$ as follows:

(empty)

$E=\mathrm{\varnothing }$ is an $X$-expression with $\mathrm{𝑎𝑟}(E)=0$;

(nullary tuple)

$E=⟨⟩$ is an $X$-expression with $\mathrm{𝑎𝑟}(E)=0$;

(singleton)

$E=⟨a⟩$ is an $X$-expression for each $a\in \mathrm{𝖵𝖺𝗅}$, with $\mathrm{𝑎𝑟}(E)=1$;

(name reference)

$E=N$ is an $X$-expression for each $N\in X$, with $\mathrm{𝑎𝑟}(E)=\mathrm{𝑎𝑟}(N)$;

(union)

for $X$-expressions $E_1,\mathrm{\dots },E_n$ with $\mathrm{𝑎𝑟}(E_1)=\mathrm{\cdots }=\mathrm{𝑎𝑟}(E_n)$, we have that $E=(E_1\cup \mathrm{\cdots }\cup E_n)$ is an $X$-expression with $\mathrm{𝑎𝑟}(E)=\mathrm{𝑎𝑟}(E_1)=\mathrm{\cdots }=\mathrm{𝑎𝑟}(E_n)$;

(product)

for $X$-expressions $E_1,\mathrm{\dots },E_n$, we have that $E=(E_1\times \mathrm{\cdots }\times E_n)$ is an $X$-expression with $\mathrm{𝑎𝑟}(E)={\sum }_{i\in [n]}\mathrm{𝑎𝑟}(E_i)$.

Note that the expression $E_n$ does not use name references. Hence, $E_n$ can be evaluated without resolving references, and the result is a relation $R_n$. Once we have $R_n$, we can construct $R_{n-1}$ from $E_n$ by replacing $N_n$ with $R_n$. We continue this way until we obtain $R_1$, which is a $k$-ary relation, and is the relation that $F$ represents. We denote this relation, $R_1$, by $⟦F⟧$. Furthermore, we will denote $R_i$ by $⟦N_i⟧$ for every $i\in [n]$.

Note that, since $D$ is a set, we should indicate which element is $S$. Indeed, choosing a different start symbol changes $⟦F⟧$ (and may make some parts of $F$ useless since they cannot be reached from $S$). One may use a notational convention that we always take $S$ to be the first name that we write down in $D$, as is done in [55, Section 4.2].

We refer to the $d$-representations of Olteanu and Zavodny [55] as named factorized relations (nFR). For an nFR $F$, we use $⟦F⟧$ to denote the named relation $R$ represented by $F$.¹¹1$⟦F⟧$ is formally defined in [55]. The definition is completely analogous to Definition 2.1 but starts from tuples in the unnamed perspective. We therefore do not repeat the definition here. Although the definitions of named and unnamed factorized relations are similar, we show that unnamed factorized relations can be exponentially more succinct than named factorized relations and vice versa. In the direction from uFRs to nFRs, the exponential size difference is due to the capability of uFRs to be able to factorize “horizontally” and can be alleviated by imposing that every column uses different values. The exponential size difference in the other direction is due to the unordered nature of nFRs and tuples in the named perspective.

In order to compare uFRs with nFRs, we need to explain when we consider an nFR and a uFR to be equivalent. We consider the standard conversion between named and unnamed database relations in [6, Chapter 2] and write $\text{unnamed}(R)$ for the unnamed relation obtained from converting the named relation $R$ to the unnamed perspective. (Intuitively, the conversion assumes a fixed ordering on relation-attribute pairs and converts tuples $⟨A_1:a_1,\mathrm{\dots },A_k:a_k⟩$ in a named relation $R$ into tuples $(a_1,\mathrm{\dots },a_k)$.) Finally, we say that an nFR $F_1$ and uFR $F_2$ are equivalent if $\text{unnamed}(⟦F_1⟧)=⟦F_2⟧$.

In this section we want to define when we consider a uFR and an ECFG to be isomorphic. To warm up, we first explain when we consider two ECFGs $G_1$ and $G_2$ to be isomorphic. Intuitively, this is the case when they are the same up to renaming of non-terminals. Formally, we define isomorphisms using a function $h:\mathrm{𝖭𝖺𝗆𝖾𝗌}\to \mathrm{𝖭𝖺𝗆𝖾𝗌}$ that we extend to regular expressions as follows:

Then, $G_1=(T_1,N_1,S_1,R_1)$ is isomorphic to $G_2=(T_2,N_2,S_2,R_2)$ if there is a bijective function $h:N_1\to N_2$ such that $h(S_1)=S_2$, for each rule $A\to e$ in $R_1$, the rule $h(A)\to h(e)$ is in $R_2$, and each rule in $R_2$ is of the form $h(A)\to h(e)$ for some rule $A\to e$ in $R_1$.

We want to extend this notion of isomorphism to factorized relations and want to maintain a property such as Observation 3.4 which says that, if the objects are syntactically isomorphic, also their semantics is the same. To this end, for a tuple $t=⟨a_1,\mathrm{\dots },a_k⟩$, we denote the word $a_1\mathrm{\cdots }{a}_k$ as $\mathrm{word}(t)$. Hence, $\mathrm{word}(⟨⟩)=\epsilon$. For a set $T$ of tuples, we define $\mathrm{word}(T):=\{\mathrm{word}(t)\mid t\in T\}$.

We now define isomorphisms between uFRs and (star-free) ECFGs. The idea is analogous as before, but with the difference that the Cartesian product operator ($\times$) in uFRs is replaced by the concatenation operator ($\cdot$) in ECFGs. That is, we define isomorphisms using a function $h:\mathrm{𝖭𝖺𝗆𝖾𝗌}\to \mathrm{𝖭𝖺𝗆𝖾𝗌}$ that we extend to $X$-expressions as follows:

A uFR $(N_1,D)$ with $D=\{N_1:=E_1,\mathrm{\dots },N_n:=E_n\}$ is isomorphic to an ECFG $G=(T,N,S,R)$ if there is a bijective function $h:\{N_1,\mathrm{\dots },N_n\}\to N$ such that

• $\mathrm{■}$

  the start symbol $S$ is $h(N_1)$;

• $\mathrm{■}$

  for every expression $N_i:=E_i$ in $D$, the rule $h(N_i)\to h(E_i)$ is in $R$; and

• $\mathrm{■}$

  for every rule $N\to e$ in $R$, there is an expression $N_i:=E_i$ in $D$ with $h(N_i)=N$ and $h(E_i)=e$.

We now observe that isomorphisms preserve the size and, in a strong sense, also the semantics of uFRs and ECFGs. To this end, the size $|E|$ of an $X$-expression or regular expression $E$ is defined to be the number of occurrences of symbols plus the number of occurrences of operators in $E$. For example, $|⟨a⟩|=1$, $|(⟨a⟩\cup (⟨⟩\times ⟨b⟩)|=5$, and $|{(a\cdot b)}^{\ast }|=4$. The size of a uFR (resp., ECFG) is the sum of the sizes of its $X$-expressions (resp., regular expressions).

A factorized relation $F$ defines a database relation, where all tuples have the same arity. An ECFG defining the same relation (i.e., $\mathrm{word}(⟦F⟧)$) defines a language in which each word has the same length (which is, in particular, finite).

Let $G=(V,N,S,R)$ be an ECFG. Notice that, if $G$ is trimmed and $L(G)$ is finite, then $G$ cannot use the Kleene star operator in a meaningful way. Indeed, it can only use subexpressions $e^{\ast }$ if $L(e)=\mathrm{\varnothing }$ or $L(e)=\epsilon$, in which case $L(e^{\ast })=\epsilon$. The same holds for recursion. We therefore assume from now on that ECFGs that define a finite language are non-recursive and do not use the Kleene star operator. We call a nonterminal $A\in N$ uniform length if every word $w\in L(A)$ has the same length. We say that $G$ is uniform length if $S$ is uniform length. We now prove that factorized relations are the same as uniform-length ECFGs.

Similarly, we say that a uniform-length ECFG $G$ has disjoint positions if, for every pair of words $a_1\mathrm{\cdots }{a}_k\in L(G)$ and $b_1\mathrm{\cdots }{b}_k\in L(G)$ we have that $a_i\ne b_j$ if $i\ne j$.

In the remainder of the paper, for an uFR $F$, we will refer to $\beta (F)$ as the CFG corresponding to $F$.

We define the membership problem for uFRs to be the problem that, given a tuple $t$ and uFR $F$, tests if $t\in ⟦F⟧$. The CYK algorithm [35] decides membership for context-free languages in polynomial time.

We call a uFR $(S,D)$ right-linear (resp., left-linear) if every expression in $D$ is of the form $A:=⟨⟩$ or $A:=\{b\}\times C$ for $A,C\in N$ and $b\in T$ (resp., $A:=⟨⟩$ or $A:=C\times \{b\}$). (The corresponding definition for CFGs is analogous.) Due to [35], we know that right-linear CFGs are isomorphic to non-deterministic finite automata. The isomorphism, formulated in terms of uFRs, is that a rule $A\to \{b\}\times C$ corresponds to a transition from state $A$ to state $C$ with label $b$, and a rule $A:=⟨⟩$ corresponds to $A$ being an accepting state. A state $A$ is a start state if $A$ does not occur on the right-hand side of a rule in $S$. (The argument for left-linear uFRs is analogous.)

Let us define the equivalence problem of uFRs as follows. Given two uFRs $F_1$ and $F_2$, is $⟦F_1⟧=⟦F_2⟧$? Likewise, the containment problem asks, given two uFRs $F_1$ and $F_2$, whether $⟦F_1⟧\subseteq ⟦F_2⟧$. Due to [61, Corollary 5.9], we now know

We recall that determinism in uFRs corresponds to unambiguity in context-free grammars and finite automata. In particular, Corollary 5.9 in [61], which shows that equivalence and containment of unambiguous finite automata is solvable in polynomial time is non-trivial. In fact, the result is even more general: it holds for $k$-ambiguous automata for every constant $k$. Here, $k$-ambiguity intuitively means that each tuple in $⟦F⟧$ is allowed to have up to $k$ derivation trees in $F$.

Filmus [28] proves a lower bound on the size of CFGs that, in terms of uFRs, is stated as follows.

In fact, the proofs of Corollary 4.4 and 4.1 use the fact that CFGs (uFRs) can be brought into Chomsky Normal Form [21], which may be yet another classical result that is useful for proving results on uFRs.

Corollary 4.2 allows us to connect recent results on counting problems for automata and grammars [7, 8, 45] to uFRs. For a class $𝒞$ uFRs, counting for $𝒞$ is the problem that, given a uFR $F\in 𝒞$, asks what is the cardinality of $⟦F⟧$. First, recall that the number of words of a given length $n$ in an unambiguous CFG (or ECFG) can be counted in polynomial time [29, Section I.5.4] by a simple dynamic programming approach.

For general right-linear uFRs, the counting problem is $\mathrm{\#}$P-complete, but the following is immediate from the existence of an FPRAS for $\mathrm{\#}$NFA [7] and Theorem 3.8.

Furthermore, the recent more efficient FPRAS for $\mathrm{\#}$NFA by Meel et al. [45] can be applied verbatim to counting for right-linear uFRs. In fact, Meel et al. [46] recently generalized the result to $\mathrm{\#}CFG$. The result is still unpublished, but it would imply:

Notice that counting for uFRs (and subclasses thereof) is a practically relevant question: it is the result of the COUNT DISTINCT query for a factorized representation.

In terms of enumeration, Dömösi shows that, given a context-free grammar $G$ and length $n$, the set of words in $L(G)$ of length $n$ can be enumerated with delay polynomial in $n$ [25]:

We note that, in the case of right-linear uFRs, more efficient algorithms are possible [1, 2]. The same holds if the uFR is deterministic [56]. For example, Muñoz and Riveros [49] considered Enumerable Compact Sets (ECS) as a data structure for output-linear delay algorithms. ECS can be viewed as context-free grammars in Chomsky Normal Form for finite languages (using a similar isomorphism as in Section 3.1). In terms of uFRs, [49] shows that, if the uFR is deterministic and $k$-bounded (which means that unions on right-hand sides have constant length), then all its tuples can be enumerated in output-linear delay.

We now consider a slightly more liberal relational data model in the sense that a database relation no longer needs to contain tuples of the same arity. The reason why we consider this case is twofold. First, this data model leads to representations for the finite languages, which is a fundamental class in formal language theory. Second, this data model is the underlying data model [57] for the query language Rel [58], implemented by RelationalAI. So it is used in practice. We say that a variable-length database relation is simply a finite set $R$ of tuples.

The correspondence between uFRs and ECFGs in Theorems 3.8 and 3.9 allows us to define a natural generalization of FRs for variable-length relations, which corresponds to ECFGs for finite languages. We inductively define variable-length $X$-expressions (vl-$X$-expression for short) $E$ as follows:

• $\mathrm{■}$

  $E=\mathrm{\varnothing }$ is a vl-$X$-expression;

• $\mathrm{■}$

  $E=⟨⟩$ is a vl-$X$-expression;

• $\mathrm{■}$

  for each $a\in \mathrm{𝖵𝖺𝗅}$, we have that $E=⟨a⟩$ is a vl-$X$-expression with $\mathrm{𝑎𝑟}(E)=1$ (singleton);

• $\mathrm{■}$

  for each $N\in X$, we have that $E=N$ is a vl-$X$-expression (name reference);

• $\mathrm{■}$

  for vl-$X$-expressions $E_1,\mathrm{\dots },E_n$ we have that

  • –

    $E=(E_1\cup \mathrm{\cdots }\cup E_n)$ is a vl-$X$-expression (union); and

  • –

    $E=(E_1\times \mathrm{\cdots }\times E_n)$ is a vl-$X$-expression (Cartesian product).

The semantics $⟦F⟧$ of a variable-length factorized relation $F$ is defined analogously as for FRs. The difference is that the result is now a variable-length database relation.

We use edge-labeled multigraphs as our abstraction of a graph database.⁴⁴4PMRs were originally defined on property graphs, which are more complex than edge-labeled graphs. The definition of PMRs presented here is therefore slightly simplified. A graph database is a tuple $G=(N,E,\text{lab})$, where $N$ is a finite set of nodes, $E\subseteq N\times N$ is a finite set of edges, and $\text{lab}:E\to \mathrm{𝖵𝖺𝗅}$ is a function that associates a label to each edge. A path in $G$ is a sequence of nodes $u_0,\mathrm{\dots },u_n$, where $(u_{i-1},u_i)\in E$ for every $i\in [n]$.

The semantics of PMRs is defined as follows. They can be used as a representation of a set or a multiset of paths. More precisely, we define $\mathrm{𝖲𝖯𝖺𝗍𝗁𝗌}(R)=\{\gamma (p)\mid p$ is a path from some node in $S$ to some node in $T$ in $R\}$. Notice that each $\gamma (p)$ is indeed a path in $G$, since $\gamma$ is a homomorphism. $\mathrm{𝖬𝖯𝖺𝗍𝗁𝗌}(R)$ is defined similarly, but it is a multiset, where the multiplicity of each path $p$ in $G$ is the number of paths $p^{\prime }$ in $R$ such that $\gamma (p^{\prime })=p$.

PMRs are closely connected to finite automata by design. One reason for this design choice is that graph pattern matching in languages such as Cypher, SQL/PGQ, and GQL starts with the evaluation of regular path queries, which match “regular” sets of paths.

We explain this connection next and assume familiarity with finite automata. In the following, we will denote nondeterministic finite automata (NFAs) as tuples $A=(\mathrm{\Sigma },Q,\delta ,I,F)$ where $\mathrm{\Sigma }$ is its symbols (or alphabet), $Q$ its finite set of states, $\delta$ its set of transitions of the form $q_1\stackrel{𝑎}{\to }{q}_2$ (meaning that, in state $q_1$, the automaton can go to state $q_2$ by reading the symbol $a$), $I\subseteq Q$ its set of initial states, and $F\subseteq Q$ its set of accepting states. As usual, we denote by $L(A)$ the language of $A$, which is the set of words accepted by $A$.

The connection between PMRs and NFAs is very close. Indeed, we can turn a PMR $R=(N,E,\gamma ,S,T)$ over graph $G=(N_G,E_G,\text{lab})$ into an NFA $N_R=(\mathrm{\Sigma },Q,\delta ,I,F)$ where

1. 1.

   the alphabet $\mathrm{\Sigma }$ is the set $N_G$ of nodes of $G$;

2. 2.

   the set $Q$ of states is $N\cup \{s\}$, where we assume $s\notin N$;

3. 3.

   for every edge $e=(u,v)\in E$, there is a transition $u\stackrel{\gamma (v)}{\to }v$;

4. 4.

   for every node $u\in S$, we have a transition $s\stackrel{\gamma (u)}{\to }u$;

5. 5.

   $I=\{s\}$; and $F=T$.

As usual, we denote by $L(N_R)$ the set of words accepted by $N_R$. The automaton $N_R$ accepts precisely the set of paths represented by $R$.

In fact, there also exists a multiset language of NFAs, denoted $ML(A)$, in which the multiplicity of each word $w\in ML(A)$ is the number of accepting runs that $A$ has on $w$. Analogously to Proposition 5.3, one can show the following.

The correspondence in Proposition 5.4 is interesting for the purposes of representing path multisets, because deciding for given NFAs $A_1$ and $A_2$ if $\mathrm{𝑀𝐿}(A_1)=\mathrm{𝑀𝐿}(A_2)$ is in polynomial time [63] if the NFAs do not have $\epsilon$-transitions, which is the case here. Deciding if $L(A_1)=L(A_2)$ on the other hand is pspace complete [48]. (The same complexities hold for the respective containment problems.) This can be interesting if we want to consider questions like finding optimal-size representations of a (multi)set of paths.

In this section, we identify a path $u_1,\mathrm{\dots },u_n$ with the database tuple $(u_1,\mathrm{\dots },u_n)$. Furthermore, for an uFR $F$ and PMR $R$, we compare $⟦F⟧$ with $\mathrm{𝖲𝖯𝖺𝗍𝗁𝗌}(R)$, i.e., we compare them under set semantics. (A similar comparison can be made when considering them both under bag semantics.) Under these assumptions, we have the following observation.

Theorems 5.6 and 5.9 also hold for variable-length (but finite) relations, as we considered in Section 4.6. The lower bounds are immediate from those results and the upper bound constructions are analogous.