text:
@inproceedings{10.1145/3252633,
author = {Milo, Tova},
title = {Session Details: PODS Keynote},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252633},
doi = {10.1145/3252633},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902305,
author = {Vardi, Moshe Y.},
title = {A Theory of Regular Queries},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902305},
doi = {10.1145/2902251.2902305},
abstract = {A major theme in relational database theory is navigating the tradeoff between expressiveness and tractability for query languages, where the query-containment problem is considered a benchmark of tractability. The query class UCQ, consisting off unions of conjunctive queries, is a fragment of first-order logic that has a decidable query containment problem, but its expressiveness is limited. Extending UCQ with recursion yields Datalog, an expressive query language that has been studied extensively and has recently become popular in application areas such as declarative networking. Unfortunately, Datalog has an undecidable query containment problem. Identifying a fragment of Datalog that is expressive enough for applications but has a decidable query-containment problem has been an open problem for several years.In the area of graph databases, there has been a similar search for a query language that combines expressiveness and tractability. Because of the need to navigate along graph paths of unspecified length, transitive closure has been considered a fundamental operation. Query classes of increasing complexity -- using the operations of disjunction, conjunction, projection, and transitive closure -- have been studied, but the classes lacked natural closure properties. The class RQ of regular queries has emerged only recently as a natural query class that is closed under all of its operations and has a decidable query-containment problem.RQ turned out to be a fragment of Datalog where recursion can be used only to express transitive closure. Furthermore, it turns out that applying this idea to Datalog, that is, restricting recursion to the expression of transitive closure, does yield the long-sought goal -- an expressive fragment of Datalog with a decidable query-optimization problem.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {1–9},
numpages = {9},
keywords = {query containment datalog graph databases, query language},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252634,
author = {Van den Bussche, Jan},
title = {Session Details: PODS Award Talks + 1 Regular Paper},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252634},
doi = {10.1145/3252634},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2935710,
author = {Arenas, Marcelo and Buneman, Peter and Van den Bussche, Jan},
title = {2016 ACM PODS Alberto O. Mendelzon Test-of-Time Award},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2935710},
doi = {10.1145/2902251.2935710},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {11},
numpages = {1},
keywords = {test-of-time award},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902280,
author = {Abo Khamis, Mahmoud and Ngo, Hung Q. and Rudra, Atri},
title = {FAQ: Questions Asked Frequently},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902280},
doi = {10.1145/2902251.2902280},
abstract = {We define and study the Functional Aggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical models and logic. This is our main conceptual contribution. We then present a simple algorithm called "InsideOut" to solve this general problem. InsideOut is a variation of the traditional dynamic programming approach for constraint programming based on variable elimination. Our variation adds a couple of simple twists to basic variable elimination in order to deal with the generality of FAQ, to take full advantage of Grohe and Marx's fractional edge cover framework, and of the analysis of recent worst-case optimal relational join algorithms.As is the case with constraint programming and graphical model inference, to make InsideOut run efficiently we need to solve an optimization problem to compute an appropriate variable ordering. The main technical contribution of this work is a precise characterization of when a variable ordering is `semantically equivalent' to the variable ordering given by the input FAQ expression. Then, we design an approximation algorithm to find an equivalent variable ordering that has the best `fractional FAQ-width'. Our results imply a host of known and a few new results in graphical model inference, matrix operations, relational joins, and logic.We also briefly explain how recent algorithms on beyond worst-case analysis for joins and those for solving SAT and #SAT can be viewed as variable elimination to solve FAQ over compactly represented input functions.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {13–28},
numpages = {16},
keywords = {join algorithm, constraint satisfaction, logic, semiring, probabilistic graphical model, quantified conjunctive query},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902291,
author = {Sealfon, Adam},
title = {Shortest Paths and Distances with Differential Privacy},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902291},
doi = {10.1145/2902251.2902291},
abstract = {We introduce a model for differentially private analysis of weighted graphs in which the graph topology (υ,ε) is assumed to be public and the private information consists only of the edge weights ω : ε → R+. This can express hiding congestion patterns in a known system of roads. Differential privacy requires that the output of an algorithm provides little advantage, measured by privacy parameters ε and δ, for distinguishing between neighboring inputs, which are thought of as inputs that differ on the contribution of one individual. In our model, two weight functions w,w' are considered to be neighboring if they have l1 distance at most one.We study the problems of privately releasing a short path between a pair of vertices and of privately releasing approximate distances between all pairs of vertices. We are concerned with the approximation error, the difference between the length of the released path or released distance and the length of the shortest path or actual distance.For the problem of privately releasing a short path between a pair of vertices, we prove a lower bound of Ω(|υ|) on the additive approximation error for fixed privacy parameters ε,δ. We provide a differentially private algorithm that matches this error bound up to a logarithmic factor and releases paths between all pairs of vertices, not just a single pair. The approximation error achieved by our algorithm can be bounded by the number of edges on the shortest path, so we achieve better accuracy than the worst-case bound for pairs of vertices that are connected by a low-weight path consisting of o(|υ|) vertices.For the problem of privately releasing all-pairs distances, we show that for trees we can release all-pairs distances with approximation error $O(log2.5|υ|) for fixed privacy parameters. For arbitrary bounded-weight graphs with edge weights in [0,M] we can brelease all distances with approximation error \~{O}(√>(|υ|M).},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {29–41},
numpages = {13},
keywords = {all-pairs distances, differential privacy, shortest paths},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902295,
author = {Czerwinski, Wojciech and Martens, Wim and Niewerth, Matthias and Parys, Pawel},
title = {Minimization of Tree Pattern Queries},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902295},
doi = {10.1145/2902251.2902295},
abstract = {We investigate minimization of tree pattern queries that use the child relation, descendant relation, node labels, and wildcards. We prove that minimization for such tree patterns is Sigma2P-complete and thus solve a problem first attacked by Flesca, Furfaro, and Masciari in 2003. We first provide an example that shows that tree patterns cannot be minimized by deleting nodes. This example shows that the M-NR conjecture, which states that minimality of tree patterns is equivalent to their nonredundancy, is false. We then show how the example can be turned into a gadget that allows us to prove Sigma2P-completeness.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {43–54},
numpages = {12},
keywords = {trees, XPath, XML, graph databases, tree patterns, complexity, optimization},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252635,
author = {Tan, Wang-Chiew},
title = {Session Details: Gems of PODS},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252635},
doi = {10.1145/3252635},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902308,
author = {Fagin, Ronald},
title = {Optimal Score Aggregation Algorithms},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902308},
doi = {10.1145/2902251.2902308},
abstract = {Assume that there is a set of "voters" and a set of "candidates", where each voter assigns a numerical score to each candidate. There is a scoring function (such as the mean or the median), and a consensus ranking is obtained by applying the scoring function to each candidate's scores. The problem is to find the top k candidates, while minimizing the number of database accesses. The speaker will present an algorithm that is optimal in an extremely strong sense: not just in the worst case or the average case, but in every case! Even though the algorithm is only 10 lines long (!), the paper containing the algorithm won the 2014 G\"{o}del Prize, the top prize for a paper in theoretical computer science.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {55},
numpages = {1},
keywords = {score aggregation, aggregation algorithms, instance optimal},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902309,
author = {Gottlob, Georg and Greco, Gianluigi and Leone, Nicola and Scarcello, Francesco},
title = {Hypertree Decompositions: Questions and Answers},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902309},
doi = {10.1145/2902251.2902309},
abstract = {In the database context, the hypertree decomposition method is used for query optimization, whereby conjunctive queries having a low degree of cyclicity can be recognized and decomposed automatically, and efficiently evaluated. Hypertree decompositions were introduced at ACM PODS 1999. The present paper reviews' in form of questions and answers' the main relevant concepts and algorithms and surveys selected related work including applications and test results.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {57–74},
numpages = {18},
keywords = {tractability, acyclic queries, query evaluation, hypertree width, hypergraphs, decompositions, conjunctive queries},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252636,
author = {Suciu, Dan},
title = {Session Details: Session 1: Query Rewriting, Views, and Join Algorithms},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252636},
doi = {10.1145/3252636},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902286,
author = {Koch, Christoph and Lupei, Daniel and Tannen, Val},
title = {Incremental View Maintenance For Collection Programming},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902286},
doi = {10.1145/2902251.2902286},
abstract = {In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the materialized view more efficiently than via recomputation.In this work we propose the first solution for the efficient incrementalization of positive nested relational calculus (NRC+) on bags (with integer multiplicities). More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify NRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incremental maintenance for NRC+ is within the complexity class NC0 and we showcase how recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries [25], can also be applied to IncNRC+.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {75–90},
numpages = {16},
keywords = {higher-order delta derivation, collection programming, incremental computation, recursive ivm, incremental view maintenance, shredding transformation, nested relational algebra, nested relational calculus},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902293,
author = {Joglekar, Manas R. and Puttagunta, Rohan and R\'{e}, Christopher},
title = {AJAR: Aggregations and Joins over Annotated Relations},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902293},
doi = {10.1145/2902251.2902293},
abstract = {We study a class of aggregate-join queries with multiple aggregation operators evaluated over annotated relations. We show that straightforward extensions of standard multiway join algorithms and generalized hypertree decompositions (GHDs) provide best-known runtime guarantees. In contrast, prior work uses bespoke algorithms and data structures and does not match these guarantees. We extend the standard techniques by providing a complete characterization of (1) the set of orderings equivalent to a given ordering and (2) the set of GHDs valid with respect to the given ordering, i.e., GHDs that correctly answer a given aggregate-join query when provided to (simple variants of) standard join algorithms. We show by example that previous approaches are incomplete. The key technical consequence of our characterizations is a decomposition of a valid GHD into a set of (smaller) unconstrained GHDs, i.e., into a set of GHDs of sub-queries without aggregations. Since this decomposition is comprised of unconstrained GHDs, we are able to connect to the wide literature on GHDs for join query processing, thereby obtaining improved runtime bounds, MapReduce variants, and an efficient method to find approximately optimal GHDs.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {91–106},
numpages = {16},
keywords = {fractional hypertreewidth, join query, semiring, generalized hypertree decomposition, aggregation},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902294,
author = {Cao, Yang and Fan, Wenfei and Geerts, Floris and Lu, Ping},
title = {Bounded Query Rewriting Using Views},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902294},
doi = {10.1145/2902251.2902294},
abstract = {A query Q has a bounded rewriting using a set of views if there exists a query Q' expressed in the same language as Q, such that given a dataset D, Q(D) can be computed by Q' that accesses only cached views and a small fraction DQ of D. We consider datasets D that satisfy a set of access constraints, a combination of cardinality constraints and associated indices, such that the size |DQ| of DQ and the time to identify DQ are independent of |D|, no matter how big D is.This paper studies the problem for deciding whether a query has a bounded rewriting given a set V of views and a set A of access constraints. We establish the complexity of the problem for various query languages, from Σ3p-complete for conjunctive queries (CQ), to undecidable for relational algebra (FO). We show that the intractability for CQ is rather robust even for acyclic CQ with fixed V and A, and characterize when the problem is in PTIME. To make practical use of bounded rewriting, we provide an effective syntax for FO queries that have a bounded rewriting. The syntax characterizes a core subclass of such queries without sacrificing the expressive power, and can be checked in PTIME.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {107–119},
numpages = {13},
keywords = {big data, query answering, complexity},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902288,
author = {Gogacz, Tomasz and Marcinkowski, Jerzy},
title = {Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902288},
doi = {10.1145/2902251.2902288},
abstract = {We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of the Red Spider method invented in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance Q0, Q=(Q1, Q2, ... Qk) such that the set Q of CQs does not determine CQ Q0 but finitely determines it. Finally, we claim that while Q0 is finitely determined by Q, there is no FO-rewriting of Q0, with respect to Q},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {121–134},
numpages = {14},
keywords = {determinacy, undecidability, conjunctive queries},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902292,
author = {Hu, Xiao and Yi, Ke},
title = {Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902292},
doi = {10.1145/2902251.2902292},
abstract = {Nested-loop join is a worst-case I/O-optimal algorithm for 2 relations. Recently, a lot of efforts have been devoted to the "triangle query", for which an I/O-optimal algorithm is known. This paper extends these results to a fairly large class of acyclic joins. Acyclic joins can be computed optimally in internal memory using Yannakakis' algorithm from 1981, which simply performs a series of pairwise joins. However, no pairwise join algorithm can be I/O-optimal beyond 2 relations. To achieve I/O-optimality, the algorithm has to handle all the intermediate results carefully without writing them to disk. Unlike the optimal internal memory join algorithm which has a nice tight bound (the AGM bound), the I/O-complexity of joins turns out to be quite complex or even unknown. Yet, we are able to prove that our algorithm is I/O-optimal for certain classes of acyclic joins without deriving its bound explicitly.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {135–150},
numpages = {16},
keywords = {worst-case optimal, I/O-efficient algorithms, acyclic joins},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902285,
author = {Ahle, Thomas Dybdahl and Pagh, Rasmus and Razenshteyn, Ilya and Silvestri, Francesco},
title = {On the Complexity of Inner Product Similarity Join},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902285},
doi = {10.1145/2902251.2902285},
abstract = {A number of tasks in classification, information retrieval, recommendation systems, and record linkage reduce to the core problem of inner product similarity join (IPS join): identifying pairs of vectors in a collection that have a sufficiently large inner product. IPS join is well understood when vectors are normalized and some approximation of inner products is allowed. However, the general case where vectors may have any length appears much more challenging. Recently, new upper bounds based on asymmetric locality-sensitive hashing (ALSH) and asymmetric embeddings have emerged, but little has been known on the lower bound side. In this paper we initiate a systematic study of inner product similarity join, showing new lower and upper bounds. Our main results are: Approximation hardness of IPS join in subquadratic time, assuming the strong exponential time hypothesis. New upper and lower bounds for (A)LSH-based algorithms. In particular, we show that asymmetry can be avoided by relaxing the LSH definition to only consider the collision probability of distinct elements. A new indexing method for IPS based on linear sketches, implying that our hardness results are not far from being tight.Our technical contributions include new asymmetric embeddings that may be of independent interest. At the conceptual level we strive to provide greater clarity, for example by distinguishing among signed and unsigned variants of IPS join and shedding new light on the effect of asymmetry.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {151–164},
numpages = {14},
keywords = {asymmetric embeddings, LSH, joins, approximation hardness, inner product},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252637,
author = {Arenas, Marcelo},
title = {Session Details: PODS Tutorial 1},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252637},
doi = {10.1145/3252637},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902306,
author = {Cohen, Sara},
title = {Data Management for Social Networking},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902306},
doi = {10.1145/2902251.2902306},
abstract = {Social networks are fascinating and valuable datasets, which can be leveraged to better understand society, and to make inter-personal choices. This tutorial explores the fundamental issues that arise when storing and querying social data. The discussion is divided into three main parts. First, we consider some of the key computational problems that arise over the social graph structure, such as node centrality, link prediction, community detection and information diffusion. Second, we consider algorithmic challenges that leverage both the textual content and the graph structure of a social network, e.g., social search and querying, and team formation. Finally, we consider critical aspects of implementing a social network database management system, and discuss existing systems. In this tutorial, we also point out gaps between the state-of-the-art and desired features of a data management system for social networking, and discuss open research challenges.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {165–177},
numpages = {13},
keywords = {data management, social networks},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252638,
author = {David, Claire},
title = {Session Details: Session 2: Workflows and Incomplete Information},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252638},
doi = {10.1145/3252638},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902275,
author = {Deutsch, Alin and Li, Yuliang and Vianu, Victor},
title = {Verification of Hierarchical Artifact Systems},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902275},
doi = {10.1145/2902251.2902275},
abstract = {Data-driven workflows, of which IBM's Business Artifacts are a prime exponent, have been successfully deployed in practice, adopted in industrial standards, and have spawned a rich body of research in academia, focused primarily on static analysis. The present work represents a significant advance on the problem of artifact verification, by considering a much richer and more realistic model than in previous work, incorporating core elements of IBM's successful Guard-Stage-Milestone model. In particular, the model features task hierarchy, concurrency, and richer artifact data. It also allows database key and foreign key dependencies, as well as arithmetic constraints. The results show decidability of verification and establish its complexity, making use of novel techniques including a hierarchy of Vector Addition Systems and a variant of quantifier elimination tailored to our context.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {179–194},
numpages = {16},
keywords = {data-centric workflows, business process management, temporal logic, verification},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902300,
author = {Abdulla, Parosh Aziz and Aiswarya, C. and Atig, Mohamed Faouzi and Montali, Marco and Rezine, Othmane},
title = {Recency-Bounded Verification of Dynamic Database-Driven Systems},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902300},
doi = {10.1145/2902251.2902300},
abstract = {We propose a formalism to model database-driven systems, called database manipulating systems (DMS). The actions of a (DMS) modify the current instance of a relational database by adding new elements into the database, deleting tuples from the relations and adding tuples to the relations. The elements which are modified by an action are chosen by (full) first-order queries. (DMS) is a highly expressive model and can be thought of as a succinct representation of an infinite state relational transition system, in line with similar models proposed in the literature. We propose monadic second order logic (MSO-FO) to reason about sequences of database instances appearing along a run. Unsurprisingly, the linear-time model checking problem of (DMS) against (MSO-FO) is undecidable. Towards decidability, we propose under-approximate model checking of (DMS), where the under-approximation parameter is the "bound on recency". In a k-recency-bounded run, only the most recent k elements in the current active domain may be modified by an action. More runs can be verified by increasing the bound on recency. Our main result shows that recency-bounded model checking of (DMS) against (MSO-FO) is decidable, by a reduction to the satisfiability problem of MSO over nested words.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {195–210},
numpages = {16},
keywords = {nested words, formal verification, relational transition systems, data-aware dynamic systems, monadic second order logic, database driven dynamic systems, under-approximation, recency boundedness, model checking},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902297,
author = {Guagliardo, Paolo and Libkin, Leonid},
title = {Making SQL Queries Correct on Incomplete Databases: A Feasibility Study},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902297},
doi = {10.1145/2902251.2902297},
abstract = {Multiple issues with SQL's handling of nulls have been well documented. Having efficiency as its key goal, evaluation of SQL queries disregards the standard notion of correctness on incomplete databases - certain answers - due to its high complexity. As a result, it may produce answers that are just plain wrong. It was recently shown that SQL evaluation can be modified, at least for first-order queries, to return only correct answers. But while these modifications came with good theoretical complexity bounds, they have not been tested in practice. The goals of this proof-of-concept paper are to understand whether wrong answers can be produced by SQL queries in real-world scenarios, and whether proposed techniques for avoiding them can be made practically feasible.We use the TPC-H benchmark, and show that for some typical queries involving negation, wrong answers are very common. On the other hand, existing solutions for fixing the problem do not work in practice at all. By analyzing the reasons for this, we come up with a new modified way of rewriting SQL queries that restores correctness. We conduct experiments which show the feasibility of our solution: the small price tag it imposes can be often tolerated to ensure correct results, and we do not miss correct answers that the usual SQL evaluation produces. The overall conclusion is that correct evaluation can be realistically achieved in the presence of nulls, at least for the SQL fragment that corresponds to first-order queries.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {211–223},
numpages = {13},
keywords = {incomplete information, certain answers, TPC-H benchmark, query translation, nulls, experimental validation, SQL},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902298,
author = {Arenas, Marcelo and Ugarte, Mart\'{\i}n},
title = {Designing a Query Language for RDF: Marrying Open and Closed Worlds},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902298},
doi = {10.1145/2902251.2902298},
abstract = {When querying an RDF graph, a prominent feature is the possibility of extending the answer to a query with optional information. However, the definition of this feature in SPARQL --the standard RDF query language-- has raised some important issues. Most notably, the use of this feature increases the complexity of the evaluation problem, and its closed-world semantics is in conflict with the underlying open-world semantics of RDF. Many approaches for fixing such problems have been proposed, being the most prominent the introduction of the semantic notion of weakly-monotone SPARQL query. Weakly-monotone SPARQL queries have shaped the class of queries that conform to the open-world semantics of RDF. Unfortunately, finding an effective way of restricting SPARQL to the fragment of weakly-monotone queries has proven to be an elusive problem. In practice, the most widely adopted fragment for writing SPARQL queries is based on the syntactic notion of well designedness. This notion has proven to be a good approach for writing SPARQL queries, but its expressive power has yet to be fully understood. The starting point of this paper is to understand the relation between well-designed queries and the semantic notion of weak monotonicity. It is known that every well-designed SPARQL query is weakly monotone; as our first contribution we prove that the converse does not hold, even if an extension of this notion based on the use of disjunction is considered. Given this negative result, we embark on the task of defining syntactic fragments that are weakly-monotone, and have higher expressive power than the fragment of well-designed queries. To this end, we move to a more general scenario where infinite RDF graphs are also allowed, so that interpolation techniques studied for first-order logic can be applied. With the use of these techniques, we are able to define a new operator for SPARQL that gives rise to a query language with the desired properties (over finite and infinite RDF graphs). It should be noticed that every query in this fragment is weakly monotone if we restrict to the case of finite RDF graphs. Moreover, we use this result to provide a simple characterization of the class of monotone CONSTRUCT queries, that is, the class of SPARQL queries that produce RDF graphs as output. Finally, we pinpoint the complexity of the evaluation problem for the query languages identified in the paper.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {225–236},
numpages = {12},
keywords = {construct queries, incomplete information, computational complexity, query languages, semantic web},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252639,
author = {Roy, Sudeepa},
title = {Session Details: Session 3: Data Streams and Indexes},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252639},
doi = {10.1145/3252639},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902299,
author = {Murlak, Filip and Paperman, Charles and Pilipczuk, Micha\l{}},
title = {Schema Validation via Streaming Circuits},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902299},
doi = {10.1145/2902251.2902299},
abstract = {XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth - an acceptable assumption from the practical view-point. In this paper we refine this analysis by taking into account that data can be streamed block-by-block, rather then letter-by-letter, which provides opportunities to speed up the computation by parallelizing the processing of each block.For this purpose we introduce the model of streaming circuits, which process words of arbitrary length in blocks of fixed size, passing constant amount of information between blocks.This model allows us to transfer fundamental results about the circuit complexity of regular languages to the setting of streaming schema validation, which leads to effective constructions of streaming circuits of depth logarithmic in the block size, or even constant under certain assumptions on the input schema.For nested-relational DTDs, a practically motivated class of bounded-depth XML schemas, we provide an efficient construction yielding constant-depth streaming circuits with particularly good parameters.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {237–249},
numpages = {13},
keywords = {semi-structured data, nested-relational DTDs, streaming, schema validation, boolean circuits, XML},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902277,
author = {Felber, David and Ostrovsky, Rafail},
title = {Variability in Data Streams},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902277},
doi = {10.1145/2902251.2902277},
abstract = {We consider the problem of tracking with small relative error an integer function f(n) defined by a distributed update stream f'(n) in the distributed monitoring model. In this model, there are k sites over which the updates f'(n) are distributed, and they must communicate with a central coordinator to maintain an estimate of f(n).Existing streaming algorithms with worst-case guarantees for this problem assume f(n) to be monotone; there are very large lower bounds on the space requirements for summarizing a distributed non-monotonic stream, often linear in the size n of the stream. However, the input streams obtaining these lower bounds are highly variable, making relatively large jumps from one timestep to the next; in practice, the impact on f(n) of any single update f'(n) is usually small. What has heretofore been lacking is a framework for non-monotonic streams that admits algorithms whose worst-case performance is as good as existing algorithms for monotone streams and degrades gracefully for non-monotonic streams as those streams vary more quickly.In this paper we propose such a framework. We introduce a stream parameter, the "variability" v, deriving its definition in a way that shows it to be a natural parameter to consider for non-monotonic streams. It is also a useful parameter. From a theoretical perspective, we can adapt existing algorithms for monotone streams to work for non-monotonic streams, with only minor modifications, in such a way that they reduce to the monotone case when the stream happens to be monotone, and in such a way that we can refine the worst-case communication bounds from θ(n) to \~{O}v. From a practical perspective, we demonstrate that v can be small in practice by proving that v is O(log f(n)) for monotone streams and o(n) for streams that are "nearly" monotone or that are generated by random walks. We expect v to be o(n) for many other interesting input classes as well.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {251–260},
numpages = {10},
keywords = {counting, distributed monitoring model, variability, data stream, non-monotonic stream, tracking},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902282,
author = {Braverman, Vladimir and Chestnut, Stephen R. and Woodruff, David P. and Yang, Lin F.},
title = {Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902282},
doi = {10.1145/2902251.2902282},
abstract = {A central problem in the theory of algorithms for data streams is to determine which functions on a stream can be approximated in sublinear, and especially sub-polynomial or poly-logarithmic, space. Given a function g, we study the space complexity of approximating ∑i=1n g(|fi|), where f ∈ Zn is the frequency vector of a turnstile stream. This is a generalization of the well-known frequency moments problem, and previous results apply only when g is monotonic or has a special functional form. Our contribution is to give a condition such that, except for a narrow class of functions g, there is a space-efficient approximation algorithm for the sum if and only if g satisfies the condition. The functions g that we are able to characterize include all convex, concave, monotonic, polynomial, and trigonometric functions, among many others, and is the first such characterization for non-monotonic functions. Thus, for nearly all functions of one variable, we answer the open question from the celebrated paper of Alon, Matias and Szegedy (1996).},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {261–276},
numpages = {16},
keywords = {frequency moments, sketching, data streams},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902290,
author = {Rahul, Saladi and Tao, Yufei},
title = {Efficient Top-k Indexing via General Reductions},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902290},
doi = {10.1145/2902251.2902290},
abstract = {Let D be a set of n elements each associated with a real-valued weight, and Q be the set of all possible predicates allowed on those elements. Given a predicate in Q and integer k, a top-k query returns the k elements with the largest weights among the elements of D satisfying q. The corresponding data structure problem aims to store D in small space to allow every query to be answered efficiently. It is already known that, before settling the problem, one must be able to solve two degenerated accompanying problems: (i) prioritized reporting: given a predicate q ∈ Q and a real value τ, return all the elements of D satisfying q and having weights at least τ (ii) max reporting: top-k queries with k fixed to 1.In this paper we prove general reductions in external memory that explore the opposite direction. Our first reduction shows that, (under mild conditions) any prioritized reporting structure yields a static top-$k$ structure with only a slow-down in query time by a factor of O(logB n), where B is the block size. Our second reduction shows that if one additionally has a max reporting structure, then combining the two structures yields a top-k structure with no performance slow down (in space, query, and update) in expectation. These reductions significantly simplify the design of top-k structures, as we showcase on numerous problems including halfspace reporting, circular reporting, interval stabbing, point enclosure, and 3d dominance. All the techniques proposed work directly in the RAM model as well.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {277–288},
numpages = {12},
keywords = {external memory, ram, reductions, top-k, algorithms, data structures},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902276,
author = {Bender, Michael A. and Berry, Jonathan W. and Johnson, Rob and Kroeger, Thomas M. and McCauley, Samuel and Phillips, Cynthia A. and Simon, Bertrand and Singh, Shikha and Zage, David},
title = {Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902276},
doi = {10.1145/2902251.2902276},
abstract = {We present history-independent alternatives to a B-tree, the primary indexing data structure used in databases. A data structure is history independent (HI) if it is impossible to deduce any information by examining the bit representation of the data structure that is not already available through the API. We show how to build a history-independent cache-oblivious B-tree and a history-independent external-memory skip list. One of the main contributions is a data structure we build on the way---a history-independent packed-memory array (PMA). The PMA supports efficient range queries, one of the most important operations for answering database queries.Our HI PMA matches the asymptotic bounds of prior non-HI packed-memory arrays and sparse tables. Specifically, a PMA maintains a dynamic set of elements in sorted order in a linear-sized array. Inserts and deletes take an amortized O(log2 N) element moves with high probability. Simple experiments with our implementation of HI PMAs corroborate our theoretical analysis. Comparisons to regular PMAs give preliminary indications that the practical cost of adding history-independence is not too large.Our HI cache-oblivious B-tree bounds match those of prior non-HI cache-oblivious B-trees. Searches take O(logB N) I/Os; inserts and deletes take O((log2 N)/B+ logB N) amortized I/Os with high probability; and range queries returning k elements take O(logB N + k/B) I/Os.Our HI external-memory skip list achieves optimal bounds with high probability, analogous to in-memory skip lists: O(logB N) I/Os for point queries and amortized O(logB N) I/Os for inserts/deletes. Range queries returning k elements run in O(logB N + k/B) I/Os. In contrast, the best possible high-probability bounds for inserting into the folklore B-skip list, which promotes elements with probability 1/B, is just Theta(log N) I/Os. This is no better than the bounds one gets from running an in-memory skip list in external memory.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {289–302},
numpages = {14},
keywords = {sequential file maintenance, B-tree, packed-memory array, online list labelling, external memory, history-independence, data structures, cache-oblivious},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252640,
author = {Senellart, Pierre},
title = {Session Details: PODS Tutorial 2},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252640},
doi = {10.1145/3252640},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902307,
author = {Neven, Frank},
title = {Logical Aspects of Massively Parallel and Distributed Systems},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902307},
doi = {10.1145/2902251.2902307},
abstract = {Database research has witnessed a renewed interest for data processing in distributed and parallel settings. While distributed and parallel data management systems have been around for quite some time, it is the rise of cloud computing and the advent of Big Data that presents the community with new challenges. This paper highlights recent research concerning the logical foundations of massively parallel and distributed systems. The first part of the paper concerns massively parallel systems where computation proceeds in a number of synchronized rounds. Here, the focus is on evaluation algorithms for conjunctive queries as well as on reasoning about correctness and optimization of such algorithms. The second part of the paper addresses a distributed asynchronous setting where eventual consistency comes into play. Here, the focus is on coordination-free computation and its relationship to logical monotonicity and Datalog programs.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {303–314},
numpages = {12},
keywords = {massive parallel model, logic, datalog, conjunctive query},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252641,
author = {Kourtris, Paris},
title = {Session Details: Session 4: Query Evaluation},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252641},
doi = {10.1145/3252641},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902279,
author = {Chen, Hubie and Mengel, Stefan},
title = {Counting Answers to Existential Positive Queries: A Complexity Classification},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902279},
doi = {10.1145/2902251.2902279},
abstract = {Existential positive formulas form a fragment of first-order logic that includes and is semantically equivalent to unions of conjunctive queries, one of the most important and well-studied classes of queries in database theory. We consider the complexity of counting the number of answers to existential positive formulas on finite structures and give a trichotomy theorem on query classes, in the setting of bounded arity. This theorem generalizes and unifies several known results on the complexity of conjunctive queries and unions of conjunctive queries. We prove this trichotomy theorem by establishing a result which we call the equivalence theorem, which shows that for each class of existential positive formulas, there exists a class of conjunctive queries having the same complexity (in a sense made precise).},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {315–326},
numpages = {12},
keywords = {existential positive queries, query evaluation, counting complexity},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902289,
author = {Abo Khamis, Mahmoud and Ngo, Hung Q. and Suciu, Dan},
title = {Computing Join Queries with Functional Dependencies},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902289},
doi = {10.1145/2902251.2902289},
abstract = {Recently, Gottlob, Lee, Valiant, and Valiant (GLVV) presented an output size bound for join queries with functional dependencies (FD), based on a linear program on polymatroids. GLVV bound strictly generalizes the bound of Atserias, Grohe and Marx (AGM) for queries with no FD, in which case there are known algorithms running within the AGM-bound and thus are worst-case optimal. A main result of this paper is an algorithm for computing join queries with FDs, running within GLVV bound up to a poly-log factor. In particular, our algorithm is worst-case optimal for any query where the GLVV bound is tight. As an unexpected by-product, our algorithm manages to solve a harder problem, where (some) input relations may have prescribed maximum degree bounds, of which both functional dependencies and cardinality bounds are special cases.We extend Gottlob et al. framework by replacing all variable subsets with the lattice of closed sets (under the given FDs). This gives us new insights into the structure of the worst-case bound and worst-case instances. While it is still open whether GLVV bound is tight in general, we show that it is tight on distributive lattices and some other simple lattices. Distributive lattices capture a strict superset of queries with no FD and with simple FDs. We also present two simpler algorithms which are also worst-case optimal on distributive lattices within a single-log factor, but they do not match GLVV bound on a general lattice. Our algorithms are designed based on a novel principle: we turn a proof of a polymatroid-based output size bound into an algorithm.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {327–342},
numpages = {16},
keywords = {join algorithm, polymatroid, entropy, functional dependency, worst-case optimal},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902302,
author = {Barcelo, Pablo and Gottlob, Georg and Pieris, Andreas},
title = {Semantic Acyclicity Under Constraints},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902302},
doi = {10.1145/2902251.2902302},
abstract = {A conjunctive query (CQ) is semantically acyclic if it is equivalent to an acyclic one. Semantic acyclicity has been studied in the constraint-free case, and deciding whether a query enjoys this property is NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (tgds) that can express, e.g., inclusion dependencies, or equality-generating dependencies (egds) that capture, e.g., functional dependencies, a CQ may turn out to be semantically acyclic under the constraints while not semantically acyclic in general. This opens avenues to new query optimization techniques. In this paper we initiate and develop the theory of semantic acyclicity under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically acyclic under the constraints, or, in other words, is the query equivalent to an acyclic one over all those databases that satisfy the set of constraints?We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not sufficient condition for the decidability of semantic acyclicity. In particular, we show that semantic acyclicity is undecidable in the presence of full tgds (i.e., Datalog rules). In view of this fact, we focus on the main classes of tgds for which CQ containment is decidable, and do not capture the class of full tgds, namely guarded, non-recursive and sticky tgds. For these classes we show that semantic acyclicity is decidable, and its complexity coincides with the complexity of CQ containment. In the case of egds, we show that if we focus on keys over unary and binary predicates, then semantic acyclicity is decidable (NP-complete). We finally consider the problem of evaluating a semantically acyclic query over a database that satisfies a set of constraints. For guarded tgds and functional dependencies the evaluation problem is tractable.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {343–354},
numpages = {12},
keywords = {acyclicity, conjunctive queries, query evaluation, equality-generating dependencies, tuple-generating dependencies, query approximation},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902301,
author = {Amarilli, Antoine and Bourhis, Pierre and Senellart, Pierre},
title = {Tractable Lineages on Treelike Instances: Limits and Extensions},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902301},
doi = {10.1145/2902251.2902301},
abstract = {Query evaluation on probabilistic databases is generally intractable (#P-hard). Existing dichotomy results have identified which queries are tractable (or safe), and connected them to tractable lineages. In our previous work, using different tools, we showed that query evaluation is linear-time on probabilistic databases for arbitrary monadic second-order queries, if we bound the treewidth of the instance.In this paper, we study limitations and extensions of this result. First, for probabilistic query evaluation, we show that MSO tractability cannot extend beyond bounded treewidth: there are even FO queries that are hard on any efficiently constructible unbounded-treewidth class of graphs. This dichotomy relies on recent polynomial bounds on the extraction of planar graphs as minors, and implies lower bounds in non-probabilistic settings, for query evaluation and match counting in subinstance-closed families. Second, we show how to explain our tractability result in terms of lineage: the lineage of MSO queries on bounded-treewidth instances can be represented as bounded-treewidth circuits, polynomial-size OBDDs, and linear-size d-DNNFs. By contrast, we can strengthen the previous dichotomy to lineages, and show that there are even UCQs with disequalities that have superpolynomial OBDDs on all unbounded-treewidth graph classes; we give a characterization of such queries. Last, we show how bounded-treewidth tractability explains the tractability of the inversion-free safe queries: we can rewrite their input instances to have bounded-treewidth.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {355–370},
numpages = {16},
keywords = {treewidth, lineages, dichotomy, minors, MSO, probabilities, database},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252642,
author = {Comcorde, Graham},
title = {Session Details: Session 5: Data Streams and Privacy},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252642},
doi = {10.1145/3252642},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902287,
author = {Har-Peled, Sariel and Indyk, Piotr and Mahabadi, Sepideh and Vakilian, Ali},
title = {Towards Tight Bounds for the Streaming Set Cover Problem},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902287},
doi = {10.1145/2902251.2902287},
abstract = {We consider the classic Set Cover problem in the data stream model. For n elements and m sets (m ≥ n) we give a O(1/δ)-pass algorithm with a strongly sub-linear ~O(mnδ) space and logarithmic approximation factor. This yields a significant improvement over the earlier algorithm of Demaine et al. [10] that uses exponentially larger number of passes. We complement this result by showing that the tradeoff between the number of passes and space exhibited by our algorithm is tight, at least when the approximation factor is equal to 1. Specifically, we show that any algorithm that computes set cover exactly using ({1 over 2δ}-1) passes must use ~Ω(mnδ) space in the regime of m=O(n). Furthermore, we consider the problem in the geometric setting where the elements are points in R2 and sets are either discs, axis-parallel rectangles, or fat triangles in the plane, and show that our algorithm (with a slight modification) uses the optimal ~O(n) space to find a logarithmic approximation in O(1/δ) passes.Finally, we show that any randomized one-pass algorithm that distinguishes between covers of size 2 and 3 must use a linear (i.e., Ω(mn)) amount of space. This is the first result showing that a randomized, approximate algorithm cannot achieve a space bound that is sublinear in the input size.This indicates that using multiple passes might be necessary in order to achieve sub-linear space bounds for this problem while guaranteeing small approximation factors.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {371–383},
numpages = {13},
keywords = {lower bound, multiple pass, geometric set cover, sampling, set cover, streaming algorithms},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902284,
author = {Bhattacharyya, Arnab and Dey, Palash and Woodruff, David P.},
title = {An Optimal Algorithm for L1-Heavy Hitters in Insertion Streams and Related Problems},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902284},
doi = {10.1145/2902251.2902284},
abstract = {We give the first optimal bounds for returning the l1-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in {1, 2, ..., n} and parameters 0 < ε < φ ≤ 1, let fi denote the frequency of item i, i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which fi ≥ φ m, returns no items j for which fj ≤ (φ -ε)m, and returns approximations ~fi with |~fi - fi| ≤ ε m for each item i that it returns. Our algorithm uses O(ε-1 logφ-1 + φ-1 log n + log log m) bits of space, processes each stream update in O(1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive ε m error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of l1-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {385–400},
numpages = {16},
keywords = {data streams, heavy hitters, algorithms, frequent items},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902283,
author = {McGregor, Andrew and Vorotnikova, Sofya and Vu, Hoa T.},
title = {Better Algorithms for Counting Triangles in Data Streams},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902283},
doi = {10.1145/2902251.2902283},
abstract = {We present space-efficient data stream algorithms for approximating the number of triangles in a graph up to a factor 1+ε. While it can be shown that determining whether a graph is triangle-free is not possible in sub-linear space, a large body of work has focused on minimizing the space required in terms of the number of triangles T (or a lower bound on this quantity) and other parameters including the number of nodes n and the number of edges m. Two models are important in the literature: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order and the adjacency list order model in which all edges incident to the same node appear consecutively. We improve over the state of the art results in both models. For the adjacency list order model, we show that ~O(ε-2m/√T) space is sufficient in one pass and ~O(ε-2m3/2/T) space is sufficient in two passes where the ~O(·) notation suppresses log factors. For the arbitrary order model, we show that ~O(ε-2m/√T) space suffices given two passes and that ~O(ε-2m3/2/T) space suffices given three passes and oracle access to the degrees. Finally, we show how to efficiently implement the "wedge sampling" approach to triangle estimation in the arbitrary order model. To do this, we develop the first algorithm for lp sampling such that multiple independent samples can be generated with O(polylog n) update time; this primitive is widely applicable and this result may be of independent interest.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {401–411},
numpages = {11},
keywords = {data streams, triangles, clustering coefficients},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902296,
author = {Nissim, Kobbi and Stemmer, Uri and Vadhan, Salil},
title = {Locating a Small Cluster Privately},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902296},
doi = {10.1145/2902251.2902296},
abstract = {We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private data exploration, clustering, and removal of outliers. Furthermore, we use it to significantly relax the requirements of the sample and aggregate technique [Nissim, Raskhodnikova, and Smith, 2007], which allows compiling of "off the shelf" (non-private) analyses into analyses that preserve differential privacy.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {413–427},
numpages = {15},
keywords = {sample and aggregate, clustering, differential privacy},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/3252643,
author = {Yi, Ke},
title = {Session Details: Session 6: Algorithms and Data Structures},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3252643},
doi = {10.1145/3252643},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
numpages = {1},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902303,
author = {Agarwal, Pankaj K. and Fox, Kyle and Munagala, Kamesh and Nath, Abhinandan},
title = {Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902303},
doi = {10.1145/2902251.2902303},
abstract = {With the massive amounts of data available today, it is common to store and process data using multiple machines. Parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first provably efficient algorithms to compute, store, and query data structures for range queries and approximate nearest neighbor queries in a popular parallel computing abstraction that captures the salient features of MapReduce and other massively parallel communication (MPC) models. In particular, we describe algorithms for $kd$-trees, range trees, and BBD-trees that only require O(1) rounds of communication for both preprocessing and querying while staying competitive in terms of running time and workload to their classical counterparts. Our algorithms are randomized, but they can be made deterministic at some increase in their running time and workload while keeping the number of rounds of communication to be constant.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {429–440},
numpages = {12},
keywords = {computational geometry, data structures, range search, mapreduce, sampling, nearest-neighbor search},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902278,
author = {Liberty, Edo and Mitzenmacher, Michael and Thaler, Justin and Ullman, Jonathan},
title = {Space Lower Bounds for Itemset Frequency Sketches},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902278},
doi = {10.1145/2902251.2902278},
abstract = {Given a database, computing the fraction of rows that contain a query itemset or determining whether this fraction is above some threshold are fundamental operations in data mining. A uniform sample of rows is a good sketch of the database in the sense that all sufficiently frequent itemsets and their approximate frequencies are recoverable from the sample, and the sketch size is independent of the number of rows in the original database. For many seemingly similar problems there are better sketching algorithms than uniform sampling. In this paper we show that for itemset frequency sketching this is not the case. That is, we prove that there exist classes of databases for which uniform sampling is a space optimal sketch for approximate itemset frequency analysis, up to constant or iterated-logarithmic factors.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {441–454},
numpages = {14},
keywords = {lower bounds, sketching, conjunction queries, itemset mining, marginal queries},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902274,
author = {Canonne, Cl\'{e}ment L.},
title = {Are Few Bins Enough: Testing Histogram Distributions},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902274},
doi = {10.1145/2902251.2902274},
abstract = {A probability distribution over an ordered universe [n]={1,...,n} is said to be a k-histogram if it can be represented as a piecewise-constant function over at most k contiguous intervals. We study the following question: given samples from an arbitrary distribution D over [n], one must decide whether D is a k-histogram, or is far in L_1 distance from any such succinct representation. We obtain a sample and time-efficient algorithm for this problem, complemented by a nearly-matching information-theoretic lower bound on the number of samples required for this task. Our results significantly improve on the previous state-of-the-art, due to Indyk, Levi, and Rubinfeld 2012) and Canonne, Diakonikolas, Gouleakis, and Rubinfeld (2016).},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {455–463},
numpages = {9},
keywords = {property testing, probability distributions, sublinear algorithms, distribution testing, histograms},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902281,
author = {Agarwal, Pankaj K. and Kumar, Nirman and Sintos, Stavros and Suri, Subhash},
title = {Range-Max Queries on Uncertain Data},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902281},
doi = {10.1145/2902251.2902281},
abstract = {Let P be a set of n uncertain points in Red, where each point pi ∈ P is associated with a real value vi and a probability αi ∈ (0,1] of existence, i.e., each pi exists with an independent probability αi. We present algorithms for building an index on P so that for a d-dimensional query rectangle ρ, the expected maximum value or the most-likely maximum value in ρ can be computed quickly. The specific contributions of our paper include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension d ≥ 1. It also provides a trade-off between query time and size of the index. (ii) A conditional lower bound for the most-likely range-max queries, based on the conjectured hardness of the set-intersection problem, which suggests that in the worst case the product (query time)2 x (index size) is Ω((n2)/polylog(n)). (iii) A linear-size index for estimating the expected range-max value within approximation factor 1/2 in O(logc n) time, for some constant c > 0; that is, if the expected maximum value is μ then the query procedure returns a value μ' with μ/2 ≤ μ' ≤ μ. (iv) Extensions of our algorithm to more general uncertainty models and for computing the top-k values of the range-max.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {465–476},
numpages = {12},
keywords = {skylines, data structures, data uncertainty, lower bounds, orthogonal query ranges, range-max queries, algorithms},
location = {San Francisco, California, USA},
series = {PODS '16}
}

@inproceedings{10.1145/2902251.2902304,
author = {Backurs, Arturs and Onak, Krzysztof},
title = {Fast Algorithms for Parsing Sequences of Parentheses with Few Errors},
year = {2016},
isbn = {9781450341912},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2902251.2902304},
doi = {10.1145/2902251.2902304},
abstract = {We consider the problem of fixing sequences of unbalanced parentheses. A classic algorithm based on dynamic programming computes the optimum sequence of edits required to solve the problem in cubic time. We show the first algorithm that runs in linear time when the number of necessary edits is small. More precisely, our algorithm runs in O(n) + dO(1) time, where n is the length of the sequence to be fixed and d is the minimum number of edits. The problem of fixing parentheses sequences is related to the task of repairing semi-structured documents such as XML and JSON.},
booktitle = {Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {477–488},
numpages = {12},
keywords = {dyck language, edit distance, parsing},
location = {San Francisco, California, USA},
series = {PODS '16}
}

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr


text:
@article{campbell2021gender,
  title={The gender gap in adolescent mental health: a cross-national investigation of 566,829 adolescents across 73 countries},
  author={Campbell, Olympia LK and Bann, David and Patalay, Praveetha},
  journal={SSM-population health},
  volume={13},
  pages={100742},
  year={2021},
  publisher={Elsevier}
}

license: MIT

license_type: permissive

branch_name: refs/heads/master

extension: bibtex


text:
@article{Villamor2012,
 abstract = {Rupture of the Greendale Fault during the 4 September 2010, M w7.1 Darfield (Canterbury) earthquake produced a zone of ground-surface rupture that severely damaged several houses, buildings and lifelines. Immediately after the earthquake, surface rupture features were mapped in the field and from digital terrain models developed from airborne Light Detection and Ranging (lidar) data. To enable rebuild decisions to be made and for future land use planning, a fault avoidance zone was defined for the Greendale Fault following the Ministry for the Environment guidelines on 'Planning for the Development of Land on or Close to Active Faults'. We present here the most detailed map to date of the fault trace and describe how this was used to define and characterise the fault avoidance zone for land use planning purposes. © 2012 The Royal Society of New Zealand.},
 author = {Villamor, P. and Litchfield, N. and Barrell, D. and Van Dissen, R. and Hornblow, S. and Quigley, M. and Levick, S. and Ries, W. and Duffy, B. and Begg, J. and Townsend, D. and Stahl, T. and Bilderback, E. and Noble, D. and Furlong, K. and Grant, H.},
 doi = {10.1080/00288306.2012.680473},
 issn = {00288306},
 journal = {New Zealand Journal of Geology and Geophysics},
 keywords = {Active Fault,Canterbury earthquake sequence,Darfield earthquake,Fault avoidance zone,Land use planning,Strike-slip fault,Surface fault rupture map},
 number = {3},
 pages = {223--230},
 title = {Map of the 2010 Greendale Fault surface rupture, Canterbury, New Zealand: Application to land use planning},
 volume = {55},
 year = {2012}
}

repository: geospatialeco/SpatialDataScience

repo_name: geospatialeco/SpatialDataScience

extension: bib


text:
require xorg-proto-common.inc

SUMMARY = "XI: X Input extension headers"

DESCRIPTION = "This package provides the wire protocol for the X Input \
extension.  The extension supports input devices other then the core X \
keyboard and pointer."

LICENSE = "MIT & MIT-style"
LIC_FILES_CHKSUM = "file://COPYING;md5=e562cc0f6587b961f032211d8160f31e \
                    file://XI2proto.h;endline=48;md5=1ac1581e61188da2885cc14ff49b20be"

PE = "1"

inherit gettext

BBCLASSEXTEND = "native nativesdk"

SRC_URI[md5sum] = "94db391e60044e140c9854203d080654"
SRC_URI[sha256sum] = "7d26b193f6699f8e9c1e28bf026844b7ecea33dd644402523471be109152c32f"

#
# debian
#
inherit debian-package
DEBIAN_SECTION = "x11"
DPR = "0"
DPN = "x11proto-input"

# There is no debian patch
DEBIAN_PATCH_TYPE = "nopatch"

repository: takuya-t/meta-debian

repo_name: takuya-t/meta-debian

branch_name: refs/heads/daisy

extension: bb


text:
SUMMARY = "Gnuplot is a portable command-line driven graphing utility"
DESCRIPTION = "Gnuplot is a portable command-line driven interactive datafile \
(text or binary) and function plotting utility."
HOMEPAGE = "http://www.gnuplot.info/"
SECTION = "console/scientific"
LICENSE = "gnuplot"
LIC_FILES_CHKSUM = "file://Copyright;md5=243a186fc2fd3b992125d60d5b1bab8f"
DEPENDS = "${BPN}-native virtual/libx11 gd readline"

inherit autotools features_check pkgconfig
# depends on virtual/libx11
REQUIRED_DISTRO_FEATURES = "x11"

SRC_URI = "${SOURCEFORGE_MIRROR}/project/${BPN}/${BPN}/${PV}/${BP}.tar.gz;name=archive \
           http://www.mneuroth.de/privat/zaurus/qtplot-0.2.tar.gz;name=qtplot \
           file://gnuplot.desktop \
           file://gnuplot.png \
           "
SRC_URI:append:class-target = " \
    file://0002-do-not-build-demos.patch \
    file://0003-Use-native-tools-to-build-docs.patch \
    file://0004-Add-configure-option-to-find-qt5-native-tools.patch \
"

SRC_URI[archive.sha256sum] = "51f89bbab90f96d3543f95235368d188eb1e26eda296912256abcd3535bd4d84"
SRC_URI[qtplot.sha256sum] = "6df317183ff62cc82f3dcf88207a267cd6478cb5147f55d7530c94f1ad5f4132"

# for building docs (they deserve it) we need *doc2* tools native
BBCLASSEXTEND = "native"
DEPENDS:class-native = "readline-native"
PACKAGECONFIG:class-native = ""

SRC_URI:append:class-native = " file://0001-reduce-build-to-conversion-tools-for-native-build.patch"

do_install:class-native() {
    install -d ${D}${bindir}
	install ${B}/docs/*doc* ${D}${bindir}
    rm ${D}${bindir}/*.o
}

PACKAGECONFIG ??= "cairo"
PACKAGECONFIG[cairo] = "--with-cairo,--without-cairo,cairo pango"
PACKAGECONFIG[lua] = "--with-lua,--without-lua,lua"
PACKAGECONFIG[qt5] = "--with-qt --with-qt5nativesysroot=${STAGING_DIR_NATIVE},--without-qt,qtbase-native qtbase qtsvg qttools-native"

EXTRA_OECONF = " \
    --with-readline=${STAGING_LIBDIR}/.. \
    --disable-wxwidgets \
    --without-libcerf \
"

do_compile:prepend() {
    install -m 0644 ${WORKDIR}/qtplot-0.2/qtopia.trm ${S}/term/
}

do_install:append:class-target() {
    install -d ${D}${datadir}/applications/
    install -m 0644 ${WORKDIR}/gnuplot.desktop ${D}${datadir}/applications/
    install -d ${D}${datadir}/pixmaps/
    install -m 0644 ${WORKDIR}/gnuplot.png ${D}${datadir}/pixmaps/
}

PACKAGES =+ "${PN}-x11"

RPROVIDES:${PN}-dbg += "${PN}-x11-dbg"

DESCRIPTION:${PN}-x11 = "X11 display terminal for Gnuplot."
SECTION:${PN}-x11 = "x11/scientific"
FILES:${PN}-x11 = "${libexecdir} ${datadir}/applications ${datadir}/pixmaps ${libdir}/X11 "

FILES:${PN} += "${datadir}/texmf"

repository: openembedded/meta-openembedded

repo_name: openembedded/meta-openembedded

gha_license_id: MIT

gha_language: BitBake


text:
require bug-app.inc

DESCRIPTION = "This is an enhanced version of the all popular BUGer  Security System.\
The Basics:\
The App uses a motion sensor and a camera.\
anytime a motion is detected, the camera takes a picture and stores it on the bug.\
By pointing a web browser to http://10.10.10.10/buger\
you will be able to see a log of all the pictures taken along with their time stamp.\
The images are displayed at a reduced size and by clicking on them you will see \
the clicked image at full size.\
The Changes:\
So far I have added an audio module to the App, to work as follow.\
when a motion is detected , picture taken and successfully saved a beep will be played.\
Eventually the storage unit will run out of room to store new pictures.\
In case this happens the Bug will play a warning sound 'Warning System Failure'\
every time the picture will be unsaved.\
(Please read the READ ME since I have disabled the audio for testing purposes)\
I also Added a new logo, a status view of the number of motions detected \
as well as making the web interface auto refresh itself every (60 seconds).\
"
HOMEPAGE = "http://buglabs.net/applications/DemoX1"

DEPENDS += "com.buglabs.bug.base com.buglabs.bug.menu com.buglabs.bug.module.audio com.buglabs.bug.audio.common com.buglabs.bug.module.camera com.buglabs.bug.module.motion com.buglabs.common com.buglabs.osgi com.buglabs.osgi.http com.sun.javax.servlet service-tracker "

PV = "10"

SRC_LINK = "http://buglabs.net/program_version/download/670"

APIVERSION = ""

repository: overo/overo-oe-natty

repo_name: overo/overo-oe-natty

branch_name: HEAD


text:
package main

import (
	"fmt"
	"strings"
	"testing"
	"time"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

type testcase struct {
	name     string
	args     string
	cfg      *config
	expected string
}

func TestTimez(t *testing.T) {

	// 1522741510

	t0, err := time.Parse("2006-01-02 15:04:05-0700", "2017-10-10 23:01:30+1300")
	require.Nil(t, err)
	z0, err := time.LoadLocation("Pacific/Auckland")
	require.Nil(t, err)
	z1, err := time.LoadLocation("Asia/Dubai")
	require.Nil(t, err)

	z := &mockZone{}
	z.On("Zone").Return(z0)

	c := &mockClock{}
	c.On("Now").Return(t0)

	tcs := []testcase{
		testcase{
			name:     "junk input",
			args:     "asdf",
			expected: usage,
		},
		testcase{
			name:     "empty input outputs local and utc",
			args:     "",
			expected: `UTC: 2017-10-10 10:01:30`,
		},
		// Old behavior: Specifying an input timezone and no output timezone, outputs local
		// testcase{
		// 	name:     "no output zone assumes local",
		// 	args:     "2017-10-10 10:59:00 UTC",
		// 	expected: `Pacific/Auckland: 2017-10-10 23:59:00`,
		// },
		testcase{
			name:     "no output zone assumes local",
			args:     "2017-10-10 10:59:00 UTC",
			expected: `UTC: 2017-10-10 10:59:00`,
		},
		testcase{
			name:     "one tz outputs now in that tz",
			args:     "US/Pacific",
			expected: `US/Pacific: 2017-10-10 03:01:30`,
		},
		testcase{
			name: "three tz outputs now in those tz",
			args: "US/Pacific Pacific/Auckland UTC",
			expected: `US/Pacific: 2017-10-10 03:01:30
Pacific/Auckland: 2017-10-10 23:01:30
UTC: 2017-10-10 10:01:30`},
		testcase{
			name:     "one tz and a timestamp without zone, outputs that local time converted to that zone",
			args:     "US/Pacific 2017-10-10 23:45:00",
			expected: `US/Pacific: 2017-10-10 03:45:00`,
		},
		testcase{
			name: "multiple tz and a timestamp without zone, outputs local time converted to those zones",
			args: "US/Pacific US/Eastern 2017-10-10 23:45:00",
			expected: `US/Pacific: 2017-10-10 03:45:00
US/Eastern: 2017-10-10 06:45:00`},
		testcase{
			name:     "one tz and a timestamp and zone, converts second zone to first",
			args:     "US/Pacific 2017-10-10 23:45:00 UTC",
			expected: `US/Pacific: 2017-10-10 16:45:00`,
		},
		testcase{
			name:     "`at in from to` are discarded",
			args:     "in to US/Pacific at 2017-10-10 23:45:00 from UTC",
			expected: `US/Pacific: 2017-10-10 16:45:00`,
		},
		// 		testcase{
		// 			name: "respects configured `default` alias",
		// 			args: "",
		// 			cfg:  &config{localTZ: z1},
		// 			expected: `Asia/Dubai: 2017-10-10 14:01:30
		// UTC: 2017-10-10 10:01:30`,
		// 		},
		testcase{
			name:     "respects configured `custom` alias",
			args:     "custom",
			cfg:      &config{localTZ: z1, aliases: map[string]string{"custom": "Europe/London"}},
			expected: `custom: 2017-10-10 11:01:30`,
		},
		testcase{
			cfg: &config{
				localTZ: z1,
			},
			name:     "transforms Unix to default",
			args:     "1522741510",
			expected: `UTC: 2018-04-03 07:45:10`,
		},
		testcase{
			name:     "transforms Unix to UTC",
			args:     "UTC 1522741510",
			expected: `UTC: 2018-04-03 07:45:10`,
		},
		testcase{
			name:     "one tz outputs now in that tz",
			args:     "US/Pacific",
			expected: `US/Pacific: 2017-10-10 03:01:30`,
		},
	}
	for _, tc := range tcs {
		t.Run(tc.name, func(t *testing.T) {
			args := strings.Split(tc.args, " ")
			if len(args) == 1 && args[0] == "" {
				args = nil
			}
			if tc.cfg == nil {
				tc.cfg = &config{
					localTZ: z0,
					aliases: defaultAlias,
				}
			}
			out := timez(*tc.cfg, c, args)
			assert.Equal(t, tc.expected, out, fmt.Sprintf("input: %s", tc.args))
		})
	}
}

repository: therealplato/timez

repo_name: therealplato/timez

extension: go


text:
DEPENDS = "qtbase-native"

LICENSE = "GFDL-1.3 & BSD & (LGPL-2.1 & Digia-Qt-LGPL-Exception-1.1 | LGPL-3.0)"
LIC_FILES_CHKSUM = " \
    file://LICENSE.LGPLv21;md5=58a180e1cf84c756c29f782b3a485c29 \
    file://LICENSE.LGPLv3;md5=c4fe8c6de4eef597feec6e90ed62e962 \
    file://LGPL_EXCEPTION.txt;md5=9625233da42f9e0ce9d63651a9d97654 \
    file://LICENSE.FDL;md5=6d9f2a9af4c8b8c3c769f6cc1b6aaf7e \
"

QT_MODULE = "qttools"

require qt5-native.inc
require qt5-git.inc

do_configure() {
    ${OE_QMAKE_QMAKE} ${OE_QMAKE_DEBUG_OUTPUT} -r ${S} CONFIG+=linguistonly
}

do_install() {
    oe_runmake install INSTALL_ROOT=${D}
}

SRCREV = "33c65366a7c3901d2aecfde3dbc485e1eac5c10c"


text:
@proceedings{ws-2017-language-technology,
    title = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    editor = "Dinu, Anca  and
      Osenova, Petya  and
      Vertan, Cristina",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    doi = "0.26615/978-954-452-046-5_",
}
@inproceedings{malahov-etal-2017-diachronic,
    title = "A Diachronic Corpus for {R}omanian ({R}o{D}ia)",
    author = "Malahov, Ludmila  and
      M{\u{a}}r{\u{a}}nduc, C{\u{a}}t{\u{a}}lina  and
      Colesnicov, Alexandru",
    booktitle = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    url = "https://www.aclweb.org/anthology/W17-8101",
    doi = "0.26615/978-954-452-046-5_001",
    pages = "1--9",
}
@inproceedings{bobicev-etal-2017-tools,
    title = "Tools for Building a Corpus to Study the Historical and Geographical Variation of the {R}omanian Language",
    author = "Bobicev, Victoria  and
      M{\u{a}}r{\u{a}}nduc, C{\u{a}}t{\u{a}}lina  and
      Perez, Cenel Augusto",
    booktitle = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    url = "https://www.aclweb.org/anthology/W17-8102",
    doi = "0.26615/978-954-452-046-5_002",
    pages = "10--19",
}
@inproceedings{declerck-etal-2017-multilingual,
    title = "Multilingual Ontologies for the Representation and Processing of Folktales",
    author = {Declerck, Thierry  and
      Aman, Anastasija  and
      Banzer, Martin  and
      Mach{\'a}{\v{c}}ek, Dominik  and
      Sch{\"a}fer, Lisa  and
      Skachkova, Natalia},
    booktitle = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    url = "https://www.aclweb.org/anthology/W17-8103",
    doi = "0.26615/978-954-452-046-5_003",
    pages = "20--23",
}
@inproceedings{dinu-etal-2017-annotation,
    title = "On the annotation of vague expressions: a case study on {R}omanian historical texts",
    author = "Dinu, Anca  and
      von Hahn, Walther  and
      Vertan, Cristina",
    booktitle = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    url = "https://www.aclweb.org/anthology/W17-8104",
    doi = "0.26615/978-954-452-046-5_004",
    pages = "24--31",
}
@inproceedings{stambolieva-etal-2017-language,
    title = "Language Technologies in Teaching Bugarian at Primary and Secondary School Level: the {NBU} Platform of Language Teaching ({PLT})",
    author = "Stambolieva, Maria  and
      Ivanova, Valentina  and
      Raykova, Mariana  and
      Hadjikoteva, Milka  and
      Neykova, Mariya",
    booktitle = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    url = "https://www.aclweb.org/anthology/W17-8105",
    doi = "0.26615/978-954-452-046-5_005",
    pages = "32--38",
}
@inproceedings{moise-2017-natural,
    title = "Natural Language Processing in Political Campaigns",
    author = "Moise, Cristina",
    booktitle = "Proceedings of the First Workshop on Language technology for Digital Humanities in Central and (South-)Eastern {E}urope",
    month = sep,
    year = "2017",
    address = "Varna",
    publisher = "INCOMA Inc.",
    url = "https://www.aclweb.org/anthology/W17-8106",
    doi = "0.26615/978-954-452-046-5_006",
    pages = "39--43",
}

repository: emorynlp/nlprankings

repo_name: emorynlp/nlprankings

gha_license_id: NOASSERTION

gha_language: TeX


text:
package main

import (
	dstags "github.com/go-generalize/datastore-repo/tools/datastore_tag_linter"
	"golang.org/x/tools/go/analysis/multichecker"
)

func main() {
	multichecker.Main(
		dstags.Analyzer,
	)
}

repository: go-generalize/datastore-repo

repo_name: go-generalize/datastore-repo

gha_language: Go


text:
%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/

%% Created for Alex Ames at 2017-12-21 18:38:32 -0600

%% Saved with string encoding Unicode (UTF-8)

@electronic{gpu-julia-nvidia,
	Abstract = {asdf},
	Author = {Tim Besard},
	Date-Added = {2017-12-22 00:36:33 +0000},
	Date-Modified = {2017-12-22 00:38:32 +0000},
	Month = {October},
	Title = {High-Performance GPU Computing in the Julia Programming Language},
	Url = {https://devblogs.nvidia.com/parallelforall/gpu-computing-julia-programming-language/},
	Year = {2017}}

@article{champagnat2011fast,
	Author = {Champagnat, Fr{\'e}d{\'e}ric and Plyer, Aur{\'e}lien and Le Besnerais, Guy and Leclaire, Benjamin and Davoust, Samuel and Le Sant, Yves},
	Date-Added = {2017-12-21 23:07:05 +0000},
	Date-Modified = {2017-12-21 23:07:05 +0000},
	Journal = {Experiments in fluids},
	Number = {4},
	Pages = {1169},
	Publisher = {Springer},
	Title = {Fast and accurate PIV computation using highly parallel iterative correlation maximization},
	Volume = {50},
	Year = {2011}}

@article{stanislas2003main,
	Author = {Stanislas, Michel and Okamoto, Koji and K{\"a}hler, Christian},
	Date-Added = {2017-12-21 05:49:16 +0000},
	Date-Modified = {2017-12-21 05:49:16 +0000},
	Journal = {Measurement Science and Technology},
	Number = {10},
	Pages = {R63},
	Publisher = {IOP Publishing},
	Title = {Main results of the first international PIV challenge},
	Volume = {14},
	Year = {2003}}

@inproceedings{pust2000piv,
	Author = {Pust, Oliver},
	Booktitle = {Proceedings of the 10th International Symposium on Applications of Laser Techniques to Fluid Mechanics, Lisbon, Portugal},
	Date-Added = {2017-12-21 05:43:20 +0000},
	Date-Modified = {2017-12-21 05:43:20 +0000},
	Pages = {114},
	Title = {Piv: Direct cross-correlation compared with fft-based cross-correlation},
	Volume = {27},
	Year = {2000}}


text:
package gluasocket_mimecore

import (
	"bytes"

	"github.com/yuin/gopher-lua"
)

/*-------------------------------------------------------------------------*\
* Incrementally decodes a string in quoted-printable
* A, B = qp(C, D)
* A is the decoded version of the largest prefix of C .. D that
* can be decoded without doubts.
* B has the remaining bytes of C .. D, *without* decoding.
\*-------------------------------------------------------------------------*/
func unqpFn(l *lua.LState) int {
	var atom bytes.Buffer

	if l.Get(1).Type() == lua.LTNil {
		l.Push(lua.LNil)
		l.Push(lua.LNil)
		return 2
	}

	input := l.ToString(1)
	var buffer bytes.Buffer

	/* process first part of input */
	for _, c := range input {
		qpdecode(c, &atom, &buffer)
	}

	/* if second part is nil, we are done */
	if l.Get(2).Type() == lua.LTNil {
		if buffer.Len() == 0 {
			l.Push(lua.LNil)
		} else {
			l.Push(lua.LString(buffer.String()))
		}
		l.Push(lua.LNil)
		return 2
	}

	/* otherwise process rest of input */
	input = l.ToString(2)
	for _, c := range input {
		qpdecode(c, &atom, &buffer)
	}

	l.Push(lua.LString(buffer.String()))
	l.Push(lua.LString(atom.String()))
	return 2
}

/*-------------------------------------------------------------------------*\
* Accumulate characters until we are sure about how to deal with them.
* Once we are sure, output the to the buffer, in the correct form.
\*-------------------------------------------------------------------------*/
func qpdecode(c rune, input *bytes.Buffer, buffer *bytes.Buffer) {
	input.WriteRune(c)

	/* deal with all characters we can deal */
	inputBytes := input.Bytes()
	switch inputBytes[0] {
	/* if we have an escape character */
	case '=':
		if len(inputBytes) < 3 {
			return
		}
		/* eliminate soft line break */
		if inputBytes[1] == '\r' && inputBytes[2] == '\n' {
			return
		}
		/* decode quoted representation */
		c_ := qpunbase[inputBytes[1]]
		d := qpunbase[inputBytes[2]]

		/* if it is an invalid, do not decode */
		if c_ > 15 || d > 15 {
			buffer.WriteByte(inputBytes[0])
			buffer.WriteByte(inputBytes[1])
			buffer.WriteByte(inputBytes[2])
			input.Next(3)
		} else {
			buffer.WriteByte((c_ << 4) + d)
			input.Next(3)
			return
		}
	case '\r':
		if len(inputBytes) < 2 {
			return
		}
		if inputBytes[1] == '\n' {
			buffer.WriteByte(inputBytes[0])
			buffer.WriteByte(inputBytes[1])
			input.Next(2)
		}
		return
	default:
		if inputBytes[0] == '\t' || (inputBytes[0] > 31 && inputBytes[0] < 127) {
			buffer.WriteByte(inputBytes[0])
			input.Next(1)
		}
	}
}

repository: teejaded/gluasocket

repo_name: teejaded/gluasocket


text:
DESCRIPTION = "Wrapper for launching GENIVI AudioManager Monitor from neptune-ui"
LICENSE = "LGPLv3"

SRC_URI = " \
    file://start.sh \
    file://info.yaml \
    file://icon.png \
"

do_install() {
    install -Dm0755 ${WORKDIR}/start.sh ${D}/opt/neptune/apps/org.genivi.audiomanagermonitor/start.sh
    install -Dm0644 ${WORKDIR}/info.yaml ${D}/opt/neptune/apps/org.genivi.audiomanagermonitor/info.yaml
    install -Dm0644 ${WORKDIR}/icon.png ${D}/opt/neptune/apps/org.genivi.audiomanagermonitor/icon.png
}

FILES_${PN} += "/opt/neptune/"

repository: Pelagicore/meta-genivi-dev-qtas

repo_name: Pelagicore/meta-genivi-dev-qtas


text:
require recipes-support/sqlite/sqlite3_3.8.3.1.bb

inherit debian-package
DEBIAN_SECTION = "devel"
DPR = "0"

LICENSE = "PD"
LIC_FILES_CHKSUM = " \
  file://src/sqlite.h.in;endline=11;md5=65f0a57ca6928710b418c094b3570bb0 \
"

DEPENDS += "tcl-native"
do_compile[depends] += "tcl-native:do_populate_sysroot"

# Required to avoid a compile error
SRC_URI += "file://fix-hardcode-libtool.patch"

do_compile_prepend_class-target () {
	export CROSS_BUILDING="yes"
}

do_install_prepend_class-target () {
	export CROSS_BUILDING="yes"
}

# Fix error: ./lemon: Command not found
# lemon need be built with $(BCC) instead of $(LTLINK)
do_compile_prepend_class-nativesdk(){
	export CROSS_BUILDING="yes"
}

do_install_prepend_class-nativesdk(){
	export CROSS_BUILDING="yes"
}

#
# Debian Native Test
#
inherit debian-test

SRC_URI_DEBIAN_TEST = "\
        file://sqlite3-native-test/run_native_test_sqlite3 \
        file://sqlite3-native-test/run_create_table \
        file://sqlite3-native-test/run_insert_record \
        file://sqlite3-native-test/run_view_record \
        file://sqlite3-native-test/run_alter_tablename \
        file://sqlite3-native-test/run_version_command \
        file://sqlite3-native-test/run_drop_table \
        file://sqlite3-native-test/insert-data.sql \
"

DEBIAN_NATIVE_TESTS = "run_native_test_sqlite3"
TEST_DIR = "${B}/native-test"


text:
CAMNAME = "opencam"
DESCRIPTION = "${CAMNAME} ${OPENCAM_VERSION} softcam"
PN = "enigma2-plugin-softcams-opencam"
OPENCAM_VERSION = "2.0.13"
PV = "v${OPENCAM_VERSION}"
PR = "r1"

SRC_URI = "http://downloads.pli-images.org/softcams/opencam_7025_${OPENCAM_VERSION}.tar.gz"

S = "${WORKDIR}/"

require softcam.inc

INHIBIT_PACKAGE_STRIP = "1"
CONFFILES = "/etc/opencam.conf"

do_install() {
	install -d ${D}/usr/bin
	install -m 0755 ${S}/opencam_7025 ${D}/usr/bin/${CAMNAME}
	install -d ${D}/etc
	install -m 0644 ${S}/opencam.conf ${D}/etc/opencam.conf
}

repository: libo/openembedded

repo_name: libo/openembedded