We propose to demonstrate Rubato DB, a highly scalable NewSQL system, supporting various consistency levels from ACID to BASE for OLTP and big data applications. Rubato DB employs the staged grid architecture with a novel formula based protocol for distributed concurrency control. Our demonstration will present Rubato DB as one NewSQL database management system running on a collection of commodity servers against two of benchmark sets.

Big data applications demand and consequently lead to developments of large-scale data management systems, which provide high scalability by partitioning data across multiple servers. Since conventional transactional access is quite expensive, many real world large-scale distributed systems eschew transactional functionality and adopt semantics of atomic multi-partition operations. Accordingly, BASE, a consistency model weaker than ACID, is commonly used to guarantee availability. In this work, we identify a new consistency model-BASIC (Basic Availability, Scalability, Instant Consistency) that matches the requirements where extra efforts are not needed to manipulate inconsistent soft states. We present a timestamp-based formula protocol for BASIC that can enforce Instant Consistency while achieving linear scalability (via logical formula caching, dynamic timestamp ordering) and achieve Basic Availability in the presence of partial failure and network partition (via partition independence, genuine atomic commit). Our extensive experimental results verify the scalability of BASIC and demonstrate that the limited overhead induced by BASIC pays a reasonable price for keeping all soft states consistent.

This paper proposes a new formula protocol for distributed concurrency control, and specifies a staged grid architecture for highly scalable database management systems. The paper also describes novel implementation techniques of Rubato DB based on the proposed protocol and architecture. We have conducted extensive experiments which clearly show that Rubato DB is highly scalable with efficient performance under both TPC-C and YCSB benchmarks. Our paper verifies that the formula protocol and the staged grid architecture provide a satisfactory solution to one of the important challenges in the database systems: to develop a highly scalable database management system that supports various consistency levels from ACID to BASE.

Top-k ranking for an uncertain database is to rank tuples in it so that the best k of them can be determined. The problem has been formalized under the unified approach based on parameterized ranking functions (PRFs) and the possible world semantics. Given a PRF, one can always compute the ranking function values of all the tuples to determine the top-k tuples, which is a formidable task for large databases. In this paper, we present a general approach to pruning for the framework based on PRFs. We show a mathematical manipulation of possible worlds which reveals key insights in the part of computation that may be pruned and how to achieve it in a systematic fashion. This leads to concrete pruning methods for a wide range of ranking functions. We show experimentally the effectiveness of our approach.

Abstract Description Logic Programs (dl-programs) proposed by Eiter et al. constitute an elegant yet powerful formalism for the integration of answer set programming with description logics, for the Semantic Web. In this paper, we generalize the notions of completion and loop formulas of logic programs to description logic programs and show that the answer sets of a dl-program can be precisely captured by the models of its completion and loop formulas. Furthermore, we propose a new, alternative semantics for dl-programs, called the canonical answer set semantics, which is defined by the models of completion that satisfy what are called canonical loop formulas. A desirable property of canonical answer sets is that they are free of circular justifications. Some properties of canonical answer sets are also explored.

Abstract This paper studies the stable model semantics of logic programs with (abstract) constraint atoms and their properties. We introduce a succinct abstract representation of these constraint atoms in which a constraint atom is represented compactly. We show two applications. First, under this representation of constraint atoms, we generalize the Gelfond–Lifschitz transformation and apply it to define stable models (also called answer sets) for logic programs with arbitrary constraint atoms. The resulting semantics turns out to coincide with the one defined by Son et al. (2007), which is based on a fixpoint approach. One advantage of our approach is that it can be applied, in a natural way, to define stable models for disjunctive logic programs with constraint atoms, which may appear in the disjunctive head as well as in the body of a rule. As a result, our approach to the stable model semantics for logic programs with constraint atoms generalizes a number of previous approaches. Second, we show that our abstract representation of constraint atoms provides a means to characterize dependencies of atoms in a program with constraint atoms, so that some standard characterizations and properties relying on these dependencies in the past for logic programs with ordinary atoms can be extended to logic programs with constraint atoms.

We present a new characterization of termination of general logic programs. Most existing termination analysis approaches rely on some static information about the structure of the source code of a logic program, such as modes/types, norms/level mappings, models/interargument relations, and the like. We propose a dynamic approach that employs some key dynamic features of an infinite (generalized) SLDNF-derivation, such as repetition of selected subgoals and recursive increase in term size. We also introduce a new formulation of SLDNF-trees, called generalized SLDNF-trees. Generalized SLDNF-trees deal with negative subgoals in the same way as Prolog and exist for any general logic programs.

This paper proposes a formalism for nonmonotonic reasoning based on prioritized argumentation. We argue that nonmonotonic reasoning in general can be viewed as selecting monotonic inferences by a simple notion of priority among inference rules. More importantly, these types of constrained inferences can be specified in a knowledge representation language where a theory consists of a collection of rules of first order formulas and a priority among these rules. We recast default reasoning as a form of prioritized argumentation and illustrate how the parameterized formulation of priority may be used to allow various extensions and modifications to default reasoning. We also show that it is possible, but more difficult, to express prioritized argumentation by default logic: Even some particular forms of prioritized argumentation cannot be represented modularly by defaults under the same language.

In this paper, we present a new approach to the problem of revising extended programs; we base this approach on the coherence theory initially advocated by Gardenfors for belief revision. Our approach resolves contradiction by removing only conflicting information, not the believed source of it, and therefore, keeps information loss minimal. Furthermore, since there is no need to search for problematic assumptions, as is done in the traditional assumption-removal approach, our approach provides a skeptical revision semantics that is tractable. We define the skeptical and credulous coherence semantics and show that both semantics can be characterized in terms of the fixpoint semantics of a revised program using a simple program-revision technique. These semantics provide a suitable framework for knowledge and belief revision in the context of logic programs. Semantical properties and advantages of the proposed revision semantics are also analyzed.

A program is first-order reducible (FO-reducible) w.r.t. a set IC of integrity constraints if there exists a first-order theory T such that the set of models for T is exactly the set of intended models for the program w.r.t. all possible EDBs. In this case, we say that P is FO-reducible to T w.r.t. IC. For FO-reducible programs, it is possible to characterize, using first-order logic implications, properties of programs that are related to all possible EDBs as in the database context. These properties include, among others, containment of programs, independence of updates w.r.t. queries and integrity constraints, and characterization and implication of integrity constraints in programs, all of which have no known proof procedures. Therefore, many important problems formalized in a nonstandard logic can be dealt with by using the rich reservoir of first-order theorem-proving tools, provided that the program is FO-reducible. The following classes of programs are shown to be FO-reducible: (1) a stratified acyclic program P is FO-reducible to comp(P)/spl cup/IC w.r.t. IC for any set IC of constraints; (2) a general chained program P is FO-reducible to comp(P')/spl cup/IC w.r.t. certain acyclicity constraints IC; and (3) a bounded program P is FO-reducible to comp(P')/spl cup/IC w.r.t. any set IC of constraints, where P' is a nonrecursive program equivalent to P. Some heuristics for constructing FO-reducible programs are described.>

Programs for which the least fixed point exists are considered. A program is first-order logic reducible (FOL-reducible) with respect to a set of integrity constraints if all its valid fixed points are least fixed points. For an FOL-reducible program, a logical assertion about least fixed points is reduced to a logical assertion about all first-order logic models. This makes it possible to characterize, in the first-order logic, some important 'all states' properties of programs for which no proof procedures exist in general. This method is applied to the following properties: containment of programs, independence of updates with respect to queries and integrity constraints, and characterization and implication of integrity constraints in programs. It is shown that the transitive closure of a graph if FOL-reducible with respect to the constraint of acyclicity. The 'all states' framework requires a modification of the standard treatment of fixed points and completed programs.>

The central issue of this paper concerns the truth value undefined in Przymusinsi's 3-valued formalization of nonmonotonic reasoning and logic programming. We argue that this formalization can lead to the problem of unintended semantics and loss of disjunctive information. We modify the formalization by proposing two general principles for logic program semantics: justifiability and minimal undefinedness. The former is shown to be a general property for almost all logic program semantics, and the latter requires the use of the undefined only when it is necessary. We show that there are three types of information embedded in the undefined: the disjunctive, the factoring, and the “difficult-to-be-assigned”. In the modified formalization, the first two can be successfully identified and branched into multiple models. This leaves only the “difficult-to-be-assigned” as the undefined. It is shown that the truth value undefined is needed only for a very special type of programs whose practicality is yet to be evidenced.

Article Free Access Share on A sound and complete query evaluation algorithm for relational databases with disjunctive information Authors: L. Y. Yuan Database Research Laboratory, Department of Computing Science, University of Alberta, Edmonton, CANADA T6G 2H1 Database Research Laboratory, Department of Computing Science, University of Alberta, Edmonton, CANADA T6G 2H1View Profile , D.-A. Chiang The Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LA The Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, LAView Profile Authors Info & Claims PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMarch 1989 Pages 66–74https://doi.org/10.1145/73721.73727Online:29 March 1989Publication History 15citation160DownloadsMetricsTotal Citations15Total Downloads160Last 12 Months7Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Recently, several researchers have discussed the advantages of extending the relational model by allowing nested relations (i.e., non-first-normal form relations). In this paper, we address the problem of designing a database with the nested relations with respect to semantic integrity constraints so that a better model of the real world can be obtained. We first define a normal form for nested relations, called nested normal form, utilizing the functional and multivalued dependencies, and then give an algorithm to a obtain such a database scheme.

We define extended conflict free dependencies in the context of functional and multivalued dependencies, and prove that there exists an acyclic, dependency preserving, 4NF database scheme if and only if the given set of dependencies has an extended conflict free cover. This condition can be checked in polynomial time. A polynomial time algorithm to obtain such a scheme for a given extended conflict free set of dependencies is also presented. The result is also applicable when the data dependencies consists of only functional dependencies, giving the necessary and sufficient condition for an acyclic, dependency preserving BCNF database scheme

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. Given a set of attributes U , and a set of multivalued dependencies (MVDs) M over these attributes, we present an algorithm to obtain a nested normal form decomposition of U with respect to M . Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVDs implied by M , and being a faithful and nonredundant representation of U . Moreover, if the given set of MVDs is conflict-free, then the nested normal form decomposition is also dependency-preserving. Finally, we show that if M is conflict-free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4NF decomposition [9, 16] of U with respect to M .

Multivalued dependencies (MVDs) are data dependencies that appear frequently in the “real world” and play an important role in designing relational database schemes. Given a set of MVDs to constrain a database scheme, it is desirable to obtain an equivalent set of MVDs that do not have any redundancies. In this paper we define such a set of MVDs, called reduced MVDs, and present an algorithm to obtain reduced MVDs. We also define a minimal cover of a set of MVDs, which is a set of reduced MVDs, and give an efficient method to find such a minimal cover. The significance and properties of reduced MVDs are also discussed in the context of database design (e.g., 4NF decomposition) and conflict-free MVDs.

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called nested normal form.Given a universal scheme U, and a set of multivalued dependencies (MVD's) M, we present an algo rithm to obtain a nested normal form decomposition of U w.r.t.M. Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVD's implied by M, and being a faithful and nonredundant representation of U.Moreover, if M is conflict free, then the nested normal form decomposition is also dependency preserving.Finally, we show that if M is conflict free, then the unique 4NF decomposition [Fa, L2 ] (which is also in SFNF [BK2]), of U is precisely the set of root-to-leaf paths of scheme trees in nested normal form decomposition of U w.r.t.M.