Simplified integrity checking for an expressive class of denial constraints
Davide Martinenghi · 2024
Read Simplified integrity checking for an expressive class of denial constraints by Davide Martinenghi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20871.txt.
Description
Abstract Data integrity is crucial for ensuring data correctness and quality, maintained through integrity constraints that must be continuously checked, especially in data-intensive systems like OLTP. While DBMSs handle common constraints well, complex constraints often require ad-hoc solutions. Research since the 1980s has focused on automatic and simplified integrity constraint checking, leveraging the assumption that databases are consistent before updates.
Catalog record
| CREATOR | Davide Martinenghi |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-20871
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Simplified integrity checking for an expressive class of denial constraints Davide Martinenghi Abstract Data integrity is crucial for ensuring data correctness and quality, maintained through integrity constraints that must be continuously checked, especially in data-intensive systems like OLTP. While DBMSs handle common constraints well, complex constraints often require ad-hoc solutions. Research since the 1980s has focused on automatic and simplified integrity constraint checking, leveraging the assumption that databases are consistent before updates. This paper discusses using program transformation operators to generate simplified integrity constraints, focusing on complex constraints expressed in denial form. In particular, we target a class of integrity constraints, called extended denials, which are more general than tuple-generating dependencies and equality-generating dependencies. These techniques can be readily applied to standard database practices and can be directly translated into SQL. Keywords— skyline, flexible skyline, top- k query, random access 1 Introduction Data integrity is a ubiquitous concern that is at the basis of crucial objectives such as data correctness and data quality. Typically, a specification of the correct states of a database is given through integrity constraints, which can be thought of as formulas that need to be kept satisfied throughout the life of the database. In any data-intensive scenario, such as an OLTP system, date are updated all the time and, therefore, integrity constraints need to be checked continuously. While DBMSs are able to optimally handle common constraints such as key and foreign key constraints, the standard practice is to resort to ad-hoc solutions (for instance, at the application level or through manually designed triggers) when the integrity constraints to be maintained are more complex. Automatic integrity constraint checking, and, in particular, simplified integrity constraint checking is a topic that has spurred numerous research attempts since the 1980s with the objective of mechanically producing the best possible set of conditions to check against a database in the face of updates. The main idea, common to the majority of the approaches, is to exploit the assumption that a database is consistent (i.e., satisfies the integrity constraints) before an update; with this, the formula to be checked, corresponding to the original integrity constraints, may be simplified so as to avoid checks of subformulas that are already guaranteed to hold thanks to the consistency assumption. For instance, consider the relation b(I,T) , indicating that there is a book with an ISBN I and a title T . The fact that the ISBN univocally identifies a book can be expressed as the integrity constraint T_{1}=T_{2}\leftarrow b(I,T_{1})\land b(I,T_{2}) (with all variables implicitly universally quantified). Now, assume that the tuple b(i,t) is added to the database. Under the consistency assumption, one just needs to check that there is no other book with the same ISBN i and a different title than t , 1 1 1 We are using set semantics, so having more than one occurrence of b(i,t) is harmless. which could be expressed by the simplified formula T=t\leftarrow b(i,T) . Without the consistency assumption, instead, we would have had to check satisfaction of the original constraint for all the books already present in the database. In this paper, we discuss the use of program transformation operators to the generation of simplified integrity constraints. We focus on databases and constraints for which we can implement these operators in terms of rewrite rules based on resolution, subsumption and replacement of specific patterns. In particular, we concentrate on integrity constraints that are more expressive than tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs), which we express in denial form with negated existential quantifiers, possibly nested. The techniques described here can be immediately applied to standard database practice, since our logical notation can be easily translated into SQL. Our results are mainly taken from an unpublished chapter of the Ph.D. dissertation [ 61 ] . To the best of our knowledge, to date there is no other approach that has considered such an expressive class of constraints for the problem of simplified integrity constraint checking. 2 Relational and deductive databases In this chapter we present the basic notation related to deductive databases, and use the syntax of the datalog language as a basis to formulate the main concepts. We refer to standard texts in logic, logic programming and databases such as [ 76 , 66 ] for further discussion. As a notational convention, we use lowercase letters to denote predicates ( p , q , \ldots ) and constants ( a , b , \ldots ) and uppercase letters ( X , Y , \ldots ) to denote variables . A term is either a variable or a constant; conventionally, terms are also denoted by lowercase letters ( t , s , \ldots ) and sequences of terms are indicated by vector notation, e.g., \mathaccent 382{t} . The language also includes standard connectives ( \land , \lor , \lnot , \leftarrow ), quantifiers, and punctuation. In quantified formulas such as (\forall XF) and (\exists XF) , X is said to be bound ; a variable not bound is said to occur free . A formula with no free variables is said to be closed . Free variables are indicated in boldface ( {\mathbf{a}} , {\mathbf{b}} , \dots ) and referred to as parameters ; the other variables, unless otherwise stated, are assumed to be universally quantified. Formulas of the form p(t_{1},\ldots,t_{n}) are called atoms . An atom preceded by a \lnot symbol is a negated atom ; a literal is either an atom or a negated atom. Predicates are divided into three pairwise disjoint sets: intensional , extensional , and built-in predicates. Intensional and extensional predicates are collectively called database predicates ; atoms and literals are classified similarly according to their predicate symbol. There is one built-in binary predicate for term equality ( = ), written using infix notation; t_{1}\neq t_{2} is a shorthand for \lnot(t_{1}=t_{2}) for any two terms t_{1} , t_{2} . A substitution \{\mathaccent 382{X}/\mathaccent 382{t}\} is a mapping from the variables in \mathaccent 382{X} to the terms in \mathaccent 382{t} ; its application is the expression arising when each occurrence of a variable in \mathaccent 382{X} is simultaneously replaced by the corresponding term in \mathaccent 382{t} . A formula or term which contains no variables is called ground . A substitution \{\mathaccent 382{X}/\mathaccent 382{Y}\} is called a renaming iff \mathaccent 382{Y} is a permutation of \mathaccent 382{X} . Formulas F , G are variants of one another if F=G\rho for some renaming \rho . A substitution \sigma is said to be more general than \theta iff there exists a substitution \eta such that \theta=\sigma\eta . A unifier of t_{1},\dots,t_{n} is a substitution \sigma such that t_{1}\sigma=\dots=t_{n}\sigma ; \sigma is a most general unifier (mgu) of t_{1},\dots,t_{n} if it is more general than any other unifier thereof. A clause is a disjunction of literals L_{1}\lor\dots\lor L_{n} . In the context of deductive databases, clauses are expressed in implicational form, A\leftarrow L_{1}\land\cdots\land L_{n} , where A is an atom and L_{1},\ldots,L_{n} are literals; A is called the head and L_{1}\land\cdots\land L_{n} the body of the clause. The head is optional and when it is omitted the clause is called a denial . A rule is a clause whose head is intensional, and a fact is