Temporal Query LanguagesContents:Introduction to temporal databasesIntro to temporal databases (cont’d)2. Temporal databases2.1 Temporal domains2.1 Temporal domains (cont’d)Slide 8Slide 9Slide 102.2 Abstract temporal databases2.2 Abstract temporal db’s (cont’d)Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 192.3 Concrete temporal databases2.3 Concrete temporal db’s (cont’d)Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 292.4 Interoperability3 Properties of Query Languages4 Abstract Query Languages4.1 Relational Calculus (continued)4.2 Relational Algebra4.3 Temporal Logic4.4 Inductive Query Languages5 Concrete Query Languages5.1 TQuel (continued)5.2 TSQL25.3 Hist. Relational Data Model5.3 HRDM (continued)5.4 Backlog Relations5.4 Backlog Relations (continued)6 Incomplete Temporal info6 Incomplete Temporal info (cont’d)Slide 467 Related Work in AITemporal Query Languagesa Surveya Surveyby Jan Chomicki, January 24, 1995by Jan Chomicki, January 24, 1995Computing and Information SciencesComputing and Information SciencesKansas State UniversityKansas State UniversityPresented by Barry Klein, USC, October 3, 2000Presented by Barry Klein, USC, October 3, 2000Contents:1.1.Introduction to temporal databasesIntroduction to temporal databases2.2.Temporal databases overviewTemporal databases overview3.3.Properties of query languagesProperties of query languages4.4.Abstract query languagesAbstract query languages5.5.Concrete query languagesConcrete query languages6.6.Incomplete temporal informationIncomplete temporal information7.7.Related work in artificial intelligenceRelated work in artificial intelligenceIntroduction to temporal databasesKey concepts: Temporal Domain, Abstract and Key concepts: Temporal Domain, Abstract and Concrete representations/Query lang’s, Incomplete Concrete representations/Query lang’s, Incomplete Temporal Information. Temporal Information. Interpreted Interpreted db domain. db domain.Examples: financial/personnel/medical/legal records; Examples: financial/personnel/medical/legal records; network monitoring, process controlnetwork monitoring, process controlFramework: integrate temporal research with Framework: integrate temporal research with research in db theory, logic and AI.research in db theory, logic and AI.Eschew Temporal DB Glossary of Jensen, et al, in Eschew Temporal DB Glossary of Jensen, et al, in Tansel book, to comply with accepted db terms.Tansel book, to comply with accepted db terms.Intro to temporal databases (cont’d)ANSI/SPARC architecture: 3 levels:ANSI/SPARC architecture: 3 levels:Physical; External; Conceptual: abstract vs. concretePhysical; External; Conceptual: abstract vs. concreteAbstract: formal meaning: representation-independ’tAbstract: formal meaning: representation-independ’tConcrete: specific, finite rep of a certain data modelConcrete: specific, finite rep of a certain data modelAbstract languages:Abstract languages:11stst-order and temporal logic, relational algebra, -order and temporal logic, relational algebra, deductive languagesdeductive languagesConcrete languages:Concrete languages:TSQL2 + others in [107, 108, 110]TSQL2 + others in [107, 108, 110]2. Temporal databasesMajor issues:Major issues:Choice of temporal domains (only “flat” types Choice of temporal domains (only “flat” types considered in this survey)considered in this survey)Points vs. intervalsPoints vs. intervalsLinear vs. branchingLinear vs. branchingDense vs. discreteDense vs. discreteBounded vs. unbounded timeBounded vs. unbounded timeQuery Language issues: Query Language issues: formal semantics, expressiveness, formal semantics, expressiveness, implementationimplementation2.1 Temporal domainsTemporal ontology – 2 distinctions from AI Temporal ontology – 2 distinctions from AI and logic:and logic:Points, or instants (Points, or instants (atat particular times); particular times);Intervals (Intervals (durinduring ranges of time)g ranges of time)Point view dominant in database work: Point view dominant in database work: intervals defined as pairs of endpoints, intervals defined as pairs of endpoints, making it easy to move between the 2 views making it easy to move between the 2 views in first-order casein first-order case2.1 Temporal domains (cont’d)Mathematical structure on pointsMathematical structure on pointsPartial orderPartial orderTotal (linear) orderTotal (linear) orderEx: Ex: cycliccyclic time modeled with linear time modeled with linear transitive order, reflexive & symmetric, or transitive order, reflexive & symmetric, or with ultimately periodic setswith ultimately periodic setsBranching time modeled with partial order Branching time modeled with partial order satisfying left-linearity (no branch to left)satisfying left-linearity (no branch to left)2.1 Temporal domains (cont’d)Temporal domain: first-order structure with a Temporal domain: first-order structure with a given given SignatureSignature (set of Constant, Function and (set of Constant, Function and Relation symbols)Relation symbols)Typical elements of signatures:Typical elements of signatures:““<“ – binary-order relation<“ – binary-order relation““0” – origin or std ref pt of a temporal domain0” – origin or std ref pt of a temporal domain““s” – denotes succession of time pointss” – denotes succession of time points““+”, “-” – relative distance of time points+”, “-” – relative distance of time points““k” – periodicity: congruence modulo ” – periodicity: congruence modulo kk2.1 Temporal domains (cont’d)Standard temporal domains Standard temporal domains (in this 1(in this 1stst-order structure:-order structure:NN – natural numbers – natural numbersZZ – integers – integersQQ – rationals – rationalsRR – real numbers – real numbersEquality not necessarily available in domains like Equality not necessarily available in domains like TSQL2TSQL2Temp domains may have finite universes, or bounded Temp domains may have finite universes, or bounded subsets of standard domainssubsets of standard domains2.1 Temporal domains (cont’d)Common assumption: “Time is discrete and Common assumption: “Time is discrete and isomorphic to natural numbers” vs. AI view that isomorphic to natural numbers” vs. AI view that
View Full Document