Article

Free access

A graphical query language supporting recursion

Authors:

Isabel F. Cruz,

Alberto O. Mendelzon,

Peter T. WoodAuthors Info & Claims

SIGMOD '87: Proceedings of the 1987 ACM SIGMOD international conference on Management of data

Pages 323 - 330

https://doi.org/10.1145/38713.38749

Published: 01 December 1987 Publication History

Abstract

We define a language G for querying data represented as a labeled graph G. By considering G as a relation, this graphical query language can be viewed as a relational query language, and its expressive power can be compared to that of other relational query languages. We do not propose G as an alternative to general purpose relational query languages, but rather as a complementary language in which recursive queries are simple to formulate. The user is aided in this formulation by means of a graphical interface. The provision of regular expressions in G allows recursive queries more general than transitive closure to be posed, although the language is not as powerful as those based on function-free Horn clauses. However, we hope to be able to exploit well-known graph algorithms in evaluating recursive queries efficiently, a topic which has received widespread attention recently.

References

[1]

A V AHO, J E HOPCROFF, AND J D ULLMAN, The Design and Analysts of Computer Algoruhms, Addison-Wesley, 1974

Digital Library

[2]

A V AHO, Y SAGIV, AND J D ULLMAN, "Efficmnt Opttm#zalaon of a Class of RelaUonal Expressions," ACM Trans on Database Syst, vol 4, no 4, pp 435-454, 1979

Digital Library

[3]

A V AHO AND J D ULLMAN, "Umversal#ty of Data Retrieval Languages," Proc 6th ACM Symp on Pnnctples of Programmmg Languages, pp 110-120, 1979

Digital Library

[4]

F BANCILHON, D MAIER, Y SAGIV, AND J D ULLMAN, "Magtc Sets and Other Strange Ways To Implement Logtc Programs," Proc 5th ACM SIGACT----SIGMOD Syrup on Prmctples of Database Systems, pp 1-15, 1986

Digital Library

[5]

A K CHANDRA AND D HAREL, "Horn Clause Quenes and Generahzauons," J Logtc Programming, vol 2, no 1, pp 1-15, 1985 OngmaUy appeared as "Horn Clauses and the F1xpomt Query H#erarchy", Proc 1st ACM SIGACT--- SIGMOD Symp on Prmctples of Database Systems, pp 158-163, 1982

Digital Library

[6]

A K CHANDRA AND P M MERLIN, "OpUmal Irnplementanon of Conjunctave Quenes m Relational Data Bases," Proc 9th ACM Symp on Theory of Computing, pp 77-90, 1977

Digital Library

[7]

E CLEMONS, "Design of an Extemal Schema Facility to Define and Process Recurswe Structures," ACM Trans on Database Syst, vol 6, no 2, pp 295-311,1981

Digital Library

[8]

W F CLOCKSIN AND C S MELLISH, Programmmg zn Prolog, Sprmger-Verlag, 1981

[9]

U DAYAL AND J M SMITH, "PROBE A Knowledge- Oriented Database Management System," m On Knowledge Base Management Systems Integrating Art#ctal lntelhgence and Database Technologws, ed M L Brod#e and J Mylopoulos, pp 227-257, Spnnger-Verlag, 1986

Digital Library

[10]

S FORTUNE, J HOPCROFT, AND J WYLLIE, "The Directed Subgraph Homeomorphlsm Problem," Theor Comput Sct,vol 10, pp 111-121,1980

[11]

S HEILER AND A ROSENTHAL, "G-WHIZ, a V#sual Interface for the Functional Model w#th Recurs#on," Proc 11th Conf on Very Large Data Bases, 1985

[12]

L J HENSCHEN AND S A NAQVI, "On Compdmg Quenes m Recurswe First-Order Databases," J ACM, vol 31, no 1, pp 47-85, 1984

Digital Library

[13]

AS LAPAUGH AND R L R/VEST, "The Subgraph Homeomorphtsm Problem," Proc lOth Ann ACM Syrup on Theory of Computing, pp 40-50, 1978

Digital Library

[14]

A O MENDELZON AND P T WOOD, "A Graplucal Query Language Supporting Recurslon," Tech Report CSRI-183, Umv of Toronto, 1986

[15]

A ROSENTHAL# S HEILER, U DAYAL, AND F MANOLA, "Traversal Recurston A Practmal Approach to Supporting Recumve Apphcaaons," Proc ACM SIGMOD Conf on Management ofData, pp 166-176, 1986

Digital Library

[16]

D SACCA AND C ZANIOLO, "On the ImplementaUon of a Simple Class of Logm Quenes," Proc 5th ACM SIGACT--81GMOD Syrup on Prmctples of Database Systems, pp 16-23, 1986

Digital Library

[17]

J D ULLMAN, "Implementauon of Logical Query Languages for Databases," ACM Trans on Database Syst, vol 10, no 3, pp 289-321, 1985 Originally appeared as Stanford Urav, Dept of Computer Science TR (May 1984)

Digital Library

[18]

MY VARDI, "The Complextty of Relauonal Query Languages," Proc 14th Ann ACM Symp on Theory of Computmg, pp 137-146, 1982

Digital Library

[19]

M M ZLOOF, "Query by Example Operauons on the Transmve Closure," IBM Research Report, RC5526, 1976

Cited By

Bollen EHendrix RKuijpers B(2024)Managing data of sensor-equipped transportation networks using graph databasesGeoscientific Instrumentation, Methods and Data Systems10.5194/gi-13-353-202413:2(353-371)Online publication date: 27-Nov-2024
https://doi.org/10.5194/gi-13-353-2024
David CFrancis NMarsault V(2024)Distinct Shortest Walk Enumeration for RPQsProceedings of the ACM on Management of Data10.1145/36516012:2(1-22)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651601
Farías BMartens WRojas CVrgoč D(2024)PathFinder: Returning Paths in Graph QueriesThe Semantic Web – ISWC 202410.1007/978-3-031-77850-6_8(135-154)Online publication date: 27-Nov-2024
https://doi.org/10.1007/978-3-031-77850-6_8
Show More Cited By

Index Terms

A graphical query language supporting recursion

Recommendations

A graphical query language supporting recursion

We define a language G for querying data represented as a labeled graph G. By considering G as a relation, this graphical query language can be viewed as a relational query language, and its expressive power can be compared to that of other relational ...
Ontology based graphical query language supporting recursion
KES'10: Proceedings of the 14th international conference on Knowledge-based and intelligent information and engineering systems: Part I

Text based queries often lead tend to be complex, and may result in non user friendly query structures. However, querying information systems using visual means, even for complex queries has proven to be more efficient and effective as compared to text ...
A Graphical Query Language: VISUAL and Its Query Processing

This paper describes VISUAL, a graphical icon-based query language with a user-friendly graphical user interface for scientific databases and its query processing techniques. VISUAL is suitable for domains where visualization of the relationships is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '87: Proceedings of the 1987 ACM SIGMOD international conference on Management of data

December 1987

509 pages

ISBN:0897912365

DOI:10.1145/38713

Editor:
Umeshwar Dayal

ACM SIGMOD Record Volume 16, Issue 3
Dec. 1987
503 pages
ISSN:0163-5808
DOI:10.1145/38714
Editor:
Umeshwar Dayal
Issue’s Table of Contents

Copyright © 1987 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

219
Total Citations
View Citations
1,110
Total Downloads

Downloads (Last 12 months)192
Downloads (Last 6 weeks)20

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bollen EHendrix RKuijpers B(2024)Managing data of sensor-equipped transportation networks using graph databasesGeoscientific Instrumentation, Methods and Data Systems10.5194/gi-13-353-202413:2(353-371)Online publication date: 27-Nov-2024
https://doi.org/10.5194/gi-13-353-2024
David CFrancis NMarsault V(2024)Distinct Shortest Walk Enumeration for RPQsProceedings of the ACM on Management of Data10.1145/36516012:2(1-22)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651601
Farías BMartens WRojas CVrgoč D(2024)PathFinder: Returning Paths in Graph QueriesThe Semantic Web – ISWC 202410.1007/978-3-031-77850-6_8(135-154)Online publication date: 27-Nov-2024
https://doi.org/10.1007/978-3-031-77850-6_8
Figueira DRomero MGeerts FNgo HSintos S(2023)Conjunctive Regular Path Queries under Injective SemanticsProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588664(231-240)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3584372.3588664
Anadiotis AManolescu IMohanty M(2023)Integrating Connection Search in Graph Queries2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00200(2607-2620)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00200
Schmid M(2022)Conjunctive Regular Path Queries with Capture GroupsACM Transactions on Database Systems10.1145/351423047:2(1-52)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1145/3514230
Deutsch AFrancis NGreen AHare KLi BLibkin LLindaaker TMarsault VMartens WMichels JMurlak FPlantikow SSelmer Pvan Rest OVoigt HVrgoč DWu MZemke FIves ZBonifati AEl Abbadi A(2022)Graph Pattern Matching in GQL and SQL/PGQProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526057(2246-2258)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526057
Arroyuelo DHogan ANavarro GRojas-Ledesma J(2022)Time- and Space-Efficient Regular Path Queries2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00277(3091-3105)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00277
Schmid MSuciu DTao YWei Z(2020)Conjunctive Regular Path Queries with String VariablesProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3375395.3387663(361-374)Online publication date: 14-Jun-2020
https://dl.acm.org/doi/10.1145/3375395.3387663
Hellings JPilachowski CVan Gucht DGyssens MWu Y(2020)From Relation Algebra to Semi-join Algebra: An Approach to Graph Query OptimizationThe Computer Journal10.1093/comjnl/bxaa03164:5(789-811)Online publication date: 9-May-2020
https://doi.org/10.1093/comjnl/bxaa031
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents