NDLI: Querying Graphs with Data

Content Provider	ACM Digital Library
Author	Libkin, Leonid Martens, Wim Vrgo, Domagoj
Copyright Year	2016
Abstract	Graph databases have received much attention as of late due to numerous applications in which data is naturally viewed as a graph; these include social networks, RDF and the Semantic Web, biological databases, and many others. There are many proposals for query languages for graph databases that mainly fall into two categories. One views graphs as a particular kind of relational data and uses traditional relational mechanisms for querying. The other concentrates on querying the topology of the graph. These approaches, however, lack the ability to $\textit{combine}$ data and topology, which would allow queries asking how data changes along paths and patterns enveloping it. In this article, we present a comprehensive study of languages that enable such combination of data and topology querying. These languages come in two flavors. The first follows the standard approach of path queries, which specify how labels of edges change along a path, but now we extend them with ways of specifying how both labels and data change. From the complexity point of view, the right type of formalisms are subclasses of register automata. These, however, are not well suited for querying. To overcome this, we develop several types of extended regular expressions to specify paths with data and study their querying power and complexity. The second approach adopts the popular XML language XPath and extends it from XML documents to graphs. Depending on the exact set of allowed features, we have a family of languages, and our study shows that it includes efficient and highly expressive formalisms for querying both the structure of the data and the data itself.
Starting Page	1
Ending Page	53
Page Count	53
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2850413
Journal	Journal of the ACM (JACM)
Volume Number	63
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-03-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graph databases XPath Data values Navigational queries
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Querying Regular Graph Patterns

XPath evaluation in linear time

On the minimization of XPath queries

Addressable Data Graphs

On compiling queries in recursive first-order databases

On Databases with Incomplete Information

Querying graph databases with XPath

A VLSI decomposition of the deBruijn graph

XPath satisfiability in the presence of DTDs

Querying Graphs with Data

Similar Documents

Querying Regular Graph Patterns

XPath evaluation in linear time

On the minimization of XPath queries

Addressable Data Graphs

On compiling queries in recursive first-order databases

On Databases with Incomplete Information

Querying graph databases with XPath

A VLSI decomposition of the deBruijn graph

XPath satisfiability in the presence of DTDs

Querying Graphs with Data