7 results for Link, Sebastian, Conference item, 2010

  • Efficient inference control for open relational queries

    Biskup, J; Hartmann, S; Link, Sebastian; Lochner, JH (2010-08-24)

    Conference item
    The University of Auckland Library

    We present a control mechanism for preserving confidentiality in relational databases under open queries. This mechanism is based on a reduction of costly inference control to efficient access control that has recently been developed for closed database queries. Our approach guarantees that secrets being declared in form of a confidentiality policy are not disclosed to database users even if they utilize their a priori knowledge to draw inferences. It turns out that there is no straightforward transition from the approach for closed queries to open queries. We show, however, that hiding the confidentiality policy from database users is sufficient to preserve confidentiality. Moreover, we propose an algorithmic implementation of the control mechanism.

    View record details
  • Hippocratic databases: extending current transaction processing approaches to satisfy the limited retention principle

    Kirchberg, M; Link, Sebastian (2010-01)

    Conference item
    The University of Auckland Library

    The concept of Hippocratic Database Systems has been introduced by Agrawal et al. Based on international privacy legislation, ten privacy principles have been identified that an information system should meet in order to enforce privacy and data protection properties. Among those, the limited retention principle and its challenges to traditional database algorithms are considered in this paper. In particular, we examine how data records cannot merely be deleted from the database but also how their corresponding log records may be erased from the log (without violating the necessity to retain data recoverability properties). To the best of our knowledge, there exists no current transaction processing or data recovery approach that supports the deletion of data from log entries as desired by Hippocratic Database Systems.

    View record details
  • Chasing after secrets in relational databases

    Biskup, J; Hartmann, S; Link, Sebastian; Lochner, JH (2010-05)

    Conference item
    The University of Auckland Library

    Inference control can guarantee confidentiality but is costly to implement. Access control can be implemented efficiently but cannot guarantee confidentiality. Hence, it is a natural question to ask when exactly inference control becomes necessary. We characterize the situation in which it becomes possible to infer secrets without any violation of a given access control policy. For this purpose, we establish the Chase as a tool that infers secrets from previous query answers by applying a class of equality- and tuple-generating data dependencies declared over the underlying schema. Our characterization aims to exploit new opportunities for maximizing the availability of data while confidentiality is preserved dynamically and efficiently.

    View record details
  • When data dependencies over SQL tables meet the logics of Paradox and S-3

    Hartmann, S; Link, Sebastian (2010)

    Conference item
    The University of Auckland Library

    We study functional and multivalued dependencies over SQL tables with NOT NULL constraints. Under a "no information" interpretation of null values we develop tools for reasoning. We further show that in the absence of NOT NULL constraints the associated implication problem is equivalent to that in propositional fragments of Priest's paraconsistent Logic of Paradox. Subsequently, we extend the equivalence to Boolean dependencies and to the presence of NOT NULL constraints using Schaerf and Cadoli's S-3 logics where S corresponds to the set of attributes declared NOT NULL. The findings also apply to Codd's interpretation "value at present unknown" utilizing a weak possible world semantics. Our results establish NOT NULL constraints as an effective mechanism to balance the expressiveness and tractability of consequence relations, and to control the degree by which the existing classical theory of data dependencies can be soundly approximated in practice.

    View record details
  • On the role of the complementation rule for data dependencies over incomplete relations

    Ferrarotti, F; Hartmann, S; Link, Sebastian (2010-07-02)

    Conference item
    The University of Auckland Library

    Recently, an axiomatization for functional dependencies (FDs) and multivalued dependencies (MVDs) has been established where arbitrary attributes can be specified as NOT NULL. That is, the information stored over such attributes must not be incomplete. The axiomatization subsumes previous axiomatizations of FDs and MVDs where every attribute is declared to be NOT NULL, and where no attribute is declared to be NOT NULL. We establish axiomatizations which underpin formally the intuition that the complementation rule is a mere means of database normalization. The results unburden the existing theory of the strong assumption that all attributes are known at the time when the dependencies are specified. The findings extend and unify previous results for the special cases above.

    View record details
  • Promoting the semantic capability of XML keys

    Ferrarotti, F; Hartmann, S; Link, Sebastian; Wang, J (2010-09-15)

    Conference item
    The University of Auckland Library

    Keys for XML data trees can uniquely identify nodes based on the data values on some of their subnodes, either in the entire tree or relatively to some selected subtrees. Such keys have an impact on several XML applications. A challenge is to identify expressive classes of keys with good computational properties. In this paper, we propose such a new class of keys. In comparison to previous work, the new class of XML keys is defined using a more expressive navigational path language that allows the specification of single-label wildcards. This provides designers with an enhanced ability to capture properties of XML data that are significant for the application at hand. We establish a sound and complete set of inference rules that characterizes all keys that are implicit in the explicit specification of XML keys. Furthermore, we establish an efficient algorithm for deciding XML key implication.

    View record details
  • Solving the implication problem for XML functional dependencies with properties

    Hartmann, S; Link, Sebastian; Trinh, T (2010-07-02)

    Conference item
    The University of Auckland Library

    Due to the complex nature of XML, finding classes of integrity constraints for XML data that are both expressive and practical is an important but challenging task. In this paper, we study a class of XML functional dependencies (called pXFDs) defined on the basis of tree homomorphism. We establish a semantic equivalence between the implications problems for pXFDs and for propositional Horn clauses, which guarantees linear time decidability of pXFD implication. Hence, pXFDs cannot only be used to capture relevant data semantics, but also be reasoned about efficiently.

    View record details