NDLI: Peer data exchange

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

Context-sensitive program analysis as database queries

XML data exchange: consistency and query answering

Schema mappings, data exchange, and metadata management

On the complexity of division and set joins in the relational algebra

Security analysis of cryptographically controlled access to XML documents

Computing cores for data exchange: new algorithms and practical solutions

Multi-structural databases

Buffering in query evaluation over XML streams

Operator placement for in-network stream query processing

XML type checking with macro tree transducers

Models and methods for privacy-preserving data publishing and analysis: invited tutorial

Estimating arbitrary subset sums with few probes

Differential constraints

XPath satisfiability in the presence of DTDs

On the complexity of nonrecursive XQuery and functional query languages on complex values

Simulatable auditing

Peer data exchange

A divide-and-merge methodology for clustering

Histograms revisited: when are histograms the best approximation method for aggregates over joins?

Join-distinct aggregate estimation over update streams

Regular rewriting of active XML and unambiguity

FTW: fast similarity search under the time warping distance

Diagnosis of asynchronous discrete event systems: datalog to the rescue!

Deciding well-definedness of XQuery fragments

An incremental algorithm for computing ranked full disjunctions

Practical privacy: the SuLQ framework

Composition of mappings given by embedded dependencies

Allocating isolation levels to transactions

Lower bounds for sorting with few random accesses to external memory

Space efficient mining of multigraph streams

Determining source contribution in integration systems

Space complexity of hierarchical heavy hitters in multi-dimensional data streams

Relative risk and odds ratio: a data mining perspective

Views and queries: determinacy and rewriting

Privacy-enhancing k-anonymization of customer data

Peer data exchange

Content Provider	ACM Digital Library
Author	Fuxman, Ariel Kolaitis, Phokion G. Miller, Renée J. Tan, Wang-Chiew
Abstract	In this paper, we introduce and study a framework, calledpeer data exchange, for sharing and exchanging data betweenpeers. This framework is a special case of a full-fledged peer datamanagement system and a generalization of data exchange between asource schema and a target schema. The motivation behind peer dataexchange is to model authority relationships between peers, where asource peer may contribute data to a target peer, specified usingsource-to-target constraints, and a target peer may usetarget-to-source constraints to restrict the data it is willing toreceive, but cannot modify the data of the source peer.A fundamental algorithmic problem in this framework is that ofdeciding the existence of a solution: given a source instance and atarget instance for a fixed peer data exchange setting, can thetarget instance be augmented in such a way that the source instanceand the augmented target instance satisfy all constraints of thesetting? We investigate the computational complexity of the problemfor peer data exchange settings in which the constraints are givenby tuple generating dependencies. We show that this problem isalways in NP, and that it can be NP-complete even for "acyclic"peer data exchange settings. We also show that the data complexityof the certain answers of target conjunctive queries is in coNP,and that it can be coNP-complete even for "acyclic" peer dataexchange settings.After this, we explore the boundary between tractability andintractability for the problem of deciding the existence of asolution. To this effect, we identify broad syntactic conditions onthe constraints between the peers under which testing for solutionsis solvable in polynomial time. These syntactic conditions includethe important special case of peer data exchange in which thesource-to-target constraints are arbitrary tuple generatingdependencies, but the target-to-source constraints arelocal-as-view dependencies. Finally, we show that the syntacticconditions we identified are tight, in the sense that minimalrelaxations of them lead to intractability.
Starting Page	160
Ending Page	171
Page Count	12
File Format	PDF
ISBN	1595930620
DOI	10.1145/1065167.1065188
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-13
Publisher Place	New York
Access Restriction	Subscribed
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