NDLI: Schema Mappings for Data Graphs

Please wait, while we are loading the content...

Data Citation: A Computational Challenge

A Relational Framework for Classifier Engineering

Benchmarking the Chase

2017 ACM PODS Alberto O. Mendelzon Test-of-Time Award

How Fast can a Distributed Transaction Commit?

Statistical Relational Learning: Unifying AI & DB Perspectives on Structured Probabilistic Models

Dichotomies in Ontology-Mediated Querying with the Guarded Fragment

2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection

Communication Cost in Parallel Query Evaluation: A Tutorial

Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem

Stable Model Semantics for Tuple-Generating Dependencies Revisited

Querying Probabilistic Preferences in Databases

Efficient and Provable Multi-Query Optimization

The Semiring Framework for Database Provenance

JSON: Data model, Query languages and Schema specification

The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries

On Asymptotic Cost of Triangle Listing in Random Graphs

Streaming Algorithms for Measuring H-Impact

Schema Mappings for Data Graphs

Write-Optimized Skip Lists

Data Integration: After the Teenage Years

J-Logic: Logical Foundations for JSON Querying

Conjunctive Queries on Probabilistic Graphs: Combined Complexity

Efficiently Enumerating Minimal Triangulations

Efficient Matrix Sketching over Distributed Data

Dependencies for Graphs

Output-optimal Parallel Algorithms for Similarity Joins

Reverse Engineering SPJ-Queries from Examples

Circuit Treewidth, Sentential Decision, and Query Compilation

Counting and Enumerating (Preferred) Database Repairs

BPTree: An $ℓ_{2}$ Heavy Hitters Algorithm Using Constant Memory

A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries

Private Incremental Regression

Answering Conjunctive Queries under Updates

What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?

Schema Mappings for Data Graphs

Content Provider	ACM Digital Library
Author	Libkin, Leonid Francis, Nadime
Abstract	Schema mappings are a fundamental concept in data integration and exchange, and they have been thoroughly studied in different data models. For graph data, however, mappings have been studied in a restricted context that, unlike real-life graph databases, completely disregards the data they store. Our main goal is to understand query answering under graph schema mappings - in particular, in exchange and integration of graph data - for graph databases that mix graph structure with data. We show that adding data querying alters the picture in a significant way. As the model, we use data graphs: a theoretical abstraction of property graphs employed by graph database implementations. We start by showing a very strong negative result: using the simplest form of nontrivial navigation in mappings makes answering even simple queries that mix navigation and data undecidable. This result suggests that for the purposes of integration and exchange, schema mappings ought to exclude recursively defined navigation over target data. For such mappings and analogs of regular path queries that take data into account, query answering becomes decidable, although intractable. To restore tractability without imposing further restrictions on queries, we propose a new approach based on the use of null values that resemble usual nulls of relational DBMSs, as opposed to marked nulls one typically uses in integration and exchange tasks. If one moves away from path queries and considers more complex patterns, query answering becomes undecidable again, even for the simplest possible mappings.
Starting Page	389
Ending Page	401
Page Count	13
File Format	PDF
ISBN	9781450341981
DOI	10.1145/3034786.3056113
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-05-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Query answering Data integration and exchange Schema mappings Graph patterns Path queries Decidability and complexity Property graphs Data graphs Graph databases Nulls
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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