# Data Synchronization: A Complete Theoretical Solution for Filesystems
## 3 Definitions
### Command Types and Execution Order  
A node value has type \(\mathbb{O}\), \(\mathbb{D}\), or \(\mathbb{F}\) depending on whether it is the empty value, a directory, or a file. For a command \(\sigma=\langle n,x,y\rangle\) the type of \(x\) is its _input type_ and the type of \(y\) is its _output type_. Depending on their input and output types commands can be partitioned into nine disjoint classes. To make their descriptions clearer, we use _patterns_. The command \(\langle n,x,y\rangle\) matches the pattern \((n,\mathsf{P}_{x},\mathsf{P}_{y})\) if the type of \(x\) is listed in \(\mathsf{P}_{x}\) and the type of \(y\) is listed in \(\mathsf{P}_{y}\). In a pattern the symbol \(\bullet\) matches any value. As an example, every command matches the pattern \(\langle\bullet,\mathbb{O}\mathbb{F}\mathbb{D},\mathbb{D}\mathbb{F}\mathbb{O}\rangle\). Structural commands change the type of the stored data, while _transient commands_ retain it. In other words, commands matching \(\langle\bullet,\mathbb{O},\mathbb{F}\mathbb{D}\rangle\), \(\langle\bullet,\mathbb{F},\mathbb{O}\mathbb{D}\rangle\) or \(\langle\bullet,\mathbb{D},\mathbb{O}\mathbb{F}\rangle\) are structural commands, while those matching \(\langle\bullet,\mathbb{O},\mathbb{O}\rangle\), \(\langle\bullet,\mathbb{F},\mathbb{F}\rangle\) or \(\langle\bullet,\mathbb{D},\mathbb{D}\rangle\) are transient ones. Commands with identical input and output values are _null commands_. Every null command is transient, and transient commands which are not null match the pattern \(\langle\bullet,\mathbb{F},\mathbb{F}\rangle\). If \(\sigma\) is a null command, then \(\sigma\sqsubseteq\lambda\) meaning that \(\sigma\) does not change the filesystem (but can break it), and if \(\sigma\sqsubseteq\lambda\) then \(\sigma\) is a null command. Structural commands are further split into _constructors_ and _destructors_. Construct commands upgrade the type from \(\mathbb{O}\) to \(\mathbb{F}\) to \(\mathbb{D}\), while destructors downgrade it. That is, constructors are commands matching \(\langle\bullet,\mathbb{O},\mathbb{F}\mathbb{D}\rangle\) or \(\langle\bullet,\mathbb{F},\mathbb{D}\rangle\), while the destructors match \(\langle\bullet,\mathbb{D},\mathbb{F}\mathbb{O}\rangle\) or \(\langle\bullet,\mathbb{F},\mathbb{O}\rangle\). Some command pairs on parent-child nodes can only be executed in a certain order. This notion is captured by the binary relation \(\sigma\ll\tau\) with the meaning that \(\sigma\) must precede \(\tau\) in the _execution order_. **Definition 1** (Execution order). : _For a command pair \(\sigma,\tau\in\Omega\) the binary relation \(\sigma\ll\tau\) holds if the pair matches either \(\langle n,\mathbb{D}\mathbb{F},\mathbb{O}\rangle\ll\langle\uparrow n,\mathbb{ D},\mathbb{F}\mathbb{O}\rangle\) or \(\langle\uparrow n,\mathbb{O}\mathbb{F},\mathbb{D}\rangle\ll\langle n,\mathbb{ O},\mathbb{F}\mathbb{D}\rangle\). An \(\ll\)-chain is a sequence of commands such that \(\sigma_{1}\ll\sigma_{2}\ll\cdots\ll\sigma_{k}\). An \(\ll\)-chain connects its first and last element._  
The first case in Definition 1 of the \(\ll\) relation corresponds to the requirement that a directory cannot be deleted when its descendants are not empty. The second case requires that before creating a file or directory, the directory holding it should exist. Observe that \(\sigma\ll\tau\) implies that both \(\sigma\) and \(\tau\) are structural commands on parent-child nodes, and either both are constructors or both are destructors.