Cross-Model Conjunctive Queries over Relation and Tree-structured Data

Yuxing Chen; Valter Uotila; Jiaheng Lu; Zhen Hua Liu; Souripriya Das

doi:10.1007/978-3-031-00123-9_2

Cross-Model Conjunctive Queries over Relation and Tree-structured Data

Yuxing Chen, Valter Uotila, Jiaheng Lu, Zhen Hua Liu, Souripriya Das

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

Abstract

Conjunctive queries are the most basic and central class of database queries. With the continued growth of demands to manage and process the massive volume of different types of data, there is little research to study the conjunctive queries between relation and tree data. In this paper, we study Cross-Model Conjunctive Queries (CMCQs) over relation and tree-structured data (XML and JSON). To efficiently process CMCQs with bounded intermediate results we first encode tree nodes with position information. With tree node original label values and encoded position values, it allows our proposed algorithm CMJoin to join relations and tree data simultaneously, avoiding massive intermediate results. CMJoin achieves worst-case optimality in terms of the total result of label values and encoded position values. Experimental results demonstrate the efficiency and scalability of the proposed techniques to answer a CMCQ in terms of running time and intermediate result size.

Original language	English
Title of host publication	Database Systems for Advanced Applications. DASFAA 2022.
Editors	A Bhattacharya, JLM Li, D Agrawal, PK Reddy, M Mohania, A Mondal, Goyal, RU Kiran
Number of pages	17
Place of Publication	Cham
Publisher	Springer
Publication date	8 Apr 2022
Pages	21-37
ISBN (Print)	978-3-031-00122-2
ISBN (Electronic)	978-3-031-00123-9
DOIs	https://doi.org/10.1007/978-3-031-00123-9_2
Publication status	Published - 8 Apr 2022
MoE publication type	A4 Article in conference proceedings
Event	International Conference on Database Systems for Advanced Applications - Hyderabad, India Duration: 11 Apr 2022 → 14 Apr 2022 Conference number: 27

Publication series

Name	Lecture Notes in Computer Science
Publisher	SPRINGER INTERNATIONAL PUBLISHING AG
ISSN (Print)	0302-9743

Fields of Science

113 Computer and information sciences
Cross-model join
Worst-case optimal
Relation and tree data
XML

Access to Document

10.1007/978-3-031-00123-9_2

Conjunctive_queries_between_relations_and_tree_data__dasfaa_Accepted author manuscript, 436 KBLicence: Unspecified

Cite this

Chen, Y., Uotila, V., Lu, J., Liu, Z. H., & Das, S. (2022). Cross-Model Conjunctive Queries over Relation and Tree-structured Data. In A. Bhattacharya, JLM. Li, D. Agrawal, PK. Reddy, M. Mohania, A. Mondal, Goyal, & RU. Kiran (Eds.), Database Systems for Advanced Applications. DASFAA 2022. (pp. 21-37). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-031-00123-9_2

@inproceedings{e98bdc37e2094690a4a45ef6ba9fdb87,

title = "Cross-Model Conjunctive Queries over Relation and Tree-structured Data",

abstract = "Conjunctive queries are the most basic and central class of database queries. With the continued growth of demands to manage and process the massive volume of different types of data, there is little research to study the conjunctive queries between relation and tree data. In this paper, we study Cross-Model Conjunctive Queries (CMCQs) over relation and tree-structured data (XML and JSON). To efficiently process CMCQs with bounded intermediate results we first encode tree nodes with position information. With tree node original label values and encoded position values, it allows our proposed algorithm CMJoin to join relations and tree data simultaneously, avoiding massive intermediate results. CMJoin achieves worst-case optimality in terms of the total result of label values and encoded position values. Experimental results demonstrate the efficiency and scalability of the proposed techniques to answer a CMCQ in terms of running time and intermediate result size.",

keywords = "113 Computer and information sciences, Cross-model join, Worst-case optimal, Relation and tree data, XML",

author = "Yuxing Chen and Valter Uotila and Jiaheng Lu and Liu, {Zhen Hua} and Souripriya Das",

year = "2022",

month = apr,

day = "8",

doi = "10.1007/978-3-031-00123-9_2",

language = "English",

isbn = "978-3-031-00122-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "21--37",

editor = "A Bhattacharya and JLM Li and D Agrawal and PK Reddy and M Mohania and A Mondal and Goyal and RU Kiran",

booktitle = "Database Systems for Advanced Applications. DASFAA 2022.",

address = "Switzerland",

note = "International Conference on Database Systems for Advanced Applications, DASFAA ; Conference date: 11-04-2022 Through 14-04-2022",

}

Chen, Y, Uotila, V , Lu, J, Liu, ZH & Das, S 2022, Cross-Model Conjunctive Queries over Relation and Tree-structured Data. in A Bhattacharya, JLM Li, D Agrawal, PK Reddy, M Mohania, A Mondal, Goyal & RU Kiran (eds), Database Systems for Advanced Applications. DASFAA 2022.. Lecture Notes in Computer Science, Springer, Cham, pp. 21-37, International Conference on Database Systems for Advanced Applications, Hyderabad, India, 11/04/2022. https://doi.org/10.1007/978-3-031-00123-9_2

Cross-Model Conjunctive Queries over Relation and Tree-structured Data. / Chen, Yuxing; Uotila, Valter ; Lu, Jiaheng et al.
Database Systems for Advanced Applications. DASFAA 2022.. ed. / A Bhattacharya; JLM Li; D Agrawal; PK Reddy; M Mohania; A Mondal; Goyal; RU Kiran. Cham: Springer, 2022. p. 21-37 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Cross-Model Conjunctive Queries over Relation and Tree-structured Data

AU - Chen, Yuxing

AU - Uotila, Valter

AU - Lu, Jiaheng

AU - Liu, Zhen Hua

AU - Das, Souripriya

N1 - Conference code: 27

PY - 2022/4/8

Y1 - 2022/4/8

N2 - Conjunctive queries are the most basic and central class of database queries. With the continued growth of demands to manage and process the massive volume of different types of data, there is little research to study the conjunctive queries between relation and tree data. In this paper, we study Cross-Model Conjunctive Queries (CMCQs) over relation and tree-structured data (XML and JSON). To efficiently process CMCQs with bounded intermediate results we first encode tree nodes with position information. With tree node original label values and encoded position values, it allows our proposed algorithm CMJoin to join relations and tree data simultaneously, avoiding massive intermediate results. CMJoin achieves worst-case optimality in terms of the total result of label values and encoded position values. Experimental results demonstrate the efficiency and scalability of the proposed techniques to answer a CMCQ in terms of running time and intermediate result size.

AB - Conjunctive queries are the most basic and central class of database queries. With the continued growth of demands to manage and process the massive volume of different types of data, there is little research to study the conjunctive queries between relation and tree data. In this paper, we study Cross-Model Conjunctive Queries (CMCQs) over relation and tree-structured data (XML and JSON). To efficiently process CMCQs with bounded intermediate results we first encode tree nodes with position information. With tree node original label values and encoded position values, it allows our proposed algorithm CMJoin to join relations and tree data simultaneously, avoiding massive intermediate results. CMJoin achieves worst-case optimality in terms of the total result of label values and encoded position values. Experimental results demonstrate the efficiency and scalability of the proposed techniques to answer a CMCQ in terms of running time and intermediate result size.

KW - 113 Computer and information sciences

KW - Cross-model join

KW - Worst-case optimal

KW - Relation and tree data

KW - XML

U2 - 10.1007/978-3-031-00123-9_2

DO - 10.1007/978-3-031-00123-9_2

M3 - Conference contribution

SN - 978-3-031-00122-2

T3 - Lecture Notes in Computer Science

SP - 21

EP - 37

BT - Database Systems for Advanced Applications. DASFAA 2022.

A2 - Bhattacharya, A

A2 - Li, JLM

A2 - Agrawal, D

A2 - Reddy, PK

A2 - Mohania, M

A2 - Mondal, A

A2 - Goyal, null

A2 - Kiran, RU

PB - Springer

CY - Cham

T2 - International Conference on Database Systems for Advanced Applications

Y2 - 11 April 2022 through 14 April 2022

ER -