On the representation of infinite temporal data and queries (extended abstract)
Published 1 April 1991Open access
Marianne Baudinet, Marc Niézette, Pierre Wolper
Citations58
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This chapter discusses how to store a temporal predicate in a database using a formalism that allows the finite representation of at least some infinite temporal extensions.
Abstract
peer reviewed
Keywords
Computer Science
Constraint logic programming
1,613 Citations1987Joxan Jaffar, J.-L. Lassez
A class of programming languages, the CLP languages, are defined, all of which share the same essential semantic properties, and are highly declarative and are soundly based within a unified framework of formal semantics.
Journal of the ACMThe Semantics of Predicate Logic as a Programming Language
1,463 Citations1976M. H. van Emden, Robert Kowalski
In this paper the operational and fixpoint semantics of predicate logic programs are defined, and the connections with the proof theory and model theory of logic are investigated, and it is concluded that operational semantics is a part ofProof theory and that fixpoint semantic is a special case of model-theoretic semantics.
On the temporal analysis of fairness
726 Citations1980Dov M. Gabbay, Amir Pnueli +2 more
It is shown that with the addition of the 'until' operator -U the temporal language becomes expressively complete and two deductive systems DX and DUX are proved to be complete for the languages without and with the new operator respectively.
Journal of Computer and System SciencesConstraint Query Languages
679 Citations1995Paris C. Kanellakis, Gabriel M. Kuper +1 more
It is shown that efficient, declarative database programming can be combined with efficient constraint solving and the key intuition is that the generalization of a ground fact is a conjunction of constraints over a small number of variables.
Journal of Computer and System SciencesStructure and complexity of relational queries
537 Citations1982Ashok K. Chandra, David Harel
This paper is an attempt at laying the foundations for the classification of queries on relational data bases according to their structure and their computational complexity, using a Σ-Π hierarchy of height, ω2, called the fixpoint query hierarchy, and its properties investigated.
The Journal of Logic ProgrammingHorn clause queries and generalizations
309 Citations1985Ashok K. Chandra, David Harel
It is shown that logic programs express precisely the queries in YE + (the set of queries representable by a fixpoint applied to a positive existential query), and the resulting class has the expressive power of universally quantified second-order logic.
Reasoning about infinite computation paths
309 Citations1983Pierre Wolper, Moshe Y. Vardi +1 more
This work investigates extensions of temporal logic by finite automata on infinite words by investigating the addition of alternation and shows that it does not increase the complexity of the decision problem.
A temporal fixpoint calculus
205 Citations1988Moshe Y. Vardi
The automata-theoretic paradigm is extended to μTL, which is the extension of temporal logic by fixpoint operators and past temporal connectives, and it is shown how to produce a finite-state Büchi automaton, whose size is at most exponentially bigger than the size of @@@@.
Constraint query languages (preliminary report)
197 Citations1990Paris C. Kanellakis, Gabriel M. Kuper +1 more
It is shown that bottom-up, efficient, declarative database programming can be combined with efficient constraint solving, and the key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints.
Handling infinite temporal data
145 Citations1990F. Kabanza, J.-M. Stevenne +1 more
It is proved that relations formed from generalized tuples are closed under the operations of relational algebra, and a characterization of the expressiveness of generalized relations is given in terms of predicates definable in Presburger arithmetic.
Temporal deductive databases and infinite objects
109 Citations1988Jan Chomicki, Tomasz Imieliński
This work discusses deductive databases with one fixed occurrence of a monadic function symbol(successor) per predicate and defines the notion of infinite objects which makes some infinite least fixpoints computable in finite time.
Information and ControlA combinatorial approach to the theory of ω-automata
78 Citations1981Wolfgang Thomas
A combinatorial lemma is proved and used here to derive new results on ω -automata and to give simpler proofs of known ones and new normal form theorems and also decidability results are proved for the first-order and the monadic second-order theory of certain structures over the ordering of natural numbers.
Lecture notes in computer scienceA closed form for datalog queries with integer order
54 Citations1990Péter Révész
It is shown that Datalog queries with simple integer order constraints can be evaluated bottom-up in closed form over generalized databases.
Temporal logic programming is complete and expressive
50 Citations1989Marianne Baudinet
It is shown how propositional TEMPLOG programs can be translated into a temporal fixpoint calculus and it is proved that they can express essentially all regular properties of sequences.
Polynomial time query processing in temporal deductive databases
43 Citations1990Jan Chomicki
A bottom-up query processing algorithm BT is presented that is guaranteed to terminate in polynomial time if the periods are polynomially bounded and it is shown that it can be decided whether a set of temporal rules is inflationary.
ACM SIGMOD RecordRelational specifications of infinite query answers
43 Citations1989Jan Chomicki, Tomasz Imieliński
Relational specifications of infinite query answers
25 Citations1989Jan Chomicki, Tomasz Imieliński
A method to finitely represent infinite least fixpoints and infinite query answers as relational specifications is presented, applicable to every domain-independent set of functional rules.
Logic programming semantics: techniques and applications
17 Citations1989Marianne Baudinet
It is proved that propositional TEMPLOG has essentially the expressiveness of finite automata or regular languages, and that its extension with stratified negation has the expressivity of Buchi automataor $\omega$-regular languages.