PSR-SQUARES：基于程序空间约简器的SQL逆向合成系统

doi:10.11959/j.issn.1000-436x.2023203

Abstract

Abstract:

In order to address the issue of rapid growth of program space in SQUARES, which led to low efficiency in program synthesis, a program space reducer based on deep neural network (DNN) was introduced into the SQUARES framework.A given ＆lt;Queried tables, Query result＆gt; pair was represented as a 2D tensor which was used as input for a DNN.And the output of the DNN was the relevance vector of the target SQL statement synthesis rules.Based on the output of the DNN, the last N rules with weak correlation to the target SQL statement were eliminated, thereby shrinking the program search space and improving the system synthesis efficiency.The architecture of DNN, the method of generating training datasets, and the training process of DNN were described in detail.Furthermore, experimental comparisons between PSR-SQUARES and other representative SQL reverse synthesis systems were conducted.The results show that the overall performance of PSR-SQUARES is superior to other synthesis systems to varying degrees, with the average synthesis time reduced from 251 s in SQUARES to 130 s and the target program synthesis success rate increased from 80% to 89%.

Key words: program synthesis, SQL reverse synthesis, SQUARES, program space reducer, domain-specific language

CLC Number:

TP39

Quansheng DOU, Shun ZHANG, Hao PAN, Huixian WANG, Huanling TANG. PSR-SQUARES: SQL reverse synthesis system based on program space reducer[J]. Journal on Communications, 2023, 44(11): 249-259.

Figures/Tables 12

References 33

[1]	PARISOTTO E , MOHAMED A R , SINGH R ,et al. Neuro-symbolic program synthesis[J]. arXiv Preprint,arXiv:1611.01855, 2016.
[2]	SOLAR-LEZAMA A . Program synthesis by sketching[D]. Berkeley:University of California, 2008.
[3]	CHEN X , LIU C , SHIN R ,et al. Latent attention for if-then program synthesis[J]. arXiv Preprint,arXiv:1611.01867, 2016.
[4]	GU X D , ZHANG H Y , KIM S . Deep code search[C]// Proceedings of the 40th International Conference on Software Engineering. New York:ACM Press, 2018: 933-944.
[5]	LI C T , TARLOW D , GAUNT A L ,et al. Neural program lattices[C]// Proceedings of the International Conference on Learning Representations (ICLR).[S.l.]: OpenReview, 2017: 1-17.
[6]	DEVLIN J , UESATO J , BHUPATIRAJU S ,et al. RobustFill:neural program learning under noisy I/O[C]// Proceedings of the 34th International Conference on Machine Learning. New York:ACM Press, 2017: 990-998.
[7]	GULWANI S , POLOZOV O , SINGH R . Program synthesis[J]. Foundations and Trends in Programming Languages, 2017,4(1/2): 1-119.
[8]	DAS-SARMA A , PARAMESWARAN A , GARCIA-MOLINA H ,et al. Synthesizing view definitions from data[C]// Proceedings of the 13th International Conference on Database Theory. New York:ACM Press, 2010: 89-103.
[9]	TRAN Q T , CHAN C Y , PARTHASARATHY S . Query by output[C]// Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. New York:ACM Press, 2009: 535-548.
[10]	TRAN Q T , CHAN C Y , PARTHASARATHY S . Query reverse engineering[J]. The VLDB Journal, 2014,23(5): 721-746.
[11]	LI H , CHAN C Y , MAIER D . Query from examples[J]. Proceedings of the VLDB Endowment, 2015,8(13): 2158-2169.
[12]	ZHANG S , SUN Y Y . Automatically synthesizing SQL queries from input-output examples[C]// Proceedings of 2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE). Piscataway:IEEE Press, 2014: 224-234.
[13]	WANG C L , CHEUNG A , BODIK R . Synthesizing highly expressive SQL queries from input-output examples[C]// Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York:ACM Press, 2017: 452-466.
[14]	WANG C L , CHEUNG A , BODIK R . Interactive query synthesis from input-output examples[C]// Proceedings of the 2017 ACM International Conference on Management of Data. New York:ACM Press, 2017: 1631-1634.
[15]	TAN W C , ZHANG M H , ELMELEEGY H ,et al. Reverse engineering aggregation queries[J]. Proceedings of the VLDB Endowment, 2017,10(11): 1394-1405.
[16]	TAN W C , ZHANG M H , ELMELEEGY H ,et al. REGAL⁺[J]. Proceedings of the VLDB Endowment, 2018,11(12): 1982-1985.
[17]	KHURANA K , HARITSA J R . UNMASQUE:a hidden SQL query extractor[J]. Proceedings of the VLDB Endowment, 2020,13(12): 2809-2812.
[18]	REHMAN M S , HUANG S L , ELMORE A J . A demonstration of RELIC[J]. Proceedings of the VLDB Endowment, 2021,14(12): 2795-2798.
[19]	QIN X , CHAI C , LUO Y ,et al. Interactively discovering and ranking desired tuples by data exploration[J]. The VLDB Journal, 2022,31(4): 753-777.
[20]	MARTINS R , CHEN J , CHEN Y J ,et al. Trinity:an extensible synthesis framework for data science[J]. Proceedings of the VLDB Endowment, 2019,12(12): 1914-1917.
[21]	ORVALHO P , TERRA-NEVES M , VENTURA M ,et al. SQUARES:a SQL synthesizer using query reverse engineering[J]. Proceedings of the VLDB Endowment, 2020,13(12): 2853-2856.
[22]	BAIK C , JIN Z J , CAFARELLA M ,et al. Duoquest:a dual-specification system for expressive SQL queries[C]// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2020: 2319-2329.
[23]	TAKENOUCHI K , ISHIO T , OKADA J ,et al. PATSQL:efficient synthesis of SQL queries from example tables with quick inference of projected columns[J]. arXiv Preprint,arXiv:2010.05807, 2020.
[24]	ZHOU X Y , BODIK R , CHEUNG A ,et al. Synthesizing analytical SQL queries from computation demonstration[C]// Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. New York:ACM Press, 2022: 168-182.
[25]	BALOG M , GAUNT A L , BROCKSCHMIDT M ,et al. DEEPCODER:learning to write programs[J]. arXiv Preprint,arXiv:1611.01989, 2016.
[26]	顾斌, 于波, 董晓刚 ,等. 程序智能合成技术研究进展[J]. 软件学报, 2021,32(5): 1373-1384.
	GU B , YU B , DONG X G ,et al. Intelligent program synthesis techniques:literature review[J]. Journal of Software, 2021,32(5): 1373-1384.
[27]	袁胜浩, 杨志斌, 张博林 ,等. 同步语言多线程代码生成的语义保持证明方法[J]. 计算机学报, 2020,43(11): 2216-2226.
	YUAN S H , YANG Z B , ZHANG B L ,et al. A semantic preservation proving method of multi-threaded code generation for synchronous language[J]. Chinese Journal of Computers, 2020,43(11): 2216-2226.
[28]	REED S , DE-FREITAS N . Neural programmer-interpreters[C]// Proceedings of the 4th International Conference on Learning Representations (ICLR).[S.l.]: OpenReview, 2016: 1-13.
[29]	GUO Z , JAMES M , JUSTO D ,et al. Program synthesis by type-guided abstraction refinement[J]. Proceedings of the ACM on Programming Languages, 2019,4: 1-28.
[30]	LE H , WANG Y , GOTMARE A D ,et al. CodeRL:mastering code generation through pretrained models and deep reinforcement learning[J]. arXiv Preprint,arXiv:2207.01780, 2022.
[31]	GULWANI S , MARRON M . NLyze:interactive programming by natural language for spreadsheet data analysis and manipulation[C]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2014: 803-814.
[32]	SHRIVASTAVA D , LAROCHELLE H , TARLOW D . Learning to combine per-example solutions for neural program synthesis[J]. arXiv Preprint,arXiv:2106.07175, 2021.
[33]	HUANG G , LIU Z , MAATEN L V D ,et al. Densely connected convolutional networks[C]// Proceedings of 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Piscataway:IEEE Press, 2017: 2261-2269.

Metrics

Recommended 0

No Suggested Reading articles found!

产生式左部	产生式右部
table→	input⁽⁰⁾\|inner_join(table,table)⁽¹⁾\|
	inner_join3(table,table,table)⁽²⁾\|
	inner_join4(table,table,table,table)⁽³⁾\|
	filter(table,filterCondition)⁽⁴⁾\|
	filters(table,filterCondition,filterCondition,op)⁽⁵⁾\|
	summariseGrouped(table,summmariseCondition,Cols)⁽⁶⁾\|
	anti_join(table,table)⁽⁷⁾\|left_join(table,table)⁽⁸⁾\|
	bind_rows(table,table)⁽⁹⁾\|intersect(table,selectCols,distinct)⁽¹⁰⁾
tableSelect→	select(table,selectCols,distinct)⁽¹¹⁾
op→	Or⁽¹²⁾\|And⁽¹³⁾
distinct→	true⁽¹⁴⁾\|false⁽¹⁵⁾
empty→	ε⁽¹⁶⁾

序号	样本编号	枚举轮数/轮	DSL程序
			L1=summariseGrouped(input0, meanage =
1	8	2	mean(age), level)
			P=select(L1, level,meanage, true)
			L1=summariseGrouped(input0, maxcost
			=max(cost),P_id)
2	18	4	L2=inner_join3(input0, L1, input1)
			L3=filter(L2,cost==maxcost)
			P=select(L3,P_id,S_name,distinct,true)
			L1=summariseGrouped(input2,
			S_key,S_name)
			L2=filters(L1, S_key==S4, S_key!=S4)
3	32	6	L3=filters(input0,S_key==S4, S_key!=S4)
			L4=inner_join4(L3, input1,L2, input0)
			L5=filter(L4,color ==green)
			P=select(L5, P_id,n, true)

合成系统	合成成功率	平均合成时间/s
Scythe	60%	893 s
Trinity	66%	724 s
SQUARES	80%	251 s
PSR-SQUARES-4	89%	130 s

PSR-SQUARES: SQL reverse synthesis system based on program space reducer

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 33

Related Articles 8

Metrics

Recommended 0

序号	样本编号	枚举轮数	SQUARES的合成时间/s	PSR-SQUARES-4的合成时间/s
1	7	1	3.2	3.1
2	24	4	3.3	3.3
3	1	2	3.7	2.3
4	12	2	3.7	3.6
5	20	5	3.4	3.3
6	21	2	3.4	3.9
7	13	1	3.4	2.5
8	10	3	3.9	3.4
9	37	4	3.9	3.6
10	19	5	4.1	3.3
11	44	5	4.1	5
12	8	2	4.7	3.3
13	36	5	5.2	4.2
14	14	3	5.5	4
15	39	4	7.2	4
16	50	5	7.6	4.8
17	23	5	8.2	3.6
18	28	5	8.4	4.8
19	31	5	8.5	6
20	11	1	8.7	3.4
21	32	6	11	4.4
22	5	3	14	3.8
23	30	6	14	10
24	2	3	23	9
25	29	6	33	5
26	48	4	40	3.3
27	4	3	40	4.3
28	41	5	43	8
29	55	4	69	4.4
30	26	5	74	39
31	45	4	80	3.4
32	3	3	82	9.7
33	54	4	89	12
34	40	5	93	5.2
35	42	5	103	3.9
36	52	4	128	14
37	6	3	128	17
38	15	3	168	6.5
39	53	4	438	29
40	49	4	920	14
41	51	4	1452	21
42	17	4	1898	11.8
43	18	4	1952	38
44	27	4	3065	309
45	35	5	—	3.9
46	47	4	—	256
47	33	6	—	549
48	9	6	—	2271
49	43	4	—	2658
50	46	4	—	—
51	38	5	—	—
52	22	5	—	—
53	16	6	—	—
54	25	6	—	—
55	34	6	—	—

[1]	Zheng HU,Baodan CHEN,Jia REN,Yupei FAN,Lian WANG. Research on sea surface NB-IoT coverage based on improved SPM [J]. Journal on Communications, 2019, 40(4): 21-32.
[2]	Guang-hai ZHOU,Zhao-long NING,Zhi-kui CHEN,Hua ZHONG,Yue-ming HU. Fault analysis and research of wireless sensor network based on kernel partial least squares [J]. Journal on Communications, 2017, 38(Z2): 94-98.
[3]	Ying GUO,Tian-shuang QIU,Hong TANG,Yong-wan PARK. Constant modulus algorithm for blind equalization under impulsive noise environments [J]. Journal on Communications, 2009, 30(4): 35-40.
[4]	Yi ZHANG,Fu-liang YIN,Zhe CHEN. Linear correction total least-squares approach to 3D acoustic source localization [J]. Journal on Communications, 2009, 30(12): 106-112.
[5]	Fang ZHAO,Yan MA,Hai-yong LUO,Quan LIN. Robust estimator for indoor node localization [J]. Journal on Communications, 2008, 29(11): 113-120.
[6]	Zhen-miao DENG,Yu LIU. Blind estimation of MPSK carrier frequency [J]. Journal on Communications, 2007, 28(2): 94-100.
[7]	Ye-qing QIAN. High-efficient adaptive predistortion structure for RF power amplifier linearization [J]. Journal on Communications, 2006, 27(5): 35-40.
[8]	HENHong-guang C,USheng-fa Y,HENZhen-kang S. [J]. Journal on Communications, 2006, 27(1): 64-68.