text:
@inproceedings{10.1145/308386.308396,
author = {Chandra, Ashok K.},
title = {Theory of Database Queries},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308396},
doi = {10.1145/308386.308396},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {1–9},
numpages = {9},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308397,
author = {Kuper, Gabriel M.},
title = {On the Expressive Power of Logic Programming Languages with Sets},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308397},
doi = {10.1145/308386.308397},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {10–14},
numpages = {5},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308400,
author = {Shmueli, Oded and Tsur, Shalom and Zaniolo, Carlo},
title = {Rewriting of Rules Containing Set Terms in a Logic Data Language LDL},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308400},
doi = {10.1145/308386.308400},
abstract = {We propose compilation methods for supporting set terms in Horn clause programs, without using general-purpose set matching algorithms, which tend to run in times exponential in the size of the participating sets Instead, we take the approach of formulating specialized computation plans that, by taking advantage of information available in the given rules, limit the number of alternatives explored. Our strategy is to employ compile time rewriting techniques and to transform the problem into an “ordinary” Horn clause compilation problem, with minimal additional overhead. The execution cost of the rewritten rules is substantially lower than that of the original rules and the additional cost of compilation can thus be amortized over many executions},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {15–28},
numpages = {14},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308402,
author = {Paredaens, Jan and Van Gucht, Dirk},
title = {Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308402},
doi = {10.1145/308386.308402},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {29–38},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308409,
author = {Hull, Richard and Su, Jianwen},
title = {On the Expressive Power of Database Queries with Intermediate Types},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308409},
doi = {10.1145/308386.308409},
abstract = {The set-height of a complex object type is defined to be its level of nesting of the set construct. In a query of the complex object calculus which maps a database D to an output type T, an intermediate type is a type which is used by some variable of the query, but which is not present in D or T. For each k, i ≥ 0 we define CALCk,i to be the family of calculus queries mapping from and to types with set-height ≤ k and using intermediate types with set-height ≤ i In particular, CALC0,0 is the relational calculus, and CALC0,1 is equivalent to the family of second-order (relational) queriesSeveral results concerning these families of languages are obtained. A primary focus is on the families CALC0,i, which map relations to relations Upper bounds on the complexity of these families are provided, and it is shown that CALC0,3 has at least the complexity of exponential space. The CALC0,i hierarchy does not collapse, because for each i, CALC0,i is strictly less expressive than CALC0,i+2. The union ∪0≤iCALC0,i is strictly less expressive than the family of 'computable' database queries.The expressive power of queries from the complex object calculus interpreted using a semantics based on the use of arbitrarily large finite numbers of invented values is studied. Under this semantics, the expressive power of the relational calculus is not increased, and the CALC0,i hierarchy collapses at CALC0,1. We also consider queries which use a bounded number of invented values.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {39–51},
numpages = {13},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308412,
author = {Kifer, Michael and Ramakrishnan, Raghu and Silberschatz, Avi},
title = {An Axiomatic Approach to Deciding Query Safety in Deductive Databases},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308412},
doi = {10.1145/308386.308412},
abstract = {A database query is safe if its result consists of a finite set of tuples. If a query is expressed using a set of pure Horn Clauses, the problem of determining query safety is, in general, undecidable. In this paper we consider a slightly stronger notion of safety, called supersafety, for Horn databases in which function symbols are replaced by the abstraction of infinite relations with finiteness constraints [Ramarkrishman et. al 87] We show that the supersafety problem is not only decidable, but also axiomatizable, and the axiomatization yields an effective decision procedure. Although there are safe queries which are not supersafe, we demonstrate that the latter represent quite a large and nontrivial portion of the safe of all safe queries},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {52–60},
numpages = {9},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308416,
author = {Chomicki, Jan and Imieli\'{n}ski, Tomasz},
title = {Temporal Deductive Databases and Infinite Objects},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308416},
doi = {10.1145/308386.308416},
abstract = {We discuss deductive databases with one fixed occurrence of a monadic function symbol(successor) per predicate Databases of this kind can be used in a natural way to model simple patterns of events repeated in time, and this is why we term them temporal. Temporal deductive databases are also interesting from a theoretical point of view, because they give rise to infinite least fix-points and infinite query answers. We study complexity properties of finite query answers and define the notion of infinite objects which makes some infinite least fixpoints computable in finite time},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {61–73},
numpages = {13},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308417,
author = {Ullman, Jeffrey D. and Vardi, Moshe Y.},
title = {The Complexity of Ordering Subgoals},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308417},
doi = {10.1145/308386.308417},
abstract = {Selection of an appropriate order for the evaluation of subgoals in a logical rule frequently is essential for efficiency. We formulate the problem as one of feasible subgoal orders and show that the question is inherently exponential in time. The proof is by reduction from linear-space alternating Turing machine recognition, which appears to be far easier, in this case, than the more obvious reduction from exponential-time (ordinary) Turing machines},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {74–81},
numpages = {8},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308419,
author = {Morris, Katherine A.},
title = {An Algorithm for Ordering Subgoals in NAIL?},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308419},
doi = {10.1145/308386.308419},
abstract = {Rule-goal graphs are the central data structures used in the NAIL′ system, a knowledge-base system being developed at Stanford University They are constructed while testing the applicability of capture rules, and traversed while generating ICODE to evaluate queries. Generating rule-goal graphs may be reduced to the problem of ordering subgoals. This paper gives an algorithm for generating rule-goal graphs efficiently, in time polynomial in the size of the rules if the arity of recursive predicates is bounded. The graphs generated may be suboptimal for some purposes, but the algorithm will always find a rule-goal graph if one exists. The algorithm has been implemented in Cprolog, and is currently being used to generate rule-goal graphs for the NAIL′ system},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {82–88},
numpages = {7},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308420,
author = {Ramakrishnan, Raghu and Beeri, Catriel and Krishnamurthy, Ravi},
title = {Optimizing Existential Datalog Queries},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308420},
doi = {10.1145/308386.308420},
abstract = {The problem of pushing projections in recursive rules has received little attention. The objective of this paper is to motivate this problem and present some (partial) solutions. We consider programs with function-free rules, also known as Datalog programs. After formally defining existential subqueries, we present a syntactic criterion for detecting them and then consider optimization in three areas 1) We identify the existential subqueries and make them explicit by rewriting the rules. This, in effect, automatically captures some aspects of Prolog's cut operator that are appropriate to the bottom-up model of computation 2) We eliminate argument positions in recursive rules by “pushing projections” 3) We observe that “pushing projections” in rules also has the effect of making some rules (even recursive rules) redundant and try to (identify and) discard them},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {89–102},
numpages = {14},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308422,
author = {Imielinski, Tomasz and Naqvi, Shamim},
title = {Explicit Control of Logic Programs through Rule Algebra},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308422},
doi = {10.1145/308386.308422},
abstract = {In this paper we argue with a basic premise in logic programming research that the meaning of a program can be inferred from its syntax alone. We show that users may have a variety of intended models for programs and that a single program may give different intended models under different assumptions of semantics. Our conclusion is that it is impossible to infer the intended model from the syntax of the program and no single semantics will capture all the intended models. We propose as a solution an explicit specification of control. Towards this purpose we define a rule algebra. The user formulates a program as an algebraic specification that directs the execution towards the intended model. The interesting question at that point is how to efficiently implement such programs. We show a natural and easy transformation such that it takes as input an algebraic specification and produces as output a program belonging to a subclass of locally stratified programs. Moreover, there is a homomorphic correspondence between the algebraic expressions and their translations.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {103–116},
numpages = {14},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308424,
author = {Ramakrishna, M. V. and Mukhopadhyay, P.},
title = {Analysis of Bounded Disorder File Organization},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308424},
doi = {10.1145/308386.308424},
abstract = {Recently Litwin and Lomet proposed the Bounded Disorder (BD) file organization which uses a combination of hashing and tree indexing Lomet provided an approximate analysis with a mention of the difficulty involved in exact modeling and analysis. The performance analysis of the method involves solving a classical sequential occupancy problem. We encountered this problem in our attempt to obtain a general model for single access and almost single access retrieval methods developed in the recent years. In this paper, we develop a probability model and present some preliminary results of the exact analysis.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {117–125},
numpages = {9},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308425,
author = {Srivastava, Jaideep and Rotem, Doron},
title = {Analytical Modeling of Materialized View Maintenance},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308425},
doi = {10.1145/308386.308425},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {126–134},
numpages = {9},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308426,
author = {Hadzilacos, Thanasis},
title = {Serialization Graph Algorithms for Multiversion Concurrency Control},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308426},
doi = {10.1145/308386.308426},
abstract = {We propose a new algorithmic framework for database concurrency control using multiple versions of data items and a serialization graph of the transactions as a synchronization technique, which generalizes all concurrency control methods known so far. This class of algorithms, called MVSGA for Multi Version Serialization Graph set of Algorithms, works by monitoring the acyclicity of the serialization graph which has nodes corresponding to transactions and arcs corresponding to read-from and other transaction positioning decisions made by the scheduler. For each of the major known schedulers we give examples of MVSGA schedulers that cover them.We propose a criterion for optimality among MVSGA schedulers Choice of versions to read from and relative positioning of transactions in the serialization graph should be done in a way that leaves the largest flexibility possible for future choices. This flexibility is measured as the number of pairs of nodes in the serialization graph that remain incomparable. Unfortunately, enforcing this criterion turns out to be NP-complete, so we describe an MVSGA scheduler based on a heuristic that approximates the optimal.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {135–141},
numpages = {7},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308427,
author = {Kelter, Udo},
title = {The Queue Protocol: A Deadlock-Free, Homogeneous, Non-Two-Phase Locking Protocol},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308427},
doi = {10.1145/308386.308427},
abstract = {The M-pitfall protocol (MPP) is the most general homogeneous non-two-phase locking protocol which supports shared and exclusive locks. It has two major disadvantages: it is not deadlock-free and it has the paradoxical property that concurrency is often reduced if shared locks are used instead of exclusive locks. This paper presents a new protocol, the Queue Protocol (QP), which removes these deficiencies. Although the QP can be regarded an enhancement of the MPP, pitfalls are no more used in the QP; thus, the QP has the further advantage that processing overhead due to pitfalls is avoided.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {142–151},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308429,
author = {Banciihon, Fran\c{c}ois},
title = {Object-Oriented Database Systems},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308429},
doi = {10.1145/308386.308429},
abstract = {This paper describes my vision of the current state of object-oriented database research. I first briefly define this field by its objectives, and relate it to other database subfields. I describe what I consider to be the main characteristics of an object oriented system, i.e. those which are important to integrate in a database system: encapsulation, object identity, classes or types, inheritance, overriding and late binding. I point out the differences between an object oriented system and an object oriented database system. I also point out the advantages and drawbacks of an object oriented database system with respect to a relational system. Finally, I list some research issues.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {152–162},
numpages = {11},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308431,
author = {Chan, Edward P. F. and Hernandez, Hector J.},
title = {Independence-Reducible Database Schemes},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308431},
doi = {10.1145/308386.308431},
abstract = {A class of cover embedding database schemes, called independence-reducible, is proposed and is proven to be bounded and algebraic-maintainable, and therefore is highly desirable with respect to query answering and constraint enforcement. This class of schemes is shown to properly contain a superset of all previously known classes of cover embedding BCNF database schemes which are bounded (and constant-time-maintainable). An efficient algorithm is found which recognizes exactly this class of database schemes. Independence-reducible database schemes properly contain a class of constant-time-maintainable database schemes and a condition which characterizes this class of schemes is found, this condition can be tested efficiently. Throughout, it is assumed that a cover of the functional dependencies is embedded in the database scheme in the form of key dependencies.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {163–173},
numpages = {11},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308434,
author = {Hegner, Stephen J.},
title = {Decomposition of Relational Schemata into Components Defined by Both Projection and Restriction},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308434},
doi = {10.1145/308386.308434},
abstract = {A generalized approach to the decomposition of relational schemata is developed in which the component views may be defined using both restriction and projection operators, thus admitting both horizontal and vertical decompositions. The realization of restrictions is enabled through the use of a Boolean algebra of types, while true independence of projections is modelled by permitting null values in the base schema. The flavor of the approach is algebraic, with the collection of all candidate views of a decomposition modelled within a lattice-like framework, and the actual decompositions arising as Boolean subalgebrac. Central to the framework is the notion of sidimensional join dependency, which generalizes the classical notion of join dependency by allowing the components of the join to be selected horizontally as well as vertically. Several properties of such dependencies are presented, including a generalization of many of the classical results known to be equivalent to schema acyclicity. Finally, a characterization of the nature of dependencies which participate in decompositions is presented. It is shown that there are two major types, the bidimensional join dependencies, which are tuple generating and allow tuple removal by implicit encoding of knowledge, and splitting dependencies, which simply partition the database into two components.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {174–183},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308435,
author = {Batory, D. S.},
title = {Concepts for a Database System Compiler},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308435},
doi = {10.1145/308386.308435},
abstract = {We propose a very simple formalism based on parameterized types and a rule-based algebra to explain the storage structures and algorithms of database management systems. Implementations of DBMSs are expressed as equations If all functions referenced in the equations have been implemented the software for a DBMS can be synthesized in minutes at little cost, in contrast to current methods where man-years of effort and hundreds of thousands of dollars are required. Our research aims to develop a DBMS counterpart to today's compiler-complier technologies},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {184–192},
numpages = {9},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308438,
author = {Hadzilacos, Thanasis and Hadzilacos, Vassos},
title = {Transaction Synchronisation in Object Bases},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308438},
doi = {10.1145/308386.308438},
abstract = {In this paper we investigate the problem of synchronising transactions in an object base. An object base is a collection of objects, much the way a database is a collection of data. An object, for our purposes, consists of a collection of variables (whose values at any point in time comprise the state of that object) and a set of operations, called methods, that are the only means of accessing (sensing or modifying) the object's variablesThere is a certain sense in which a traditional database is an object base. It consists of “objects” (records, tuples or what have you) each of which has a state that can be accessed only through the operations Read and Write. The main difference is that in an object base, each object supplies its own methods and these are arbitrary. In particular, a method for a certain object may call methods of other objects to carry out its task. In contrast to certain models in which objects correspond to “levels of abstraction”, our model is completely general in this respect for example, it is permissible for a method of object A to call a method of object B which, in turn, may call some other method of object A againOne implication of this difference between data and object bases is that in the latter the assumption, commonly made in the former, that the operations which manipulate the state of the objects are short enough to be implemented serially (one at a time) is no longer valid. A related implication is that in object bases we are faced with the necessity of dealing with nested transactions, since the invocation of one method may result in further method invocationsAnother, less fundamental, difference between data and object bases is that, in addition to being of uniform type, the “objects” of a database are usually assumed to be of uniform size as well. In an object base one can imagine objects of widely differing sizes. A clock and the New York City telephone directory could be objects differing in size by orders of magnitude, yet co-existing in the same object baseIn spite of these differences it is possible to approach concurrency control in an object base in the following way. Each object is viewed as a database item. Further, each method invocation is treated as a group of Read or Write operations on those data items that were accessed as a result of that method invocation. With these analogies, any conventional database concurrency control method (two-phase locking, timestamp ordering, certification, and the whole lot) can be employed to synchronise concurrent transactions in the object base. This approach has the virtue of simplicity and may be well-suited to certain environments. It is, for example, the approach taken in the GemStone project and product (cf Maier and Stein [1987], Purdy et al [1987])We are interested in exploring approaches to concurrency control in object bases which take into account their special features and differences from databases. The hope is that this will lead to more efficient techniques. More specifically, we would like to consider mechanisms that
Take into account the nested nature of transactionsAllow methods accessing an object to execute concurrently (but correctly) This seems especially important as multiprocessors become available, since forcing serial access to an object's methods restricts parallelism (bear in mind that each method could be a lengthy procedure)Are modular, in that each object is responsible for synchronizing the invocations of its own methods as it sees fitThe first two of these points have been considered by others as well. For example, Argus (cf Liskov and Scheifler [1983]) uses a synchronisation algorithm which is an adaptation of strict two-phase locking in a nested transaction environment. In addition, Argus allows multiple concurrent invocations of an object's methods1We believe that the third point is a novel idea, so we elaborate on it a bit. In accordance with (b), multiple invocations of an object's methods may be active simultaneously As these methods may operate on common data (the object's variables), they must be synchronised. That is, if we view the object's variables as a database, and the simultaneous method invocations as concurrent transactions, we have to solve the serialisability problem within a single object. We call this intra-object synchronisationIt is not difficult to see that simply ensuring serialisability within each object is not, in itself, enough to guarantee serialisability of the overall computation. For instance, then may be two transactions T1 and T2 each accessing objects A and B, so that in object A the concurrent computation of the two transactions' method executions serialises T1 before T2, while the reverse holds in object B.The effect of such an execution is not the same as running the two transactions serially in either order and the overall computation is therefore not serial, sable, even though the computation at each object is Thus, in addition to intra-object synchronisation, it is also necessary to exercise some inter-object synchronisation, whose goal will be to ensure the compatibility of the independent decisions made at each objectThe potential advantage of separating intra- from inter-object synchronisation is seen if one recalls our previous observation regarding the non-uniformity of objects in an object base. Accordingly, we may be able to allow each object use, for intra-object synchronisation, the most suitable algorithm depending on its semantics, the implementation of its methods and so on. For example, an object representing and Delete) might be implemented as a B-tree. Thus, one of the many special B-tree algorithms could be used for intra-object synchronisation by this object (cf Bayer and Schkolnick [1977], Ellis [1980], Kung and Lehman [1980], Kwong and Wood [1982], Lehman and Yao [1981], Manber and Ladner [1982], Samadi [1976]) That object would enjoy the efficiency of the special algorithm, even though that algorithm is not applicable to other types of objects. Of course, the viability of such a scheme depends on the existence of efficient inter-object synchronisation schemes that can be used with disparate intra-object synchronisation algorithms. Even though we have no definitive answer for this question, our work so far leaves us hopeful that this may indeed be possibleThe remainder of this paper is organised as follows. In Section 2 we present a formal model for representing executions in object bases, we also define what serialisable (i e correct) executions are in this context. In Section 3 we present an extension of the Serialisability Theorem of “classical” concurrency control, which relates the serialisability of an execution to the acyclicity of a graph. We exhibit the utility of this theorem by using it to derive simple proofs of the correctness of Nested Two-Phase Locking (a slight generalisation of the algorithm used in Argus) and Nested Timestamp Ordering (an algorithm proposed by Reed [1978]). We also present a corollary to this theorem that we feel justifies our hopes for modular synchronisation mechanisms. We conclude with a description of further work in Section 4This work draws on three main sources “classical” serialisability theory (e.g. Bernstein et al [1987], Papadimitriou [1986]), the theory of nested transactions (e.g. Beeri et al [1980], Lynch and Merritt [1986]), and object-oriented systems (e.g. Stefik and Bobrow [1986])},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {193–200},
numpages = {8},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308440,
author = {Herlihy, Maurice P. and Weihl, William E.},
title = {Hybrid Concurrency Control for Abstract Data Types},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308440},
doi = {10.1145/308386.308440},
abstract = {We define a new locking protocol that permits more concurrency than existing commutativity-based protocols. The protocol uses timestamps generated when transactions commit to provide more information about the serialization order of transactions, and hence to weaken the constraints on conflicts. In addition, the protocol permits operations to be both partial and non-deterministic, and it permits results of operations to be used in choosing locks. The protocol exploits type-specific properties of objects, necessary and sufficient constraints on lock conflicts are defined directly from a data type specification. We give a complete formal description of the protocol, encompassing both concurrency control and recovery, and prove that the protocol satisfies hybrid atomicity, a local atomicity property that combines aspects of static and dynamic atomic protocols. We also show that the protocol is optimal in the sense that no hybrid atomic locking scheme can permit more concurrency.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {201–210},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308442,
author = {Lanin, Vladimir and Shasha, Dennis},
title = {Concurrent Set Manipulation without Locking},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308442},
doi = {10.1145/308386.308442},
abstract = {Set manipulation consists of the actions insert, delete, and member on keys. We propose a concurrent set manipulation algorithm that uses no locking at all and requires no aborts, relying instead on atomic read-modify-write operations on single (data) locations. The algorithm satisfies order-preserving serializability through conditions that are strictly looser than existing algorithms},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {211–220},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308444,
author = {Van Gelder, Allen and Ross, Kenneth and Schlipf, John S.},
title = {Unfounded Sets and Well-Founded Semantics for General Logic Programs},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308444},
doi = {10.1145/308386.308444},
abstract = {A general logic program (abbreviated to “program” hereafter) is a set of rules that have both positive and negative subgoals. It is common to view a deductive database as a general logic program consisting of rules (IDB) sitting above elementary relations (EDB, facts). It is desirable to associate one Herbrand model with a program and think of that model as the “meaning of the program,” or its “declarative semantics.” Ideally, queries directed to the program would be answered in accordance with this model. We introduce unfounded sets and well-founded partial models, and define the well-founded semantics of a program to be its well-founded partial model. If the well-founded partial model is in fact a model, we call it the well-founded model, and say the program is “well-behaved”. We show that the class of well-behaved programs properly includes previously studied classes of “stratified” and “locally stratified” programs Gelfand and Lifschits have proposed a definition of “unique stable model” for general logic programs. We show that a program has a unique stable model if it has a well-founded model, in which case they are the same. We discuss why the converse is not true.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {221–230},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308446,
author = {Kolaitis, Phokion G. and Papadimitriou, Christos H.},
title = {Why Not Negation by Fixpoint?},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308446},
doi = {10.1145/308386.308446},
abstract = {There is a fixpoint semantics for DATALOG programs with negation that is a natural generalization of the standard semantics for DATALOG programs without negation. We show that, unfortunately, several compelling complexity-theoretic obstacles rule out its efficient implementation. As an alternative, we propose Inflationary DATALOG, an efficiently implementable semantics for negation, based on inflationary fixpoints},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {231–239},
numpages = {9},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308448,
author = {Abiteboul, Serge and Vianu, Victor},
title = {Procedural and Declarative Database Update Languages},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308448},
doi = {10.1145/308386.308448},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {240–250},
numpages = {11},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308451,
author = {Naqvi, Shamim and Krishnamurthy, Ravi},
title = {Database Updates in Logic Programming},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308451},
doi = {10.1145/308386.308451},
abstract = {The need for control in logic programs is now being recognized. This is particularly evident when one focuses on allowing updates in logic programs. In this paper we propose a language DatalogA which is an extension of Datalog with updates to base relations. We define some procedural constructs to allow update programs to be written in an easy manner. The (W,p) scheme of Dynamic Logic fits nicely into the semantics of DatalogA programs in which W is taken to be the set of all possible states of the program and p is the accessibility relation between states. We give declarative semantics and equivalent constructed model semantics for DatalogA programs. We show that in the absence of updates our semantics reduce to the classical semantics of Datalog. Finally, we show some examples of non-stratified programs expressed in DatalogA.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {251–262},
numpages = {12},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308452,
author = {Muralikrishna, M. and DeWitt, David J.},
title = {Optimization of Multiple-Relation Multiple-Disjunct Queries},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308452},
doi = {10.1145/308386.308452},
abstract = {In this paper we discuss the optimization of multiple-relation multiple-disjunct queries in a relational database system. Since optimization techniques for conjunctive (single disjunct) queries in relational databases are well known [Smith75, Wong76, Selinger79, Yao79, Youssefi79], the natural way to evaluate a multiple-disjunct query was to execute each disjunct independently [Bernstein81, Kerschberg82] However, evaluating each disjunct independently may be very inefficient. In this paper, we develop methods that merge two or more disjuncts to form a term. The advantage of merging disjuncts to form terms lies in the fact that each term can be evaluated with a single scan of each relation that is present in the term. In addition, the number of times a join is performed will also be reduced when two or more disjuncts are merged. The criteria for merging a set of disjuncts will be presented. As we will see, the number of times each relation in the query is scanned will be equal to the number of terms. Thus, minimizing the number of terms will minimize the number of scans for each relation. We will formulate the problem of minimizing the number of scans as one of covering a merge graph by a minimum number of complete merge graphs which are a restricted class of Cartesian product graphs. In general, the problem of minimizing the number of scans is NP-complete. We present polynomial time algorithms for special classes of merge graphs. We also present a heuristic for general merge graphs.Throughout this paper, we will assume that no relations have any indices on them and that we are only concerned with reducing the number of scans for each relation present in the query. What about relations that have indices on them? It turns out that our performance metric of reducing the number of scans is beneficial even in the case that there are indices. In [Muralikrishna88] we demonstrate that when optimizing single-relation multiple-disjunct queries, the cost (measured in terms of disk accesses) may be reduced if all the disjuncts are optimized together rather than individually. Thus, our algorithm for minimizing the number of terms is also very beneficial in cases where indices exist},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {263–275},
numpages = {13},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308455,
author = {Hou, Wen-Chi and Ozsoyoglu, Gultekin and Taneja, Baldeo K.},
title = {Statistical Estimators for Relational Algebra Expressions},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308455},
doi = {10.1145/308386.308455},
abstract = {Present database systems process all the data related to a query before giving out responses. As a result, the size of the data to be processed becomes excessive for real-time/time-constrained environments. A new methodology is needed to cut down systematically the time to process the data involved in processing the query. To this end, we propose to use data samples and construct an approximate synthetic response to a given query.In this paper, we consider only COUNT(E) type queries, where E is an arbitrary relational algebra expression. We make no assumptions about the distribution of attribute values and ordering of tuples in the input relations, and propose consistent and unbiased estimators for arbitrary COUNT(E) type queries. We design a sampling plan based on the cluster sampling method to improve the utilization of sampled data and to reduce the cost of sampling. We also evaluate the performance of the proposed estimators.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {276–287},
numpages = {12},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308458,
author = {Huang, Bing-Chao and Langston, Michael A.},
title = {Stable Set and Multiset Operations in Optimal Time and Space},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308458},
doi = {10.1145/308386.308458},
abstract = {The focus of this paper is on demonstrating the existence of methods for stably performing set and multiset operations on sorted files of data in both optimal time and optimal extra space. It is already known that stable merging and stable duplicate-key extraction permit such methods. The major new results reported herein are these
an asymptotically optimal time and space algorithm is devised for stably selecting matched records from a sorted file,this selection strategy is employed, along with other algorithmic tools, to prove that all of the elementary binary set operations can be stably performed in optimal time and space on sorted files, andafter generalizing these operations to multisets in a natural way for file processing, it is proved that each can be stably performed in optimal time and space on sorted files},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {288–293},
numpages = {6},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308460,
author = {Yu, Lin and Rosenkrantz, Daniel J.},
title = {Minimizing Time-Space Cost for Database Version Control},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308460},
doi = {10.1145/308386.308460},
abstract = {We introduce the concept of a version graph to model the problem of minimising the space and version regeneration cost for database version control. We show that, in general, this problem and several of its variations are NP-complete. Motivated by the practical importance of these problems, we develop several heuristics and obtain worst-case guarantees on their performance. We also present linear time algorithms for problems characterized by special classes of version graphs.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {294–301},
numpages = {8},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308462,
author = {Reiter, Raymond},
title = {What Should a Database Know?},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308462},
doi = {10.1145/308386.308462},
abstract = {The by now conventional perspective on databases, especially deductive databases, is that they are sets of first order sentences. As such, they can be said to be claims about the truths of some external world, the database is a symbolic representation of that world.While agreeing with this account of what a database is, I disagree with how, both in theory and practice, a database is used, specifically how it is queried and how its integrity is enforced.Virtually all approaches to database query evaluation treat queries as first order formulas, usually with free variables whose bindings resulting from the evaluation phase define the answers to the query. The sole exception to this is the work of Levesque (1981, 1984), who argues that queries should be formulas in an epistemic modal logic. Queries, in other words, should be permitted to address aspects of the external world as represented in the database, as well as aspects of the database itself i e aspects of what the database knows. To take a simple example, suppose DB = p y qQuery p (i e is p true in the external world?)Answer unknownQuery Kp (i e. do you know whether p is true in the external world?)Answer noLevesque's modal logic (called KFOPCE) distinguishes between known and unknown individuals in the database and thus accounts for “regular” database values as well as null values. For example, if KB is{Teach (John, Math100), (∃ x) Teach (x, CS100), Teach (Mary, Psych100) y Teach (Sue, Psych100)},thenQuery (∃ x)K Teach (John, x) i e is there a known course which John teaches?Answer yes-Math100Query (∃ x)K Teach (x, CS100) i e is there a known teacher for CS100?Answer NoQuery (∃ x) Teach (x, Psych100) i e does anyone teach Psych 100?Answer: Yes - Mary or SueQuery (∃ x)K Teach (x, Psych100) i e is there a known teacher of Psych100?Answer NoLevesque (1981, 1984) provides a semantics for his language KFOPCE FOPCE, is the first order language KFOPCE without the modal K Levesque proposes that a database is best viewed as a set of FOPCE sentences, and that it be queried by sentences of KFOPCE. He further provides a (noneffective) way of answering database queries.Recently I have considered the concept of a static integrity constraint in the context of Levesque's KFOPCE (Reiter 1988). The conventional view of integrity constraints is that, like the database itself, they too are first order formulas (e g Lloyd & Topor (1985), Nicolas & Yazdanian (1978), Reiter (1984)). There are two definitions in the literature of a deductive database KB satisfying an integrity constraint IC.Definition 1 Consistency (e.g. Kowalski (1978), Sadri and Kowalski (1987)) KB satisfies IC if f KB + IC is satisfiableDefinition 2 Entailment (e g Lloyd and Topor (1985), Reiter (1984)) KB satisfies IC if f KB @@@@ ICAlas, neither definition seems correct. Consider a constraint requiring that employees have social security numbers (Vx) emp (x) ⊃ (∃ y) ss# (x y) (1)1 Suppose KB = {emp (Mary)} Then KB + IC is satisfiable. But intuitively, we want the constraint to require KB to contain a ss# entry for Mary, so we want IC to be violated. Thus Definition 1 does not capture our intuitions.2 Suppose KB = { } Intuitively, this should satisfy IC, but KB @@@@ IC. So Definition 2 is inappropriate.An alternative definition comes to mind when one sees that constraints like (1) intuitively are interpreted as statements not about the world but about the contents of the database, or about what it knows. Thus, using the modal K for “knows”, (1) should be rendered by (Vx K emp (x) ⊃ (∃ y) K ss# (x y)Other Examples1 To prevent a database from simultaneously assigning the properties male and female to the same individual, use the constraint (Vx) ⌍ K (male (x) ∧female (x))2 To force a database to assign one of the properties male and female to each individual, use the constraint (Vx) K person (x) ⊃K male (x) ∨ K female (x)3 To require that known instances of the relation mother(,) have first argument a female person and a second argument a person, use the constraint (Vx, y) K mother (x,y) ⊃ K (person (x) ∧female (x) ∧person (y))4 To require that every known employee have a social security number, without necessarily knowing what that number is (so that a null value is permitted), use (Vx) K emp (x) ⊃ K (∃ y) ss# (x y)My account of integrity constraints therefore, is that rather than being first order sentences, they are sentences of Levesque's KFOPCE. Constraints are not statements about the world, but about the contents of the database. The natural definition of when a database KB satisfies a constraint IC is the following KB satisfies IC iff the answer to IC when viewed as a query to KB is “yes”.In effect, therefore, my proposal is to understand integrity constraints as formally indistinguishable from KFOPCE queries, with the proviso that for any database state the answer to these queries must be “yes”.My talk will elaborate on the above notion of deductive databases. Specifically, it will provide Levesque's semantics for the K operator, discuss query evaluation under the closed world assumption, characterize integrity checking for a natural class of integrity constraints and databases, and conclude with some open research topics.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {302–304},
numpages = {3},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308463,
author = {Buneman, Peter and Davidson, Susan and Watters, Aaron},
title = {A Semantics for Complex Objects and Approximate Queries},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308463},
doi = {10.1145/308386.308463},
abstract = {A new definition of complex objects is introduced which provides a denotation for incomplete tuples as well as partially described sets. Set values are “sandwiched” between “complete” and “consistent” descriptions (representing the Smyth and Hoare powerdomains respectively), allowing the maximal values to be arbitrary subsets of maximal elements in the domain of the set. We also examine the use of rules in defining queries over such objects.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {305–314},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308465,
author = {Winslett, Marianne},
title = {A Framework for Comparison of Update Semantics},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308465},
doi = {10.1145/308386.308465},
abstract = {Scattered across the scientific literature of three or more disciplines appears a profusion of proposals for semantics of updates to logical theories. Because no previous work has compared these proposals with one another, the merits and demerits of the various approaches are not well known. Since the semantics differ from one another in systematic ways, it is possible to generalize from existing proposals and speak of the properties of classes of update semantics. In this paper we suggest a two-dimensional taxonomy for characterizing semantics, and describe the properties inherent to the classes implicit therein. Our discussion includes measurement of the computational complexity of the different classes.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {315–324},
numpages = {10},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308467,
author = {Sippu, Seppo and Soisalon-Soininen, Eljas},
title = {A Generalized Transitive Closure for Relational Queries},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308467},
doi = {10.1145/308386.308467},
abstract = {We augment relational algebra with a generalized transitive closure operator that allows for the efficient evaluation of a subclass of recursive queries. The operator is based on a composition operator which is as general as possible when the operator is required to be associative and when only relational algebra operators are used in its definition. The closure of such a composition can be computed using the well-known efficient algorithms designed for the computation of the usual transitive closure. Besides the case in which complete materialization of recursive relations are required, our strategy also yields an efficient solution in the case in which a selection is applied to the closure.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {325–332},
numpages = {8},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308469,
author = {Haddad, Ramsey W. and Naughton, Jeffrey F.},
title = {Counting Methods for Cyclic Relations},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308469},
doi = {10.1145/308386.308469},
abstract = {In this paper we consider selections of the form “column = constant” on relations defined by linear recursive, two rule datalog programs. In general, counting methods perform well on such queries. However, counting methods fail in the presence of cycles in the database. We present an algorithm in the spirit of counting methods that correctly deals with cyclic data and has the same asymptotic running time as counting methods. The algorithm, which is based on reducing a query on a database to a question about intersections of semi-linear sets, works by using efficient methods to construct the appropriate semi-linear sets from the database and query constant.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {333–340},
numpages = {8},
location = {Austin, Texas, USA},
series = {PODS '88}
}

@inproceedings{10.1145/308386.308470,
author = {Vardi, Moshe Y.},
title = {Decidability and Undecidability Results for Boundedness of Linear Recursive Queries},
year = {1988},
isbn = {0897912632},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/308386.308470},
doi = {10.1145/308386.308470},
abstract = {If it is possible to eliminate recursion from a Datalog program P, then P is said to be bounded. It was shown by Gaifman et al that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs that has one 4-ary intensional predicate. We sharpen that result by showing that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs that has one binary intensional predicate. We then consider linear programs with a single recursive rule. We show that if the intensional predicate is binary, then the boundedness problem for such program is decidable, in fact, it is NP-complete.},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems},
pages = {341–351},
numpages = {11},
location = {Austin, Texas, USA},
series = {PODS '88}
}

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr


text:
DESCRIPTION = "distcc is a parallel build system that distributes \
compilation of C/C++/ObjC code across machines on a network."
SECTION = "devel"
LICENSE = "GPLv2"

PR = "r2"

DEPENDS = "avahi gtk+"
RRECOMMENDS_${PN} = "avahi-daemon"

SRC_URI = "http://distcc.googlecode.com/files/distcc-${PV}.tar.bz2 \
           file://default \
	   file://distccmon-gnome.desktop \
	   file://distcc"

inherit distutils-base autotools update-rc.d

INITSCRIPT_NAME = "distcc"

EXTRA_OECONF = " --with-gtk --with-avahi ac_cv_path_PYTHON=${STAGINGDIR_NATIVE}/python PYTHON_CFLAGS=-I${STAGING_INCDIR}/${PYTHON_DIR}"

do_install_append() {
    install -d ${D}${sysconfdir}/init.d/
    install -d ${D}${sysconfdir}/default
    install -d ${D}${sysconfdir}/distcc
    install -m 0755 ${WORKDIR}/distcc ${D}${sysconfdir}/init.d/
    install -m 0755 ${WORKDIR}/default ${D}${sysconfdir}/default/distcc
    install -m 0644 ${WORKDIR}/distccmon-gnome.desktop ${D}${datadir}/distcc/
    echo "+zeroconf" > ${D}${sysconfdir}/distcc/hosts
}

PACKAGES += "distcc-distmon-gnome"

FILES_${PN} = " ${sysconfdir} \
		${bindir}/distcc \
		${bindir}/lsdistcc \
		${bindir}/distccd \
		${bindir}/distccmon-text"

FILES_${PN}-dbg += "${bindir}/.debug"

CONFFILES_${PN} += "${sysconfdir}/default/distcc \
                    ${sysconfdir}/distcc/hosts \
                    ${sysconfdir}/init.d/distcc \
                   "

FILES_distcc-distmon-gnome = "  ${bindir}/distccmon-gnome \
				${datadir}/distcc"

pkg_postinst_${PN} () {
    # can't do this offline
    if [ "x$D" != "x" ]; then
        exit 1
    fi
    grep "^distcc:" /etc/group > /dev/null || addgroup distcc
    grep "^distcc:" /etc/passwd > /dev/null || adduser --disabled-password --system --home /var/lib/distcc distcc --ingroup distcc -g "distcc daemon"
}

pkg_postrm_${PN} () {
    deluser distcc || true
    delgroup distcc || true
}

SRC_URI[md5sum] = "a1a9d3853df7133669fffec2a9aab9f3"
SRC_URI[sha256sum] = "f55dbafd76bed3ce57e1bbcdab1329227808890d90f4c724fcd2d53f934ddd89"

license: MIT

repository: overo/overo-oe-natty

license_type: permissive

repo_name: overo/overo-oe-natty

branch_name: HEAD

extension: bb


text: @inproceedings{Cardoso07ESA,	address = {Funchal, Portugal},	author = {Cardoso, Jorge},	booktitle = {3rd International Conference Interoperability for Enterprise Software and Applications (I-ESA 2007)},	date = {March 28th-30th},	date-added = {2018-04-25 20:02:07 +0000},	date-modified = {2018-04-25 20:02:07 +0000},	isbn = {978-1-84628-857-9},	owner = {Jorge Cardoso},	pages = {333-344},	publisher = {Springer},	refid = {58},	timestamp = {2010.08.26},	title = {Integrating HAD Organizational Data Assets using Semantic Web Technologies},	webpdf = {/Papers/CP-2007-046-IESA-Integrating-HAD-organizational-data-assets.pdf},	year = {2007}}

branch_name: refs/heads/master

gha_license_id: MIT

gha_language: TeX

extension: bib


text:
require cim-schema.inc

LICENSE = "DMTF"

RCONFLICTS:${PN} = "cim-schema-exper"

SRC_URI = "http://dmtf.org/sites/default/files/cim/cim_schema_v2400/cim_schema_${PV}Final-MOFs.zip;subdir=${BP} \
    file://LICENSE \
"
SRC_URI[md5sum] = "a9bdf17c7374e3b5b7adeaac4842c4ad"
SRC_URI[sha256sum] = "dbfa3064ea427acd71a4bebbc172ca2dc44b0b09a6d83b0945b9ffa988a9058a"
LIC_FILES_CHKSUM = "file://${WORKDIR}/LICENSE;md5=eecc6f71a56ff3caf17f15bf7aeac7b4"

do_install() {
    install -d -m 0755 ${D}${datadir}/mof/cimv${PV}/
    install -d -m 0755 ${D}${datadir}/doc/cim-schema-${PV}
    install -m 644 ${WORKDIR}/LICENSE ${D}${datadir}/doc/cim-schema-${PV}

    cp -R --no-dereference --preserve=mode,links -v ${S}/* ${D}${datadir}/mof/cimv${PV}/
    chown -R root:root ${D}${datadir}/mof/cimv${PV}/
    for i in `find ${D}${datadir}/mof/cimv${PV} -name "*.mof"`; do
        sed -i -e 's/\r//g' $i
    done
    ln -s cimv${PV} ${D}${datadir}/mof/cim-current
    ln -s cim_schema_${PV}.mof ${D}${datadir}/mof/cim-current/CIM_Schema.mof
}

FILES:${PN} = "${datadir}/mof/* ${datadir}/doc/*"
FILES:${PN}-doc = ""

repository: openembedded/meta-openembedded

repo_name: openembedded/meta-openembedded

gha_language: BitBake


text:
# This recipe was inspired from:
# http://cgit.openembedded.org/meta-openembedded/commit/?id=0ec21b6a50058d703f40f77e1845bf8df637e7bd
SUMMARY = "PIP is a tool for installing and managing Python packages"
LICENSE = "MIT & LGPL-2.1"
LIC_FILES_CHKSUM = "file://LICENSE.txt;md5=593c6cd9d639307226978cbcae61ad4b"

SRC_URI = "https://pypi.python.org/packages/source/p/pip/pip-${PV}.tar.gz"

SRC_URI[md5sum] = "52f75ceb21e96c258f289859a2996b60"
SRC_URI[sha256sum] = "a0e11645ee37c90b40c46d607070c4fd583e2cd46231b1c06e389c5e814eed76"

S = "${WORKDIR}/pip-${PV}"

inherit setuptools3

# Since PIP is like CPAN for PERL we need to drag in all python modules to ensure everything works
RDEPENDS_${PN} = "python-modules python-distribute"

repository: patersonc/meta-renesas-ai

repo_name: patersonc/meta-renesas-ai


text:
//go:build !no_gzip
// +build !no_gzip

package compress

import (
	"bytes"
	"github.com/klauspost/compress/gzip"
	"github.com/xitongsys/parquet-go/parquet"
	"io/ioutil"
	"sync"
)

var gzipWriterPool sync.Pool

func init() {
	gzipWriterPool = sync.Pool{
		New: func() interface{} {
			return gzip.NewWriter(nil)
		},
	}

	compressors[parquet.CompressionCodec_GZIP] = &Compressor{
		Compress: func(buf []byte) []byte {
			res := new(bytes.Buffer)
			gzipWriter := gzipWriterPool.Get().(*gzip.Writer)
			gzipWriter.Reset(res)
			gzipWriter.Write(buf)
			gzipWriter.Close()
			gzipWriter.Reset(nil)
			gzipWriterPool.Put(gzipWriter)
			return res.Bytes()
		},
		Uncompress: func(buf []byte) (i []byte, err error) {
			rbuf := bytes.NewReader(buf)
			gzipReader, _ := gzip.NewReader(rbuf)
			res, err := ioutil.ReadAll(gzipReader)
			return res, err
		},
	}
}

repository: xitongsys/parquet-go

repo_name: xitongsys/parquet-go

gha_language: Go

extension: go


text:
# Copyright (C) 2018 Digi International Inc.

SUMMARY = "Home Addons"
DESCRIPTION = "Adding optional files to homedir"
LICENSE = "CLOSED"

FILESEXTRAPATHS_prepend := "${THISDIR}/files:"

RPROVIDES_${PN} += "${PN}"

SRC_URI = " \
	file://.profile \
	file://LED_kitt.py \
	file://demo_i2c_MCP23017.py \
	file://demo_i2c_PCF8574.py \
	file://gpio67_button.sh \
	file://gpio75_led_on_off.sh \
	file://ledmulti2.sh \
	file://ledmulti_blink2.sh \
	file://ledmulti_blink.sh \
	file://setup_demo_gpio.sh \
	file://setup_gpioled.sh \
	file://timer_adc_led.sh \
"

# Specify where to get the files
S = "${WORKDIR}"

do_configure[noexec] = "1"
do_compile[noexec] = "1"

do_install() {
	# creating the destination directories
	install -d ${D}/home/root

	# extra files need to go in the respective directories
	install -m 0644 ${WORKDIR}/.profile ${D}/home/root/
	install -m 0644 ${WORKDIR}/LED_kitt.py ${D}/home/root/
	install -m 0644 ${WORKDIR}/demo_i2c_MCP23017.py ${D}/home/root
	install -m 0644 ${WORKDIR}/demo_i2c_PCF8574.py ${D}/home/root
	install -m 0755 ${WORKDIR}/gpio67_button.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/gpio75_led_on_off.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/ledmulti2.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/ledmulti_blink2.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/ledmulti_blink.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/setup_demo_gpio.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/setup_gpioled.sh ${D}/home/root
	install -m 0755 ${WORKDIR}/timer_adc_led.sh ${D}/home/root
}

FILES_${PN} += "/home/root/* /home/root/.profile "

repository: paolochiarlone/meta-paoloc

repo_name: paolochiarlone/meta-paoloc


text:
require bug-app.inc

DESCRIPTION = "This app is loaded on a BUG to give demos.  It launched native demo apps from the hotkeys."
HOMEPAGE = "http://buglabs.net/applications/DemoBunny5000"

DEPENDS += "com.buglabs.osgi service-tracker com.buglabs.common "

PV = "4"

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

APIVERSION = ""


text:
@inproceedings{cibrian2016collective,
 author = {Cibrian, Franceli L and Weibel, Nadir and Tentori, Monica},
 booktitle = {Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing},
 pages = {328--339},
 title = {Collective use of a fabric-based interactive surface to support early development in toddler classrooms},
 year = {2016}
}

repository: robinzhx/hxi-website

repo_name: robinzhx/hxi-website

branch_name: refs/heads/main


text:
package dorado

import (
	"context"
	"fmt"
	"strconv"

	"github.com/pkg/errors"
)

// EthernetPort is type definition
type EthernetPort struct {
	BONDID             string `json:"BONDID"`
	BONDNAME           string `json:"BONDNAME"`
	ERRORPACKETS       string `json:"ERRORPACKETS"`
	ETHDUPLEX          string `json:"ETHDUPLEX"`
	ETHNEGOTIATE       string `json:"ETHNEGOTIATE"`
	HEALTHSTATUS       string `json:"HEALTHSTATUS"`
	ID                 string `json:"ID"`
	INIORTGT           string `json:"INIORTGT"`
	IPV4ADDR           string `json:"IPV4ADDR"`
	IPV4GATEWAY        string `json:"IPV4GATEWAY"`
	IPV4MASK           string `json:"IPV4MASK"`
	IPV6ADDR           string `json:"IPV6ADDR"`
	IPV6GATEWAY        string `json:"IPV6GATEWAY"`
	IPV6MASK           string `json:"IPV6MASK"`
	ISCSINAME          string `json:"ISCSINAME"`
	ISCSITCPPORT       string `json:"ISCSITCPPORT"`
	LOCATION           string `json:"LOCATION"`
	LOGICTYPE          string `json:"LOGICTYPE"`
	LOSTPACKETS        string `json:"LOSTPACKETS"`
	MACADDRESS         string `json:"MACADDRESS"`
	MTU                string `json:"MTU"`
	NAME               string `json:"NAME"`
	OVERFLOWEDPACKETS  string `json:"OVERFLOWEDPACKETS"`
	OWNINGCONTROLLER   string `json:"OWNINGCONTROLLER"`
	PARENTID           string `json:"PARENTID"`
	PARENTTYPE         int    `json:"PARENTTYPE"`
	PORTSWITCH         string `json:"PORTSWITCH"`
	RUNNINGSTATUS      string `json:"RUNNINGSTATUS"`
	SHARETYPE          string `json:"SHARETYPE"`
	SPEED              string `json:"SPEED"`
	STARTTIME          string `json:"STARTTIME"`
	TYPE               int    `json:"TYPE"`
	CrcErrors          string `json:"crcErrors"`
	DswID              string `json:"dswId"`
	DswLinkRight       string `json:"dswLinkRight"`
	FrameErrors        string `json:"frameErrors"`
	FrameLengthErrors  string `json:"frameLengthErrors"`
	LightStatus        string `json:"lightStatus"`
	MaxSpeed           string `json:"maxSpeed"`
	NumberOfInitiators string `json:"numberOfInitiators"`
	SelectType         string `json:"selectType"`
	WorkModeList       string `json:"workModeList"`
	WorkModeType       string `json:"workModeType"`
	ZoneID             string `json:"zoneId"`
}

// GetAssociatedEthernetPort get ethernet port associated ASSOCIATEOBJID (maybe port group).
// you must set ASSOCIATEOBJID and ASSOCIATEOBJTYPE. we recommend use dorado.GetPortalIPAddresses().
func (d *Device) GetAssociatedEthernetPort(ctx context.Context, query *SearchQuery) ([]EthernetPort, error) {
	spath := "/eth_port/associate"

	if query == nil || query.AssociateObjType == "" || query.AssociateObjID == "" {
		return nil, errors.New("you must set associated parameter")
	}

	req, err := d.newRequest(ctx, "GET", spath, nil)
	if err != nil {
		return nil, fmt.Errorf(ErrCreateRequest+": %w", err)
	}
	req = AddSearchQuery(req, query)

	var etherports []EthernetPort
	if err = d.requestWithRetry(req, &etherports, DefaultHTTPRetryCount); err != nil {
		return nil, fmt.Errorf(ErrRequestWithRetry+": %w", err)
	}

	if len(etherports) == 0 {
		return nil, ErrEthernetPortNotFound
	}

	return etherports, nil
}

// GetPortalIPAddresses get iSCSI portal IP addresses that associated port group.
// return only IPv4 address.
func (d *Device) GetPortalIPAddresses(ctx context.Context, portgroupID int) ([]string, error) {
	query := &SearchQuery{
		AssociateObjID:   strconv.Itoa(portgroupID),
		AssociateObjType: strconv.Itoa(TypePortGroup),
	}

	ethernetports, err := d.GetAssociatedEthernetPort(ctx, query)
	if err != nil {
		return nil, fmt.Errorf("failed to associated ethernet port: %w", err)
	}

	var portalIPs []string
	for _, ethernetport := range ethernetports {
		portalIPs = append(portalIPs, ethernetport.IPV4ADDR)
	}

	if len(portalIPs) == 0 {
		return nil, errors.New("portal ip addresses is not found")
	}

	return portalIPs, nil
}

// GetPortalIPAddresses is dorado.Client version of dorado.Device.GetPortalIPAddresses.
func (c *Client) GetPortalIPAddresses(ctx context.Context, localPortgroupID, remotePortgroupID int) ([]string, error) {
	localIPs, err := c.LocalDevice.GetPortalIPAddresses(ctx, localPortgroupID)
	if err != nil {
		return nil, fmt.Errorf("failed to get local portal IP: %w", err)
	}

	remoteIPs, err := c.RemoteDevice.GetPortalIPAddresses(ctx, remotePortgroupID)
	if err != nil {
		return nil, fmt.Errorf("failed to get remote portal IP: %w", err)
	}

	ips := append(localIPs, remoteIPs...)
	return ips, nil
}


text:
@article{Guo:2019:VEA:3312745.3182187,
 author = {Guo, Fangzhou and Gu, Tianlong and Chen, Wei and Wu, Feiran and Wang, Qi and Shi, Lei and Qu, Huamin},
 title = {Visual Exploration of Air Quality Data with a Time-correlation-partitioning Tree Based on Information Theory},
 journal = {ACM Transactions on Interactive Intelligent Systems},
 issue_date = {February 2019},
 volume = {9},
 number = {1},
 month = feb,
 year = {2019},
 issn = {2160-6455},
 pages = {4:1--4:23},
 articleno = {4},
 numpages = {23},
 url = {http://doi.acm.org/10.1145/3182187},
 doi = {10.1145/3182187},
 acmid = {3182187},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Sensor, information theory, multivariate time series, transfer entropy},
}


text:
inherit esw_examples features_check

REQUIRED_DISTRO_FEATURES = "emacps"

ESW_COMPONENT_SRC = "/XilinxProcessorIPLib/drivers/emacps/examples/"

repository: fullstackfpga/meta-xilinx

repo_name: fullstackfpga/meta-xilinx


text:
DESCRIPTION = "TFS rootfs image with Qt5 and the End application"

inherit core-image

IMAGE_FSTYPES = "tar ubi sdcard"

LICENSE = "CLOSED"

DEPENDS = "u-boot-variscite linux-variscite initscripts testscripts"
export IMAGE_BASENAME = "tfs-image-debug-rootfs"

IMAGE_INSTALL += " \
  packagegroup-tfs-base \
  packagegroup-tfs-deeplaser \
  packagegroup-tfs-qt5-modules \
  packagegroup-tfs-app \
  packagegroup-core-tools-debug \
  packagegroup-tfs-debug \
	"
EXTRA_IMAGE_FEATURES = "debug-tweaks ssh-server-openssh "
INSANE_SKIP_${PN} = "dev-so"

repository: thotakabsp/Morty

repo_name: thotakabsp/Morty


text:
#[==[.md
# vtkcompiletools-config.cmake

This file is used by CMake when finding VTK's compile tools.
#]==]

cmake_policy(PUSH)
cmake_policy(VERSION 3.8...3.12)

set("${CMAKE_FIND_PACKAGE_NAME}_VERSION" "@VTK_MAJOR_VERSION@.@VTK_MINOR_VERSION@.@VTK_BUILD_VERSION@")

set("${CMAKE_FIND_PACKAGE_NAME}_FOUND" 1)
include("${CMAKE_CURRENT_LIST_DIR}/${CMAKE_FIND_PACKAGE_NAME}-targets.cmake")
include("${CMAKE_CURRENT_LIST_DIR}/${CMAKE_FIND_PACKAGE_NAME}-vtk-module-properties.cmake")

cmake_policy(POP)

extension: in


text:
DESCRIPTION = "pngcheck verifies the integrity of PNG, JNG and MNG files"
HOMEPAGE = "http://www.libpng.org/pub/png/apps/pngcheck.html"
LICENSE = "GPLv2"
LIC_FILES_CHKSUM = "file://gpl/COPYING;md5=94d55d512a9ba36caa9b7df079bae19f"
DEPENDS = "zlib libpng"

SRC_URI = "${SOURCEFORGE_MIRROR}/project/png-mng/${BPN}/${PV}/${BPN}-${PV}.tar.gz"

SRC_URI[md5sum] = "980bd6d9a3830fdce746d7fe3c9166ee"
SRC_URI[sha256sum] = "77f0a039ac64df55fbd06af6f872fdbad4f639d009bbb5cd5cbe4db25690f35f"

do_compile() {
    oe_runmake -f Makefile.unx INCS=-I${STAGING_DIR_HOST}${incdir} LIBS=${STAGING_DIR_HOST}${libdir}/libz.a
}

do_install() {
    install -d ${D}${bindir}
    install pngcheck ${D}${bindir}
    install png-fix-IDAT-windowsize ${D}${bindir}
    install pngsplit ${D}${bindir}
}

repository: ExorEmbedded/exor-workspace

repo_name: ExorEmbedded/exor-workspace

gha_language: Python


text:
@InProceedings{lim16,
  supplementary = {Supplementary:lim16-supp.pdf},
  title = {Efficient Bregman Projections onto the Permutahedron and Related Polytopes},
  author = {Lim, Cong Han and Wright, Stephen J.},
  pages = {1205-1213},
  abstract = {The problem of projecting onto the permutahedron $\mathbf{PH}(c)$ -- the convex hull of all permutations of a fixed vector $c$ -- under a uniformly separable Bregman divergence is shown to be reducible to the Isotonic Optimization problem. This allows us to employ known fast algorithms to improve on several recent results on Bregman projections onto permutahedra. In addition, we present a new algorithm ${\rm mergepool}$ that have better complexity when the number of distinct entries $d$ in the vector $c$ is small, the simplex being one such example, with $c=(1,0,0,\dotsc,0)^T$ and $d=2$. ${\rm mergepool}$ runs in $O(n \log d)$ for certain popular Bregman divergence measures and requires $O((n \log d) \log \frac{U} {\epsilon})$ to find $\epsilon$-close solutions for general uniformly separable Bregman divergences, where $U$ is a bound on the width of the interval containing the dual solution components. These estimates matches or improves best known bounds for all Bregman projection problems onto various permutahedra, including recent results for projection onto the simplex. The same complexity bounds apply to signed permutahedra, a class that includes the $\ell_1$-ball as a special case. In summary, this work describes a fast unified approach to this well-known class of problems.},
}

repository: mreid/papersite

repo_name: mreid/papersite


text:
@InProceedings{hellerstein12,
  title = {Tight Bounds on Proper Equivalence Query Learning of DNF},
  author = {Lisa   Hellerstein and Devorah Kletenik and Linda Sellie and Rocco Servedio},
  pages = {31.1--31.18},
  abstract = {We prove a new structural lemma for partial Boolean functions \emph{f}, which we call the \emph{seed lemma} for \emph{DNF}. Using the lemma, we give the first subexponential algorithm for proper learning of poly(\emph{n})-term DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity 2^{(Õ√\emph{n})}, which is optimal. We also give a new result on certificates for DNF-size, a simple algorithm for properly PAC-learning DNF, and new results on EQ-learning log \emph{n}-term DNF and decision trees.},
  pdf = {http://jmlr.org/proceedings/papers/v23/hellerstein12/hellerstein12.pdf},
}