NDLI: Datalog redux: experience and conjecture

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

Datalog redux: experience and conjecture

Expressive languages for path queries over graph-structured data

The ACM PODS Alberto O. Mendelzon test-of-time-award 2010

From information to knowledge: harvesting entities and relationships from web sources

Optimal sampling from distributed streams

Optimizing linear counting queries under differential privacy

Information complexity: a tutorial

On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases

Foundations of schema mapping management

Characterizing schema mappings via data examples

Cache-oblivious hashing

Transducing Markov sequences

An optimal algorithm for the distinct elements problem

Incremental query evaluation in a ring of databases

Universally optimal privacy mechanisms for minimax agents

Capturing missing tuples and missing values

Certain answers for XML queries

Schema design for XML repositories: complexity and tractability

Understanding queries in a search database system

Performance guarantees for B-trees with different-sized atomic keys

Positive higher-order queries

Understanding cardinality estimation using entropy maximization

Fast Manhattan sketches in data streams

Towards an axiomatization of statistical privacy and utility

Computing query probability with incidence algebras

Simplifying XML schema: single-type approximations of regular tree languages

A learning algorithm for top-down XML transformations

When data dependencies over SQL tables meet the logics of paradox and S-3

Semantic query optimization in the presence of types

On probabilistic fixpoint and Markov chain query languages

The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability

Datalog redux: experience and conjecture

Content Provider	ACM Digital Library
Author	Hellerstein, Joseph M.
Abstract	There is growing urgency in computer science circles regarding an impending crisis in parallel programming. Emerging computing platforms, from multicore processors to cloud computing, predicate their performance growth on the development of software to harness parallelism. For the first time in the history of computing, the progress of Moore's Law depends on the productivity of software engineers. Unfortunately, parallel and distributed programming today is challenging even for the best programmers, and simply unworkable for the majority. There has never been a more urgent need for breakthroughs in programming models and languages. While parallel programming in general is considered very difficult, data parallelism has been very successful. The relational algebra parallelizes easily over large datasets, and SQL programmers have long reaped the benefits of parallelism without modifications to their code. This point has been rediscovered and amplified via recent enthusiasm for MapReduce programming and "Big Data", which have turned data parallelism into common culture across computing. As a result, it is increasingly attractive to tackle the challenge of parallel programming on the firm common ground of data parallelism: start with an easy-to-parallelize kernel-relational algebra-and extend it to general-purpose computation. This approach has clear precedents in database theory, where it has long been known that classical relational languages have natural Turing-complete extensions. At the same time that this crisis has been evolving, variants of Datalog have been seen cropping up in a wide range of practical settings, from security to robotics to compiler analysis. Over the past seven years, we have been exploring the use of Datalog-inspired languages in a variety of systems projects, with a focus on inherently parallel tasks in networking and distributed systems. The experience has been largely positive: we have demonstrated full-featured Datalog-based system implementations that are orders of magnitude more compact than equivalent imperatively-implemented systems, with competitive performance and significantly accelerated software evolution. Evidence is mounting that Datalog can serve as the basis of a much simpler family of languages for programming serious parallel and distributed software. This raises many questions that should warm the heart of a database theoretician. How does the complexity hierarchy of logic languages relate to parallel models of computation? Is there a suitable Coordination Complexity model that captures the realities of modern parallel hardware, where computation is cheap and coordination is expensive? Can the lens of logic provide better focus on what is "hard" to parallelize, what is "embarrassingly parallel", and points in between? Does our understanding of non-monotonic reasoning shed light on the ability of loosely-coupled distributed systems to guarantee eventual consistency? And finally, a question close to the heart of the PODS conference: if Datalog has been The Answer all these years, is parallel and distributed programming The Question it has been waiting for? In this talk and the paper that accompanies it, I present design patterns that arose in our experience building distributed and parallel software in the style of Datalog, and use them to motivate some initial conjectures relating to the questions above. The full paper was not available at the time these proceedings were printed, but can be found online by searching for the phrase "Springtime for Datalog".
Starting Page	1
Ending Page	2
Page Count	2
File Format	PDF QT / MOV
ISBN	9781450300339
DOI	10.1145/1807085.1807087
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Cloud computing Boom Datalog Distributed systems Bloom Parallelism Dedalus Overlog
Content Type	Video 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