Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 55 Issue 2, May 2008

Security analysis of cryptographically controlled access to XML documents
Martín Abadi, Bogdan Warinschi
Article No.: 6
DOI: 10.1145/1346330.1346331

Some promising recent schemes for XML access control employ encryption for implementing security policies on published data, avoiding data duplication. In this article, we study one such scheme, due to Miklau and Suciu [2003]. That...

XML data exchange: Consistency and query answering
Marcelo Arenas, Leonid Libkin
Article No.: 7
DOI: 10.1145/1346330.1346332

Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target. Theoretical foundations of data exchange have recently been...

XPath satisfiability in the presence of DTDs
Michael Benedikt, Wenfei Fan, Floris Geerts
Article No.: 8
DOI: 10.1145/1346330.1346333

We study the satisfiability problem associated with XPath in the presence of DTDs. This is the problem of determining, given a query p in an XPath fragment and a DTD D, whether or not there exists an XML document T such that...

Efficient core computation in data exchange
Georg Gottlob, Alan Nash
Article No.: 9
DOI: 10.1145/1346330.1346334

Data exchange deals with inserting data from one database into another database having a different schema. Fagin et al. [2005] have shown that among the universal solutions of a solvable data exchange problem, there exists—up to...

Optimal probabilistic fingerprint codes
Gábor Tardos
Article No.: 10
DOI: 10.1145/1346330.1346335

We construct binary codes for fingerprinting digital documents. Our codes for n users that are ε-secure against c pirates have length O(c2log(n/ε)). This improves the codes proposed by Boneh...

Minimum-weight triangulation is NP-hard
Wolfgang Mulzer, Günter Rote
Article No.: 11
DOI: 10.1145/1346330.1346336

A triangulation of a planar point set S is a maximal plane straight-line graph with vertex set S. In the minimum-weight triangulation (MWT) problem, we are looking for a triangulation of a given point set that minimizes the...