Encoding Database Schemas with Relation-Aware Self-Attention for Text-to-SQL Parsers
Richard Shin


Semiclassical origin of asymmetric nuclear fission:
Nascent-fragment shell effect in periodic-orbit theory
    
 

^1Department of Physics, Nagoya Institute of Technology,
Nagoya 466-8555, Japan 

^2Yukawa Institute for Theoretical Physics, Kyoto 606-8502, Japan 

^3RIKEN Nishina Center, Wako 351-0198, Japan

    Submitted: 28 June 2019
 Revised: 20 August 2019
===========================================================================================================================================================================================================




  When translating natural language questions into SQL queries to answer questions from a database,
  we would like our methods to generalize to domains and database schemas outside of the training set.
  To handle complex questions and database schemas with a neural encoder-decoder paradigm, it is critical to properly encode the schema as part of the input with the question.
  In this paper, we use relation-aware self-attention within the encoder 
  so that it can reason about how the tables and columns in the provided schema relate to each other
  and use this information in interpreting the question.
  We achieve significant gains on the recently-released Spider dataset
  with  exact match accuracy, compared to the 18.96% reported in published work.






§ INTRODUCTION


The ability to effectively query databases with natural language has the potential to unlock the power of large datasets to the vast majority of users who are not proficient in the use of languages such as SQL.
As such, a large body of existing work has focused on the task of translating natural language questions into queries that existing database software can execute.


The release of large annotated datasets containing questions and the corresponding database queries has catalyzed significant progress in the field, by enabling the training of supervised learning models for the task <cit.>.
This progress has arrived not only in the form of improved accuracy on the test sets provided with the datasets, but also through an evolution of the problem formulation towards greater complexity more closely resembling real-world applications.


The recently-released Spider dataset <cit.> exemplifies greater realism in the task specification: the queries are written using SQL syntax, the dataset contains a large number of domains and schemas with no overlap between the train and test sets, and each schema contains multiple tables with many complicated questions being expressed in the queries.

Due to the extra difficulty caused by these factors, the best result on this dataset in published work achieves about 19% exact match accuracy on the development set <cit.>,
which is significantly worse compared to >80% exact matching accuracy reported for past datasets such as ATIS, GeoQuery, and WikiSQL <cit.>.



We posit that a central challenge of the multi-schema problem setting is generalization to new database schemas different from what was seen during training.


When the model needs to generate queries for arbitrary new schemas, it needs to take the relevant schema as an input and process it together with the question in order to generate the correct query.

Previous methods on the WikiSQL dataset <cit.> have also contended with the challenge of generalizing to arbitrary new schemas.
However, all schemas in this dataset are quite simple, as they only contain one table.
The model has no need to reason about the relationships between multiple tables in order to generate the correct query.
As such, models developed for this dataset have largely focused on innovations to the decoder for generating the query,
rather than the encoder for the question and the schema. 
In contrast, most real databases (including those in Spider) contain multiple tables with features such as foreign keys that link rows in one table to another. 
We hypothesize that to generate correct queries for such databases,
a model needs the ability to reason about how the tables and columns in the provided schema relate to each other
and use this information in interpreting the question.

In this paper, we develop a method to test this hypothesis.
First, we construct a directed graph (with labels on nodes and edges) over all of the elements of the schema.
This graph contains a node for each column or table, and an edge exists from one node to another if the two have an interesting relationship (e.g., the two nodes are columns which belong to the same table) with a label encoding that relationship.
Each node has an initial vector representation based on the words in the column or table's name.
We also obtain a vector representation for each word in the question.


For a fixed number of times, we then update each node and word representation based on all other node and word representations, taking the labels of edges between nodes into account. 
We use these updated representations with a tree-structured SQL decoder, which uses attention over them at each decoding step, and also points to the column and table representations when it needs to output a column or table reference in the query.

We empirically evaluate our method on the Spider dataset <cit.>, using a decoder based on <cit.>.
We achieve  exact set match accuracy on the development set, significantly higher than the published result of 18.9% <cit.>.
We further verify the utility of directly encoding the relationships within the schema with an ablation study.





§ PROBLEM FORMULATION AND MOTIVATION

Provided with a natural language question and a schema for a relational database, our goal is to generate the SQL query corresponding to the question.

The schema contains the following information, as depicted in Figure <ref>:

a list of tables in the database, each with a meaningful name (e.g., airlines, airports, and flights for an aviation database);
for each table, a list of columns, where
each column has a type such as  or ,
and some of them can be primary keys, used to uniquely identify each row;
finally, a column can have another column in a different table as its foreign key, which is used to link together rows across multiple tables.












As mentioned in the introduction, we would like our method to generalize to not only new questions, but also new schemas it has never seen during training time.





Using natural language to query databases has been a long-standing problem studied for many decades in the research community
<cit.>.
We identify several limitations of past work and problem settings:






  
  * Some datasets only concern themselves with one domain (e.g., US geography <cit.>).
  
  
  
  
  * Most datasets about one domain also contain only one database schema for the domain, so the system only needs to know how to generate queries for that single schema.
  
  * While WikiSQL <cit.> contains a large number of domains and schemas, each schema only contains one table in it.
  
  * Datasets containing only one domain and database necessarily contain overlaps between the train and test sets. Furthermore, as discussed by <cit.>, many existing datasets exhibit overlap in queries between the train and test sets, which limits their ability to test how models generalize to generating new queries.
  
  


The neural methods common in recent work follow an encoder-decoder paradigm,


and
past work has largely focused on improvements to the decoder part.




As such, the question of how best to encode the question and the schema has remained relatively under-studied.
Models developed using datasets which contain only one domain and schema ((a) and (b) above) typically internalize the schema within the learned parameters.
The popular WikiSQL dataset necessitates generalizing to new schemas at test time, so models developed for it also encode the schema together with the question;
however, as all these schemas only contain one table, the demands placed on the schema encoder are relatively light.

It is most useful if we can train a single model that can generalize to new domains and new database schemas,
where both the queries and the schemas have complicated structure that better reflect potential real-world applications.

The Spider dataset <cit.> provides an environment for evaluating this problem setting.
In this work, we study how to better encode the question and schema under these more demanding conditions.







§ EXISTING ENCODING SCHEMES

In this section, we review how some existing works (mostly for the WikiSQL dataset) addressed the challenge of encoding the input question and schema.








  
Encoding each element independently
In SQLNet <cit.> (for the WikiSQL dataset),
the name of each column, and the question, are separately processed using a bidirectional LSTM.
The LSTM outputs for the question tokens are utilized in the decoder using attention, and the final LSTM states of the columns with a pointer network.
Note that the encoding of each column is uninfluenced by which other column are present;
furthermore, the question is encoded entirely separately from the schema.

In SyntaxSQLNet <cit.> (for the Spider dataset),
the question is encoded identically as SQLNet, using a bidirectional LSTM.
Each column is encoded similarly, by using a bidirectional LSTM over the concatenation of the words in the column name, words in the table name, and column type (e.g., , ).



  
Encoding the columns jointly
TypeSQL <cit.> computes the encoding of each column by an elementwise averaging of the embeddings of the words in the name, and using a bidirectional LSTM over these averages (i.e., over all columns);
therefore, the encoding for each column depends on which other columns are present (and also their order, although that is arbitrary).



  
Using the schema while encoding the question
Using the information in the schema while encoding the question can help the decoder generate the correct query.
In TypeSQL, the word embeddings for each question token are concatenated with a type embedding;
in particular, question tokens appearing in a column name are specially marked.

Coarse2Fine <cit.> goes further
by using attention to gather information from the schema while encoding the question.




First, the input question is encoded using a bidirectional LSTM,
then an attention mechanism retrieves a weighted sum of the column embeddings for the LSTM state of each token.
These two are concatenated together and processed together in another bidirectional LSTM, to obtain the final embeddings for each question token.

IncSQL <cit.> uses “cross-serial attention”, also updating the column embeddings using the question token embeddings, in addition to the other direction used in Coarse2Fine.




















§ OUR APPROACH


In the previous section, we reviewed how previous neural methods developed for the text-to-SQL problem encode the input (the question and the database schema) for use in the decoder.
Several of these methods encode the question and the columns entirely independently (e.g., the embedding of a column is uninfluenced by other columns in the schema).



In contrast, we specifically seek interactions between schema elements within our encoder,
as explained in Sections <ref> and <ref>.
In this section, we describe how we encode the schema as a directed graph and use relation-aware self-attention to interpret it.
We will use the following notation:

    
  * c_i for each column in the schema. Each column contains words c_i,1, ⋯, c_i,|c_i|.
    
  * t_i for each table in the schema. Each table contains words t_i,1, ⋯, t_i,|t_i|.
    
  * q for the input question. The question contains words q_1, ⋯, q_|q|.











 §.§ Encoding the Schema as a Graph


To support reasoning about relationships between schema elements in the encoder,
we begin by representing the database schema using a directed graph 𝒢, where each node and edge has a label.
We represent each table and column in the schema as a node in this graph, labeled with the words in the name;
for columns, we prepend the type of the column to the label.
For each pair of nodes x and y in the graph, Table <ref> describes when there exists an edge from x to y and the label it should have.
Figure <ref> illustrates an example graph (although not all edges and labels are shown).



 §.§ Initial Encoding of the Input


We now obtain an initial representation for each of the nodes in the graph, as well as for the words in the input question.
For the graph nodes, we use a bidirectional LSTM over the words contained in the label.
We concatenate the output of the initial and final time steps of this LSTM to form the embedding for the node.
For the question, we also use a bidirectional LSTM over the words.
Formally, we perform the following:












    (𝐜_i,0^fwd, 𝐜_i,0^rev), ⋯, (𝐜_i,|c_i|^fwd, 𝐜_i,|c_i|^rev)
        = BiLSTM_Column(c_i^type, c_i,1, ⋯, c_i,|c_i|);   𝐜_i^init = Concat(𝐜_i,|c_i|^fwd, 𝐜_i,0^rev) 
    
    (𝐭_i,1^fwd, 𝐭_i,1^rev), ⋯, (𝐭_i,|t_i|^fwd, 𝐭_i,|t_i|^rev)
        = BiLSTM_Table(t_i,1, ⋯, t_i,|t_i|);   𝐭_i^init = Concat(𝐭_i,|c_i|^fwd, 𝐭_i,1^rev) 
    
    (𝐪_1^fwd, 𝐪_1^rev), ⋯, (𝐪_|q|^fwd, 𝐪_|q|^rev)
        = BiLSTM_Question(q_1, ⋯, q_|q|);   𝐪_i^init = Concat(𝐪_i^fwd, 𝐪_i^rev)

where each of the BiLSTM functions first lookup word embeddings for each of the input tokens.
The LSTMs do not share any parameters with each other.



 §.§ Relation-Aware Self-Attention


At this point, we have representations 𝐜_i^init, 𝐭_i^init, and 𝐪_i^init.
Similar to encoders used in some previous papers, these initial representations are independent of each other (uninfluenced by which other columns or tables are present).
Now, we would like to imbue these representations with the information in the schema graph.
We use a form of self-attention <cit.> that is relation-aware <cit.> to achieve this goal.

In one step of relation-aware self-attention, we begin with an input 𝐱 of n elements (where x_i ∈ℝ^d_x) and transform each x_i into y_i ∈ℝ^d_z.
We follow the formulation described in <cit.>:

    e_ij^(h)   = x_i W_Q^(h) (x_j W_K^(h) + 𝐫_𝐢𝐣^𝐊)^T/√(d_z / H);   α_ij^(h) = exp(e_ij^(h))/∑_l=1^n exp(e_il^(h))
    
        z_i^(h)   = ∑_j=1^n α_ij^(h) (x_j W_V^(h) + 𝐫_𝐢𝐣^𝐕);   
        z_i = Concat(z_i^(0), ⋯, z_i^(H)) 
    ỹ_i    = LayerNorm(x_i + z_i);   
        y_i = LayerNorm(ỹ_i + FC(ReLU(FC(ỹ_i)))

The r_ij terms encode the relationship between the two elements x_i and x_j in the input.
We explain how we obtain r_ij in the next part.































  
Application Within Our Encoder
At the start, we construct the input x of |c| + |t| + |q| elements using 𝐜_i^init, 𝐭_i^init, and 𝐪_i^init:

    x = (𝐜_1^init, ⋯, 𝐜_|c|^init,
             𝐭_1^init, ⋯, 𝐭_|t|^init, 
             𝐪_1^init, ⋯, 𝐪_|q|^init).

We then apply a stack of N relation-aware self-attention layers, where N is a hyperparameter.
We set d_z = d_x to facilitate this stacking.
The weights of the encoder layers are not tied; each layer has its own set of weights.

We define a discrete set of possible relation types, and map each type to an embedding to obtain r_ij^V and r_ij^K.
We need a value of r_ij for every pair of elements in x.
If x_i and x_j both correspond to nodes in 𝒢 (i.e. each is either a column or table) with an edge from x_i to x_j, then we use the label on that edge (possibilities listed in Table <ref>).

However, this is not sufficient to obtain r_ij for every pair of i and j.
In the graph we created for the schema, we have no nodes corresponding to the question words;
not every pair of nodes in the graph has an edge between them (the graph is not complete);
and we have no self-edges (for when i = j).
As such, we add more types beyond what is defined in Table <ref>:

    
  * If i = j, then Column-Identity or Table-Identity.
    
  * x_i ∈ question, x_j ∈ question: 
       Question-Dist-d, where d = clip(j - i, D); clip(a, D) = max(-D, min(D, a)). We use D = 2.
    
  * x_i ∈ question, x_j ∈column∪table; or x_i ∈column∪table, x_j ∈ question: 

       Question-Column, Question-Table, Column-Question or Table-Question
        depending on the type of x_i and x_j.
    
  * Otherwise, one of Column-Column, Column-Table, Table-Column, or Table-Table.

In the end, we add 2 + 5 + 4 + 4 types beyond the 10 in Table <ref>, for a total of 25 types.





















After processing through the stack of N encoder layers, we obtain

    (𝐜_1^final, ⋯, 𝐜_|c|^final,
          𝐭_1^final, ⋯, 𝐭_|t|^final, 
          𝐪_1^final, ⋯, 𝐪_|q|^final) 
         = y.

We use 𝐜_i^final, 𝐭_i^final, and 𝐪_i^final
in our decoder.



  
Comparison to Past Work

We use the same formulation of relation-aware self-attention as <cit.>.
However, that work only applied it to sequences of words in the context of machine translation, and as such, their r_ij only encoded the relative distance between two words.
We extend their work and show that relation-aware self-attention can effectively encode more complex relationships that exist within an unordered sets of elements (in this case, columns and tables within a database schema).

Compared to the encoders used in past work such as Coarse2Fine <cit.> and IncSQL <cit.>,
our novel use of relation-aware self-attention frees our encoder from spurious consideration of the order in which the columns and tables are presented in the schema (as the relations we have defined are not impacted by this order).



In their implementation, <cit.> 
share r_ij^K across the H heads and the b examples in a batch,
which meant they could use n parallel multiplications of bH × (d_Z / H) and (d_z / H) × n matrices.
This is possible as r_ij^K does not change across the batch when only encoding the relative distances between words.
However, due to the more varied relations between x_i in our work which are not shared by all elements in a batch,
we instead use bn parallel multiplications of H × (d_z / H) and (d_z / H) × n matrices,
exploiting the fact that we share r_ij^K across the H heads.
















 §.§ Decoder


Once we have obtained an encoding of the input, we used the decoder from <cit.> to generate the SQL query.
The decoder generates the SQL query as an abstract syntax tree in depth-first traversal order, 
by outputting a sequence of production rules that expand the last generated node in the tree.
However, following SyntaxSQLNet <cit.>, the decoder does not generate the FROM clause; rather, it is recovered afterwards with hand-written rules using the columns referred to in the remainder of the query.
The decoder is restricted to choosing only syntactically valid production rules, and therefore it always produces syntactically valid outputs.
To save space, we refer readers to <cit.>,
although we made the following modifications:

    
  * When the decoder needs to output a column, we use a pointer network based on scaled dot-product attention <cit.> which points to 𝐜_i^final and 𝐭_i^final.
    
    
    
  * At each step, the decoder accesses the encoder outputs 𝐜_i^final, 𝐭_i^final, and 𝐪_i^final using multi-head attention. The original decoder in <cit.> uses a simpler form of attention.










§ EXPERIMENTS

In this section, we describe the experiments we conducted to empirically validate our schema encoding approach.



 §.§ Experimental Setup

We implemented our model using PyTorch <cit.>.

Within the encoder, we use GloVe word embeddings and hold them fixed during training.





All word embeddings have dimension 300.
The bidirectional LSTMs have hidden size 128 per direction, and use the recurrent dropout method of <cit.> with rate 0.2.
Within the relation-aware self-attention layers, we set d_x = d_z = 256, H = 8, and use dropout with rate 0.1.
The position-wise feed-forward network has inner layer dimension 1024.
Inside the decoder, we use rule embeddings of size 128, node type embeddings of size 64, and a hidden size of 256 inside the LSTM with dropout rate 0.2 .



We used the Adam optimizer <cit.> with β_1 = 0.9, β_2 = 0.999, and ϵ = 10^-9, which are defaults in PyTorch.
During the first warmup_steps = max_steps / 20 steps of training, we linearly increase the learning rate from 0 to 10^-3.
Afterwards, the learning rate is annealed to 0, with formula 10^-3(1 - step - warmup_steps/max_steps - warmup_steps)^-0.5.
For all parameters, we used the default initialization method in PyTorch.
We use a batch size of 50 and train for up to 40,000 steps.



















































 §.§ Dataset and Metrics

We use the Spider dataset <cit.> for all our experiments.
As described by <cit.>, the training data contains 8,659 examples, including 1,659 examples (questions and queries, with the accompanying schemas) from the Restaurants <cit.>, GeoQuery <cit.>, Scholar <cit.>, Academic <cit.>, Yelp and IMDB <cit.> datasets.
We do not use the data augmentation scheme of <cit.>.

As <cit.> have kept the test set secret, we perform all evaluations using the publicly available development set.
There are 1,034 examples in the development set, containing schemas distinct from those in the training set.
We report results using the same metrics as <cit.>:
exact match accuracy on all development set examples, as well as after division into four levels of difficulty.

As in previous work, these metrics do not measure the model's performance on generating values within the queries.
We report results from the snapshot that obtained the best exact match accuracy across 3 repetitions of each configuration, except for the SyntaxSQLNet baseline where we reuse the pretrained model from the authors.

In addition to results on all of the development set, we also report results on subsets (Easy, Medium, Hard, and Extra Hard) partitioned by complexity of the query as defined by <cit.>.
These partitions make up
24.18%,
42.55%,
16.83%, and
16.44% respectively.



 §.§ Variants Tested

Our main result uses the encoder and decoder described previously, with the number N of relation-aware self-attention layers in the encoder set to 4.
To further study the utility of our scheme, we also tried the following variations, listed in Table <ref>.



  
Reducing the number of self-attention layers.
Set N = 0 and N = 2. With N = 0, there are no relation-aware self-attention layers; we set
𝐜_i^final = 𝐜_i^init,
𝐭_i^final = 𝐭_i^init, and
𝐪_i^final = 𝐪_i^init.
As such, the question words, the words in each column's name, and the words in each table's name are encoded separately using bidirectional LSTMs.



  
Removing the relation information from the encoder.
We would like to measure the impact of providing to the encoder the 25 relation types we defined earlier.
In particular, we want to see whether the self-attention mechanism is sufficient within the encoder to obtain a representation for each schema element that is aware of all of the other schema elements, even if we don't explicitly provide information about how the elements are related.

For “fewer relation types”, we exclude all of the types in Table <ref>, resulting in 15 rather than 25 possible types.
For “minimal relation types”, we further merge all of {Question,Column,Table}-{Question,Column,Table} relations into one, as well as {Column,Table}-Identity with Question-Dist-0, and so we only have 6 types.



  
Not using pretrained word embeddings.
The Spider dataset only contains 8,659 training examples, which is significantly smaller than many other datasets used in natural language processing.
Furthermore, there is also reduced overlap in the vocabulary between the training and validation/test sets, as they contain different database schemas and domains.
Therefore, we measure the impact of using word embeddings learned from only this dataset.
We construct a vocabulary consisting of all of the words in the columns, tables, and questions that occur at least 3 times in the training data (the words which occur in columns and tables are counted every time the corresponding schema is used by a question in the data);
for each, we randomly initialize an embedding of dimension 300.












§ RESULTS AND DISCUSSION


Table <ref> presents our exact match accuracy results on the development set of Spider. 
For the SyntaxSQLNet row, we obtained the results by running the pretrained model without data augmentation from <https://github.com/taoyds/syntaxSQL>.






Our method exceeds the performance of all other configurations tried, including all ablations.
In particular, we can see that our method strongly outperforms SyntaxSQLNet <cit.>, the best published baseline, achieving  exact match accuracy over the 18.96% of the previous work.



  
Reducing the number of self-attention layers.
We can see that the process of relation-aware self-attention is critical for the performance of this encoder, as the accuracy drops precipitiously when the self-attention layers are removed.
In particular, “no self-attention layers” uses an encoder very similar to SyntaxSQLNet's.
We observe fairly marginal gains by using 4 such layers (in “Our method”) as opposed to 2 (“2 self-attention layers”).



  
Removing the relation information from the encoder.
Comparing against the rows of “No self-attention layers” and “Our method”, we see that while having self-attention layers helps increase performance, it is the relation information provided to the encoder that is responsible for most of the gains.
The use of self-attention, on its own, contributes relatively little.




  
Not using pretrained word embeddings.
Given the small size of the training data, we confirm that using pretrained word embeddings helps significantly.


When we evaluate “No pretrained word embeddings” on the subset of the development set where all question words have a learned embedding (i.e. no UNKs in the question; 239 out of 1034 examples), then the exact match accuracy recovers to 40.17%; “Our method” achieves 50.21% on this subset,
substantialy reducing the gap in accuracy.













§ CONCLUSION

This paper proposes the use of relation-aware self-attention <cit.> when encoding a database schema and a natural language question for the purposes of synthesizing a SQL query.
We achieve significantly better results on the Spider dataset
than the best published result of <cit.>.
Our ablation study confirms the importance of encoding relations directly in the self-attention mechanism.


plainnat

