NDLI: Reconcilable differences

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

Automatic verification of database-driven systems: a new frontier

Repair checking in inconsistent databases: algorithms and complexity

Structural characterizations of schema-mapping languages

Optimal splitters for database partitioning with size bounds

A compositional query algebra for second-order logic and uncertain databases

Incremental XPath evaluation

Towards a theory of search queries

Automatic construction of simple artifact-based business processes

Tight results for clustering and summarizing data streams

Containment of conjunctive queries on annotated relations

$Datalog^{±}:$ a unified approach to ontologies and integrity constraints

Consistent query answering under primary keys: a characterization of tractable queries

Query languages for data exchange: beyond unions of conjunctive queries

Efficient data structures for range-aggregate queries on trees

A logical account of uncertain databases based on linear logic

Efficient asymmetric inclusion between regular expression types

Reconcilable differences

TOP-K projection queries for probabilistic business processes

Analysis of sampling techniques for association rule mining

Optimizing user views for workflows

On approximating optimum repairs for functional dependency violations

Querying data sources that export infinite sets of views

Faster join-projects and sparse matrix multiplications

A compositional framework for complex queries over uncertain data

How big must complete XML query languages be?

Automatic verification of data-centric business processes

The average-case complexity of counting distinct elements

Reconcilable differences

Content Provider	ACM Digital Library
Author	Green, Todd J. Ives, Zachary G. Tannen, Val
Abstract	Exact query reformulation using views in positive relational languages is well understood, and has a variety of applications in query optimization and data sharing. Generalizations to larger fragments of the relational algebra (RA) --- specifically, support for the difference operator --- would increase the options available for query reformulation, and also apply to view adaptation (updating a materialized view in response to a modified view definition) and view maintenance. Unfortunately, most questions about queries become undecidable in the presence of difference/negation. We present a novel way of managing this difficulty via an excursion through a non-standard semantics, Z-relations, where tuples are annotated with positive or negative integers. We show that under Z-semantics RA queries have a normal form as a single difference of positive queries and this leads to the decidability of equivalence. In most real-world settings with difference, it is possible to convert the queries to this normal form. We give a sound and complete algorithm that explores all reformulations of an RA query (under Z-semantics) using a set of RA views, finitely bounding the search space with a simple and natural cost model. We investigate related complexity questions, and we also extend our results to queries with built-in predicates. Z-relations are interesting in their own right because they capture updates and data uniformly. However, our algorithm turns out to be sound and complete also for bag semantics, albeit necessarily only for a subclass of RA. This subclass turns out to be quite large and covers generously the applications of interest to us. We also show a subclass of RA where reformulation and evaluation under Z-semantics can be combined with duplicate elimination to obtain the answer under set semantics.
Starting Page	212
Ending Page	224
Page Count	13
File Format	PDF
ISBN	9781605584232
DOI	10.1145/1514894.1514920
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-03-23
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

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

Reconcilable differences (2009)

10.1177/1052562903256489 articlejournal of management education / december 2004doh / reconcilable differences? reconcilable differences? incorporating a trade-environment simulation into a management course.

Reconcilable differences?: united states-japan economic conflict (1993).

Occasionally reconcilable differences: bringing games and linear entertainment IP together, for better and for worse

Do Firm-to-Segment Reconcilable Earnings Differences Affect Stock Prices?

Reconcilable Differences : The Supreme Court Should Allow the Marriage of Brady and Plea Bargaining

A segment-based approach for reconcilable model transformation ( ESEC-FSE '07 )

Reconcilable differences: correcting medication errors at hospital admission and discharge

A segment-based approach for reconcilable model transformation ( ESEC-FSE companion '07 )

Reconcilable differences

Similar Documents

Reconcilable differences (2009)

10.1177/1052562903256489 articlejournal of management education / december 2004doh / reconcilable differences? reconcilable differences? incorporating a trade-environment simulation into a management course.

Reconcilable differences?: united states-japan economic conflict (1993).

Occasionally reconcilable differences: bringing games and linear entertainment IP together, for better and for worse

Do Firm-to-Segment Reconcilable Earnings Differences Affect Stock Prices?

Reconcilable Differences : The Supreme Court Should Allow the Marriage of Brady and Plea Bargaining

A segment-based approach for reconcilable model transformation ( ESEC-FSE '07 )

Reconcilable differences: correcting medication errors at hospital admission and discharge

A segment-based approach for reconcilable model transformation ( ESEC-FSE companion '07 )

Reconcilable differences