NDLI: Data exchange with arithmetic operations

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

From A to E: analyzing TPC's OLTP benchmarks: the obsolete, the ubiquitous, the unexplored

ProRea: live database migration for multi-tenant RDBMS with snapshot isolation

Eagle-eyed elephant: split-oriented indexing in Hadoop

Rapid experimentation for testing and tuning a production database deployment

Compromising privacy in precise query protocols

An automatic physical design tool for clustered column-stores

Utility-driven data acquisition in participatory sensing

Compressed feature-based filtering and verification approach for subgraph search

CINEMA: conformity-aware greedy algorithm for influence maximization in online social networks

Scalable top-k spatial keyword search

Skyline probability over uncertain preferences

SWORD: scalable workload-aware data placement for transactional workloads

Skyline queries in crowd-enabled databases

Enhanced stream processing in a DBMS kernel

Data exchange with arithmetic operations

Temporal query processing in Teradata

Cost exploration of data sharings in the cloud

Choosing the right crowd: expert finding in social networks

EXLEngine: executable schema mappings for statistical data processing

iPark: identifying parking spaces from trajectories

Tuning in action

Trust and reputation in and across virtual communities

Invisible loading: access-driven data transfer from raw files into database systems

Query-aware compression of join results

SWAT: a lightweight load balancing method for multitenant databases

Computing n-gram statistics in MapReduce

Towards context-aware search and analysis on social media data

Efficient privacy-aware record integration

Mining frequent serial episodes over uncertain sequence data

An RFID and particle filter-based indoor spatial query evaluation system

Efficient query answering against dynamic RDF databases

Pollux: towards scalable distributed real-time search on microblogs

Panorama: a semantic-aware application search framework

SkyDiver: a framework for skyline diversification

PMAX: tenant placement in multitenant databases for profit maximization

From stars to galaxies: skyline queries on aggregate data

Probabilistic inference of object identifications for event stream analytics

HIL: a high-level scripting language for entity integration

Near real-time analytics with IBM DB2 analytics accelerator

A performance comparison of parallel DBMSs and MapReduce on large-scale text analytics

Real-time wildfire monitoring using scientific database and linked data technologies

HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm

Limosa: a system for geographic user interest analysis in Twitter

PostgreSQL anomalous query detector

The W3C PROV family of specifications for modelling provenance metadata

History repeats itself: sensible and NonsenSQL aspects of the NoSQL hoopla

Web data indexing in the cloud: efficiency and cost reductions

CloudOptimizer: multi-tenancy for I/O-bound OLAP workloads

Processing multi-way spatial joins on map-reduce

Proactive natural language search engine: tapping into structured data on the web

Updating outsourced anatomized private databases

Efficient processing of containment queries on nested sets

A safe zone based approach for monitoring moving skyline queries

Efficient breadth-first search on large graphs with skewed degree distributions

Semantic queries by example

Selectivity estimation for hybrid queries over text-rich data graphs

Subspace global skyline query processing

Elastic online analytical processing on RAMCloud

Efficient top-k query answering using cached views

High-performance complex event processing using continuous sliding views

Optimizing query rewriting in ontology-based data access

AppSleuth: a tool for database tuning at the application level

Sparkler: supporting large-scale matrix factorization

Efficient multifaceted screening of job applicants

Entity discovery and annotation in tables

Accelerating spatial range queries

Processing XML queries and updates on map/reduce clusters

Schema mappings and data examples

Anomaly management using complex event processing: extending data base technology paper

Efficient and accurate strategies for differentially-private sliding window queries

Inferential time-decaying Bloom filters

An efficient layout method for a large collection of geographic data entries

CISC: clustered image search by conceptualization

In the Mood4: recommendation by examples

MinExp-card: limiting data collection using a smart card

YmalDB: a result-driven recommendation system for databases

PrivComp: a privacy-aware data service composition system

CrowdSeed: query processing on microblogs

ProQua: a system for evaluating logic-based scoring functions on uncertain relational data

Hive open research network platform

ProvenanceCurious: a tool to infer data provenance from scripts

Data exchange with arithmetic operations

Content Provider	ACM Digital Library
Author	Othman, Walied Kolaitis, Phokion G. ten Cate, Balder
Abstract	Data exchange is the problem of transforming data structured under a source schema into data structured under a target schema, taking into account structural relationships between the two schemas, which are described by a schema mapping. Existing schema-mapping languages lack the ability to express arithmetic operations, such as addition and multiplication, which naturally arise in data warehousing, ETL applications, and applications involving scientific data. We initiate the study of data exchange for arithmetic schema mappings, that is, schema mappings specified by source-to-target dependencies and target dependencies that may include arithmetic formulas interpreted over the algebraic real numbers (we restrict attention to algebraic real numbers to maintain finite presentability). We show that, for arithmetic schema mappings without target dependencies, the existence-of-solutions problem can be solved in polynomial time, and, if a solution exists, then a universal solution (suitably defined) exists and can be computed in polynomial time. In the case of arithmetic schema mappings with a weakly acyclic set of target dependencies, a universal solution may not exist, but a finite universal basis exists (if a solution exists) and can be computed in polynomial space. The existence-of-solutions problem turns out to be NP-hard, and solvable in PSpace. In fact, we show it is ∃R-complete, which means that it has the same complexity as the decision problem for the existential theory of the real numbers, or, equivalently, the problem of deciding whether or not a quantifier-free arithmetic formula has a solution over the real numbers. If we allow only linear arithmetic formulas in the schema mapping and in the query, interpreted over the rational numbers, then the existence-of-solutions problem is NP-complete. We obtain analogous complexity results for the data complexity of computing the certain answers of arithmetic conjunctive queries and linear arithmetic conjunctive queries.
Starting Page	537
Ending Page	548
Page Count	12
File Format	PDF
ISBN	9781450315975
DOI	10.1145/2452376.2452439
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-03-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Data exchange Schema mappings Arithmetic
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