Our poster suggests a spiral model of CS teachers' knowledge growth in laboratory sessions, based on Shulman's model of pedagogical reasoning. Our proposed spiral model deals with much smaller units of time, e.g. a session or a part of a session in class, and with small units of knowledge. It is based on observations in laboratory sessions of regressed experts in the first, second and third time they taught inheritance and polymorphism, as well as on interviews with them.

This article reports on difficulties related to the concepts of inheritance and polymorphism, expressed by a group of 22 in-service CS teachers with an experience with the procedural paradigm, as they coped with a course on OOP. Our findings are based on the analysis of tests, questionnaires that the teachers completed in the course, as well as on observations made during the course. The article suggests that the difficulties are mostly caused by the learners’ ignorance about a programming model for inheritance and polymorphism. Such a model is presented in the appendix. The article offers a classification of the difficulties into the following four clusters: (1) alternative (partial) models, (2) analogies to the use of inheritance and conversion in day-to-day life or in imperative programming, (3) lack of understanding of hierarchies and their role in inheritance, and (4) difficulties due to approaches to teaching, and their impact on the students understanding, as well as, with difficulties that arose in previous stages of learning OOP and have yet not been resolved.

When integrating geo‐spatial data sets, a join algorithm is used for finding sets of corresponding objects (i.e., objects that represent the same real‐world entity). This article investigates location‐based join algorithms for integration of several data sets. First, algorithms for integration of two data sets are presented and their performances, in terms of recall and precision, are compared. Then, two approaches for integration of more than two data sets are described. In one approach, all the integrated data sets are processed simultaneously. In the second approach, a join algorithm for two data sets is applied sequentially, either in a serial manner, where in each join at least one of the joined data sets is a single source, or in a hierarchical manner, where two join results can be joined. For the two approaches, join algorithms are given. The algorithms are designed to perform well even when location of objects are imprecise and each data set represents only some of the real‐world entities. Results of extensive experiments with the different approaches are provided and analyzed. The experiments show the differences, in accuracy and efficiency, between the approaches, under different circumstances. The results also show that all our algorithms have much better accuracy than applying the commonly used one‐sided nearest‐neighbor join.

Due to a reform in the Israeli CS high school curricula, in-service teachers who studied and taught procedural programming are now required to cope with the new paradigm of OOP. In this paper we describe a case study in which we traced the difficulties of one in-service teacher as she taught the topic of inheritance and polymorphism for the first time. We noticed a growth in her knowledge in the laboratory problem-session, whereas in a similar pen-and-paper session no substantial knowledge growth took place. A qualitative analysis enabled us to discern how the combined factors of the teacher's experience, the presence of the computer, and students' expectations for workable solutions, pressured the teacher to seek to resolve difficulties through trial and error, which facilitated knowledge growth. We argue that all these factors have to be fulfilled in order for teacher learning to happen.

No abstract available.

Processes are increasingly being used to make complex application logic explicit. Programming using processes has significant advantages but it poses a difficult problem from the system point of view in that the interactions between processes cannot be controlled using conventional techniques. In terms of recovery, the steps of a process are different from operations within a transaction. Each one has its own termination semantics and there are dependencies among the different steps. Regarding concurrency control, the flow of control of a process is more complex than in a flat transaction. A process may, for example, partially roll back its execution or may follow one of several alternatives. In this article, we deal with the problem of atomicity and isolation in the context of processes. We propose a unified model for concurrency control and recovery for processes and show how this model can be implemented in practice, thereby providing a complete framework for developing middleware applications using processes.

MARIFlow System [1] provides for automating and monitoring the flow of control and data over the Internet among different organizations, thereby creating a platform necessary to describe higher order processes involving several organizations and companies. The architecture is general enough to be applied to any business practice where data flow among different industries and cooperations and the invocation of activities follow a pattern that can be described through a process definition. The example application provided within the scope of this project is on maritime industry A MARIFlow process is executed through cooperating agents, called MARCAs (MARIFlow Cooperating Agents) that are automatically initialized at each site that the process executes. MARCAs handle the activities at their site, provide for coordination with other MARCAs in the system by routing the documents in electronic form according to the process description, keeping track of process information, and providing for the security and authentication of documents as well as comprehensive monitoring facilities. More specifically, the functionality provided by the system is as follows: ¯ A declarative means to specify the control of document flow over the Internet where it is possible to define the source of data, its control flow and the activities that make use of this data. ¯ A fully distributed execution architecture achieved through cooperating agents over the Internet. The agents know about other agents that they need to communicate with and preserve their state during communication. They also manage local information for monitoring purposes and for recovering from failures. ¯ Communicating with inside firewall applications. A MARCA can activate in-house activities automati-

Catriel Beeri Hebrew University y Tova Milo Tel-Aviv University z Paula Ta-Shma Hebrew University x 1 Introduction Genericity is a property of queries expressed in declarative query languages. The idea, first expressed in [2, 7], is that data values are uninterpreted, hence a query should be invariant under isomorphisms (i.e. element renaming) of databases. This has been generalized, following [10], to account for preservation of constants. This concept of genericity is intimately related to classical relational database research, that considered databases as constructed over an abstract domain of uninterpreted elements. However, the scope of database models has vastly expanded in the last decade. Multiple domains, use of domain functions and predicates, user-defined types, and bulk types --- these are essential components of recent data models. Genericity is central to many results in the theory of databases, yet little attention has been paid to it in the development of the...

We consider the relationship between the deductive and the functional/algebraic query language paradigms. Previous works considered this subject for a non-recursive algebra, or an algebra with a fixed point operation, and the corresponding class of deductive queries is that defined by stratified programs. We consider here algebraic languages extended by general recursive definitions. We also consider languages that allow non-restricted use of negation. It turns out that recursion and negation in the algebraic paradigm need to be studied together. The semantics used for the comparison is the valid semantics, although other well-known declarative semantics can also be used to derive similar results. We show that the class of queries expressed by general deduction with negation can be captured using algebra with recursive definitions.

New data models and languages have been the focus of attention in database research in the last decade. The object-oriented paradigm is a convenient vehicle for describing this research, its accomplishments, and for considering which directions are now interesting. This paper presents some concepts of object-oriented databases, and then considers recent interesting developments concerning query languages, object identities, views and meta-data.

Article Free Access Share on Functional and predictive programming in OODB's Authors: Catriel Beeri View Profile , Tova Milo View Profile Authors Info & Claims PODS '92: Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsJuly 1992 Pages 176–190https://doi.org/10.1145/137097.137863Published:01 July 1992Publication History 16citation241DownloadsMetricsTotal Citations16Total Downloads241Last 12 Months19Last 6 weeks4 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

We present the valid model semantics, a new approach to providing semantics for logic programs with negation, set-terms and grouping. The valid model semantics is a three-valued semantics, and is defined in terms of a ‘normal form’ computation. The valid model semantics also gives meaning to the generation and use of non-ground facts (i.e., facts with variables) in a computation.

Article Free Access Share on Subtyping in OODB's (extended abstract) Authors: Catriel Beeri Department of Computer Science, The Hebrew University, Jerusalem 91904, Israel Department of Computer Science, The Hebrew University, Jerusalem 91904, IsraelView Profile , Tova Milo Department of Computer Science, The Hebrew University, Jerusalem 91904, Israel Department of Computer Science, The Hebrew University, Jerusalem 91904, IsraelView Profile Authors Info & Claims PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1991Pages 300–314https://doi.org/10.1145/113413.113441Published:01 April 1991Publication History 3citation230DownloadsMetricsTotal Citations3Total Downloads230Last 12 Months13Last 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

Today's standard model for database concurrency control, called serializability theory, represents executions of transactions as partial orders of operations. The theory tells when an execution is serializable, that is, when the set of operations of a transaction execute atomically with respect to those of other transactions. It has been used successfully to prove correctness of most database concurrency control algorithms. Its most serious limitation is its inability to represent nested computations conveniently. This paper presents a more general model that permits nested transactions. In this model, transactions may execute subtransactions, giving rise to tree-structured computations. A serializability theory is developed for this model, which can be used to prove the correctness of concurrency control algorithms for nested transactions and for multilevel database systems. The theory is based on an abstract model of computation that allows arbitrary operations, and parallel and even nondeterministic programs. Axioms are presented that express the basic properties that programs that manage or access data need to satisfy. We use these axioms to derive proof techniques. One new technique—substitution—shows the equivalence of two executions by substituting one subcomputation by another, usually shallower (i.e., less nested), one. Our proof techniques are illustrated by applying them to several well-known concurrency control problems.

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

We consider the problem of propagating selections (i.e., bindings of variables) into logic programs. In particular, we study the class of binary chain programs and define selection propagation as the task of finding an equivalent program containing only unary derived predicates. We associate a context free grammar L(H) with every binary chain program H. We show that, given H propagating a selection involving some constant is possible iff L(H) is regular, and therefore undecidable. We also show that propagating a selection of the form p(X,X) is possible iff L(H) is finite, and therefore decidable. We demonstrate the connection of these two cases, respectively, with the weak monadic second order theory of one successor and with monadic generalized spectra. We further clarify the analogy between chain programs and languages from the point of view of program equivalence and selection propagation heuristics.

In this paper we extend LDL, a Logic Based Database Language, to include finite sets and negation. The new language is called LDL1. We define the notion of a model and show that a negation-free program need not have a model, and that it may have more than one minimal model. We impose syntactic restriction in order to define a deterministic language. These restrictions allow only layered (stratified) programs. We prove that for any program satisfying the syntactic restrictions of layering, there is a minimal model, and that this model can be constructed in a bottom-up fashion. Extensions to the basic grouping mechanism are proposed. We show that these extensions can be translated into equivalent LDL1 programs. Finally, we show how the technique of magic sets can be extended to translate LDL1 programs into equivalent programs which can often be executed more efficiently

This paper considers the efficient evaluation of recursive queries expressed using Horn Clauses. We define sideways information passing formally and show how a query evaluation algorithm may be defined in terms of sideways information passing and control. We then consider a class of information passing strategies which suffices to describe most query evaluation algorithms in the database literature, and show that these strategies may always be implemented by rewriting a given program and evaluating the rewritten program bottom-up. We describe in detail several algorithms for rewriting a program. These algorithms generalize the Counting and Magic Sets algorithms to work with arbitrary programs. Safety and optimality of the algorithms are also considered.

The desirability of acyclic database schemes is well argued in [8] and [13]. For schemas described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand sides and do not form intersection anomalies. In a recent work [4] it is argued that real-world database schemes always meet the former requirement, and in [5] it is shown that any given real-world scheme can be made to satisfy also the latter requirement, after being properly extended. However, the method of elimination of intersection anomalies proposed in [5] is intrinsically nondeterministic—an undesirable property for a design tool. In the present work it is shown that this nondeterminism does not, however, affect the final result of the design process. In addition, we present an efficient deterministic algorithm, which is equivalent to the nondeterministic process of [5]. Along the way a study of intersection anomalies, which is interesting in its own right, is performed.

The desirability of acyclic (conflict-free) schemes is well argued in [8] and [13]. When a scheme is described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand side and do not form intersection anomalies . It is shown that if the second condition fails to hold, the scheme can be amended so that it does hold. The basic step is to add one attribute and some dependencies to resolve one intersection anomaly. This step generates an extension of the given scheme in which the anomaly does not exist. Also, the iterative use of the basic step is analyzed and it is proved that the transformation so defined terminates and removes all intersection anomalies.

We propose a new approach to the design of relational database schemes. The main features of the approach are the following: A combination of the traditional decomposition and synthesis approaches, thus allowing the use of both functional and multivalued dependencies. Separation of structural dependencies relevant for the design process from integrity constraints, that is, constraints that do not bear any structural information about the data and which should therefore be discarded at the design stage. This separation is supported by a simple syntactic test filtering out nonstructural dependencies. Automatic correction of schemes which lack certain desirable properties.

An Armstrong relation for a set of functional dependencies (FDs) is a relation that satisfies each FD implied by the set but no FD that is not implied by it.The structure and size (number of tuples) of Armstrong relatsons are investigated.Upper and lower bounds on the size of minimal-sized Armstrong relations are derived, and upper and lower bounds on the number of distinct entries that must appear m an Armstrong relation are given.It is shown that the time complexity of finding an Armstrong relation, gwen a set of functional dependencies, is precisely exponential in the number of attributes.Also shown ,s the falsity of a natural conjecture which says that almost all relations obeying a given set of FDs are Armstrong relations for that set of FDs.Finally, Armstrong relations are used to generahze a result, obtained by Demetrovics using quite complicated methods, about the possible sets of keys for a relauon.

A class of dependencies, tuple and equality generating dependencies, is defined, and the chase process is generalized to deal with these dependenetes.For total dependencies the chase is an exponential ttme decision procedure for the implication problem, and in some restricted cases it can be modified to run m polynomial Ume.For nontotal dependencies the chase is only a proof procedure.However, several cases for which it is a decision procedure are shown.It is also shown that equality is redundant for deciding implication of tuple-generating dependencies, and is "almost redundant" for dec~ding implication of equality-generating dependencies.

We develop several formal systems for tuple and equality generating dependencies. There are three kinds of systems, based upon substitution, tuple elimination and transitivity. We specialize our systems to several subclasses: total dependencies, template dependencies and binary dependencies. We also show that finding a formal system for embedded multivalued dependencies is equivalent to solving the implication problem for that class.

Concurrency control is the activity of synchronizing transactions that access shared data. A concurrency control algorithm is regarded as correct if it ensures that any interleaved execution of transactions is equivalent to a serial one. Such executions are called serializable. Serializability theory provides a method for modelling and analyzing the correctness of concurrency control algorithms [BSW, Pa].The concept of nested transaction has recently received much attention [GR], [Mo]. In a nested transaction model, each transaction can invoke sub- transactions, which can invoke sub-subtransactions, and so on. The natural modelling concept is the tree log. The leaves of a tree log are atomic operations executed by the underlying system. Internal nodes are operations (as seen by their parents) implemented as transactions (as seen by their children). Nodes are related by a partial order

The desirability of acyclic database scheme is well argued in [L,BFMY]. When a scheme is described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand side and do not form intersection anomalies. We show that if the second condition fails to hold, the scheme can be amended so that it holds. The basic step is to add one attribute and some dependencies to resolve one intersection anomaly. This step generates an extension of the given scheme in which the anomaly does not exists. We also analyze the repetitive use of the basic step and prove that the transformation so defined removes all intersection anomalies. Finally, we characterize a class of attributes that can be removed from the final scheme, leaving it acyclic.

A class of database schemes, called acychc, was recently introduced.It is shown that this class has a number of desirable properties.In particular, several desirable properties that have been studied by other researchers m very different terms are all shown to be eqmvalent to acydicity.In addition, several equivalent charactenzauons of the class m terms of graphs and hypergraphs are given, and a smaple algorithm for determining acychclty is presented.Also given are several eqmvalent characterizations of those sets M of multivalued dependencies such that M is the set of muRlvalued dependencies that are the consequences of a given join dependency.Several characterizations for a conflict-free (in the sense of Lien) set of muluvalued dependencies are provided.

The problem of entities that play multiple roles in a relational database is studied, with an emphasis on the universal relation view of the database. A tree structure is used to describe the compatibilities among attributes. The compatibility information for an attribute encodes role playing information that cannot be described by traditional data dependencies. This structure is used to define the semantics of a QUEL-like (Stonebraker et al. [1976]) query language that uses special naming rules to permit easy use of attribute compatibility

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

We show that functional dependency preservation can be tested in polynomial time. We show further that while finding a cover for all embedded dependencies is NP-complete, such a cover can be found in polynomial time if dependencies are preserved.

We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. When data dependencies are given, we need only consider those fixed points that satisfy the dependencies. A polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. We also provide an exponential algorithm to handle the case where there are functional and/or multivalued dependencies. Furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. Lastly, we introduce the “update sets” approach to database design as an application of these results.

The problem of whether a given dependency in a database relation can be derived from a given set of dependencies is investigated. We show that the problem can be decided in polynomial time when the given set consists of either multivalued dependencies only or of both functional and multivalued dependencies and the given dependency is also either a functional or a multivalued dependency. These results hold when the derivations are restricted not to use the complementation rule.

We investigate the question of when two database schemes embody the same information. We argue that this question reduces to the equivalence of the sets of fixed points of the project-join mappings associated with the two database schemes in question. When data dependencies are given, we need only consider those fixed points that satisfy the dependencies. A polynomial algorithm to test the equivalence of database schemes, when there are no dependencies, is given. We also provide an exponential algorithm to handle the case where there are functional and/or multivalued dependencies. Furthermore, we give a polynomial time test to determine whether a project-join mapping preserves a set of functional dependencies, and a polynomial time algorithm for equivalence of database schemes whose project-join mappings do preserve the given set of functional dependencies. Lastly, we introduce the “update sets” approach to database design as an application of these results.

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of several relations has the intuitively expected value (is lossless ) and to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.

Problems related to functional dependencies and the algorithmic design of relational schemas are examined. Specifically, the following results are presented: (1) a tree model of derivations of functional dependencies from other functional dependencies; (2) a linear-time algorithm to test if a functional dependency is in the closure of a set of functional dependencies; (3) a quadratic-time implementation of Bernstein's third normal form schema synthesis algorithm. Furthermore, it is shown that most interesting algorithmic questions about Boyce-Codd normal form and keys are NP -complete and are therefore probably not amenable to fast algorithmic solutions.

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, not all joins are semantically meaningful. This paper gives an efficient algorithm to determine whether the join of several relations is semantically meaningful (lossless) and an efficient algorithm to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. Similar techniques also apply to the case where data dependencies are multivalued.

We investigate the inference rules that can be applied to functional and multivalued dependencies that exist in a database relation. Three types of rules are discussed. First, we list the well known rules for functional dependencies. Then we investigate the rules for multivalued dependencies. It is shown that for each rule for functional dependencies the same rule or a similar rule holds for multivalued dependencies. There is, however, one additional rule for multivalued dependencies that has no parallel among the rules for functional dependencies. Finally, we present rules that involve functional and multivalued dependencies together. The main result of the paper is that the rules presented are complete for the family of functional and multivalued dependencies.

In this paper Valiant's decision procedure for equivalence of deterministic finite-turn pushdown machines is improved upon. The improved equivalence test is: Given two mahcines, one constructs a pushdown machine that simulates them simultaneously and accepts a string iff it is accepted by exactly one of them. The given machines are equivalent iff the simulating pda accepts the empty language. The simulating machine uses its pushdown store to hold the contents of the stores of the two simulated machines. In order ot prevent the tops of the two stores to get too far apart the simulating machine sometimes replaces the contents of one of the stores. Valiant 1,2 has proved the existence of a suitable function which determines the replacements. The crux of this paper is an algorithm for constructing such a function. The existence of such an algorithm enables us to calculate an upper bound on the time complexity of the improved algorithm. We obtain the results that equivalence of deterministic finite-turn pushdown automata can be tested in super-exponential time and equivalence of deterministic two-tape automata can be tested in exponential time.